Class ParallelBreadthFirstBetweennessCentrality
To use this class you first create an instance, and then invoke compute()
.
After that, you can peek at the field betweenness
to discover the betweenness of each node.
For every three distinct nodes s, t and v, let σst be the number of shortest paths from s to t, and σst(v) the number of such paths on which v lies. The betweenness centrality of node v is defined to be the sum of δst(v)=σst(v) / σst over all pairs of distinct nodes s, t different from v (the summand is assumed to be zero whenever the denominator is zero).
Brandes's approach consists in performing a breadth-first visit from every node, recording (in distance
) the
distance of the node from the current source. After each visit, nodes are considered in decreasing order of
distance, and for each of them we consider the arcs (v,w) such that the distance of w
is exactly one plus the distance of v: in this case we say that v is a parent of w.
Such parents are used to compute the values of δ (exactly as in the original algorithm, but without
any need to keep an explicit set of parents).
For more information about the way the visit is implemented in parallel, we refer the reader to ParallelBreadthFirstVisit
.
Performance issues
This class needs two integers and two doubles per node. If there are several available cores, breadth-first visits will be decomposed into relatively small tasks (small blocks of nodes in the queue at the same distance from the starting node) and each task will be assigned to the first available core. Since all tasks are completely independent, this ensures a very high degree of parallelism. However, on very sparse graphs the cost of keeping the threads synchronised can be extremely high, and even end up increasing the visit time.
Note that if the degree distribution is extremely skewed some cores might get stuck in the enumeration of the successors of some nodes with a very high degree.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic final class
An exception telling that the path count exceeded 64-bit integer arithmetic. -
Field Summary
FieldsModifier and TypeFieldDescriptionfinal double[]
The array of betweenness value.final it.unimi.dsi.fastutil.ints.IntArrayList
At the end of a visit, the cutpoints ofqueue
.final double[]
The array of dependencies (computed at the end of each visit).final AtomicIntegerArray
The array containing the distance of each node from the current source (or -1 if the node has not yet been reached by the visit).final ImmutableGraph
The graph under examination.final it.unimi.dsi.fastutil.ints.IntArrayList
The queue of visited nodes.final AtomicLongArray
The array containing the values of σ incremented for each parent/child pair during each visit, as explained in Brandes's algorithm.protected boolean
Whether to stop abruptly the visiting process. -
Constructor Summary
ConstructorsConstructorDescriptionCreates a new class for keeping track of the state of parallel breadth-first visits, using as many threads as the number of available processors.ParallelBreadthFirstBetweennessCentrality
(ImmutableGraph graph, int requestedThreads) Creates a new class for keeping track of the state of parallel breadth-first visits.ParallelBreadthFirstBetweennessCentrality
(ImmutableGraph graph, int requestedThreads, it.unimi.dsi.logging.ProgressLogger pl) Creates a new class for keeping track of the state of parallel breadth-first visits.ParallelBreadthFirstBetweennessCentrality
(ImmutableGraph graph, it.unimi.dsi.logging.ProgressLogger pl) Creates a new class for keeping track of the state of parallel breadth-first visits, using as many threads as the number of available processors. -
Method Summary
-
Field Details
-
graph
The graph under examination. -
queue
public final it.unimi.dsi.fastutil.ints.IntArrayList queueThe queue of visited nodes. -
cutPoints
public final it.unimi.dsi.fastutil.ints.IntArrayList cutPointsAt the end of a visit, the cutpoints ofqueue
. The d-th cutpoint is the first node in the queue at distance d. The last cutpoint is the queue size. -
distance
The array containing the distance of each node from the current source (or -1 if the node has not yet been reached by the visit). -
sigma
The array containing the values of σ incremented for each parent/child pair during each visit, as explained in Brandes's algorithm. -
delta
public final double[] deltaThe array of dependencies (computed at the end of each visit). -
betweenness
public final double[] betweennessThe array of betweenness value. -
stop
protected volatile boolean stopWhether to stop abruptly the visiting process.
-
-
Constructor Details
-
ParallelBreadthFirstBetweennessCentrality
public ParallelBreadthFirstBetweennessCentrality(ImmutableGraph graph, int requestedThreads, it.unimi.dsi.logging.ProgressLogger pl) Creates a new class for keeping track of the state of parallel breadth-first visits.- Parameters:
graph
- a graph.requestedThreads
- the requested number of threads (0 forRuntime.availableProcessors()
).pl
- a progress logger, ornull
.
-
ParallelBreadthFirstBetweennessCentrality
public ParallelBreadthFirstBetweennessCentrality(ImmutableGraph graph, it.unimi.dsi.logging.ProgressLogger pl) Creates a new class for keeping track of the state of parallel breadth-first visits, using as many threads as the number of available processors.- Parameters:
graph
- a graph.pl
- a progress logger, ornull
.
-
ParallelBreadthFirstBetweennessCentrality
Creates a new class for keeping track of the state of parallel breadth-first visits.- Parameters:
graph
- a graph.requestedThreads
- the requested number of threads (0 forRuntime.availableProcessors()
).
-
ParallelBreadthFirstBetweennessCentrality
Creates a new class for keeping track of the state of parallel breadth-first visits, using as many threads as the number of available processors.- Parameters:
graph
- a graph.
-
-
Method Details
-
compute
Performs a full computation.- Throws:
InterruptedException
-
main
public static void main(String[] arg) throws IOException, com.martiansoftware.jsap.JSAPException, InterruptedException - Throws:
IOException
com.martiansoftware.jsap.JSAPException
InterruptedException
-