jung.algorithms.scoring.BetweennessCentrality seems to be wrong

[darkclouder]

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.

[jrtom]

@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?

[darkclouder]

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);