Class ParallelBreadthFirstBetweennessCentrality
- java.lang.Object
-
- it.unimi.dsi.webgraph.scratch.ParallelBreadthFirstBetweennessCentrality
-
public class ParallelBreadthFirstBetweennessCentrality extends java.lang.Object
Computes the betweenness centrality using a parallel implementation of Brandes's algorithm (Ulrik Brandes, “A Faster Algorithm for Betweenness Centrality”, Journal of Mathematical Sociology 25(2):163−177, 2001).To use this class you first create an instance, and then invoke
compute()
. After that, you can peek at the fieldbetweenness
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 Classes Modifier and Type Class Description static class
ParallelBreadthFirstBetweennessCentrality.PathCountOverflowException
An exception telling that the path count exceeded 64-bit integer arithmetic.
-
Field Summary
Fields Modifier and Type Field Description double[]
betweenness
The array of betweenness value.it.unimi.dsi.fastutil.ints.IntArrayList
cutPoints
At the end of a visit, the cutpoints ofqueue
.double[]
delta
The array of dependencies (computed at the end of each visit).java.util.concurrent.atomic.AtomicIntegerArray
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).ImmutableGraph
graph
The graph under examination.it.unimi.dsi.fastutil.ints.IntArrayList
queue
The queue of visited nodes.java.util.concurrent.atomic.AtomicLongArray
sigma
The array containing the values of σ incremented for each parent/child pair during each visit, as explained in Brandes's algorithm.protected boolean
stop
Whether to stop abruptly the visiting process.
-
Constructor Summary
Constructors Constructor Description ParallelBreadthFirstBetweennessCentrality(ImmutableGraph graph)
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.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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
compute()
Performs a full computation.static void
main(java.lang.String[] arg)
-
-
-
Field Detail
-
graph
public final ImmutableGraph graph
The graph under examination.
-
queue
public final it.unimi.dsi.fastutil.ints.IntArrayList queue
The queue of visited nodes.
-
cutPoints
public final it.unimi.dsi.fastutil.ints.IntArrayList cutPoints
At 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
public final java.util.concurrent.atomic.AtomicIntegerArray 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
public final java.util.concurrent.atomic.AtomicLongArray 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[] delta
The array of dependencies (computed at the end of each visit).
-
betweenness
public final double[] betweenness
The array of betweenness value.
-
stop
protected volatile boolean stop
Whether to stop abruptly the visiting process.
-
-
Constructor Detail
-
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
public ParallelBreadthFirstBetweennessCentrality(ImmutableGraph graph, int requestedThreads)
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
public ParallelBreadthFirstBetweennessCentrality(ImmutableGraph graph)
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 Detail
-
compute
public void compute() throws java.lang.InterruptedException
Performs a full computation.- Throws:
java.lang.InterruptedException
-
main
public static void main(java.lang.String[] arg) throws java.io.IOException, com.martiansoftware.jsap.JSAPException, java.lang.InterruptedException
- Throws:
java.io.IOException
com.martiansoftware.jsap.JSAPException
java.lang.InterruptedException
-
-