jung.algorithms.scoring.BetweennessCentrality seems to be wrong
Opened this issue · 2 comments
Hey there,
the implementation of jung.algorithms.scoring.BetweennessCentrality seems to be wrong.
Initially, I came across this because I was so surprised that the JUNG implementation is so much faster than my own.
Tested with this graph:
http://www.cs.utah.edu/~lifeifei/research/tpq/OL.cedge
(Edge list of Edge ID, Start Node ID, End Node ID, L2 Distance)
I used the L2 distance as an edge length.
I compared the vertex betweenness of JUNG with the betweenness that I get with my own implementation and then compared both with the implementation of Visone, a graphical graph tool from the chair of research of Ulrik Brandes (the creator of that particular betweenness algorithm in the first place). http://www.visone.info/html/download.html
Simply looking at node 0 shows a huge difference.
JUNG returns a betweenness of 0.0, my implementation and the one of Visone returns 38,924.
@darkclouder thanks for the report. I would imagine that a betweenness of 0 for anything that isn't an isolated node would be a bug, yeah (unless the edge lengths themselves are 0).
We need a couple of things in order to follow up on this.
(1) Which version of JUNG are you using?
(2) Can you give us a short self-contained snippet that shows how you invoked BC?
It's not the only one, I just picked one result by random. Generally, all betweenness scores by JUNG are far smaller than those of the official Brandes implementation (that has the same results as mine when I checked) in order of magnitude of... 3 or more.
(1) 2.1.1
(2)
final String edgeListFile = "OL.cedge.txt";
Graph<Integer, Integer> g = new UndirectedSparseGraph<>();
Map<Integer, Double> w = new HashMap<>();
try (BufferedReader br = new BufferedReader(new FileReader(edgeListFile))) {
for (String line; (line = br.readLine()) != null; ) {
String[] columns = line.split(" ");
final int edgeId = Integer.parseInt(columns[0]);
final int sourceId = Integer.parseInt(columns[1]);
final int targetId = Integer.parseInt(columns[2]);
final double distance = Double.parseDouble(columns[3]);
g.addEdge(edgeId, sourceId, targetId);
w.put(edgeId, distance);
}
} catch (IOException e) {
e.printStackTrace();
}
BetweennessCentrality bc = new BetweennessCentrality(g, w::get);