Algorithm: Betweenness Centrality

[mknblch]

Betweenness Centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through or the sum of the weights of the edges is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

Progress

• [x] implement procedure
• [x] tests
• [x] edge case tests
• [x] simple benchmark
• [x] benchmark on bigger graphs
• [x] parallelization
• [x] documentation

TODO

• adapt apoc-procedure to algorithm-api

[mknblch]

We have 3 different implementations so far

• a sequential BC algorithms as described by Brandes
• our parallel adaptation if this algo
• a slightly changed brandes-algo which should be considered as experimental (must be tested on different kinds of graphs)

all of them calculate the (unweighted) node-betweenness based on the number of nodes (not their weight)

TODO

• im going to try if we can calculate the betweenness using @knutwalker 's MSBFS

[mknblch]

@tomasonjo Do we already have documentation?

[tomasonjo]

I see only two version:

=== algo.betweenness

• implementation of brandes-bc algorithm and nodePartitioning extension
• http://www.algo.uni-konstanz.de/publications/b-fabc-01.pdf
• if concurrency parameter is set (and >1) ParallelBetweennessCentrality is used
• ParallelBC spawns N(given by the concurrency param) concurrent threads for calculation where each one calculates the BC for one node at a time

=== algo.betweenness.exp1

• brandes-like algorithm which uses successor sets instead of predecessor sets
• The algorithm is based on Brandes definition but with some changes regarding the dependency-accumulation step.
• http://cass-mt.pnnl.gov/docs/pubs/georgiatechlbnlpnnlfastbc-mtaap2009.pdf

On Fri, Jul 21, 2017 at 8:36 PM, Martin Knobloch notifications@github.com wrote:

@tomasonjo https://github.com/tomasonjo Do we already have documentation?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/neo4j-contrib/neo4j-graph-algorithms/issues/98#issuecomment-317079657, or mute the thread https://github.com/notifications/unsubscribe-auth/ATBjTUz5Y42PuNrNSHiu-901S2wObtB1ks5sQO-WgaJpZM4NIy_a .

[JoKre17]

Is there the intention to make a weighted version of the betweenness centrality?

I guess I didn't really thought this through, but wouldn't it be possible e.g. for the normal BetweennessCentrality.java to replace the distances array with a float/double distances array and iterate over the relationships via the WeightedRelationshipIterator?

In most of the cases there won't be any or really small sigma values, I am not sure, wether this would be an issue, but I guess not.