Class ParallelBreadthFirstBetweennessCentrality

java.lang.Object
it.unimi.dsi.webgraph.scratch.ParallelBreadthFirstBetweennessCentrality

public class ParallelBreadthFirstBetweennessCentrality extends 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 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.

  • Field Details

    • 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 of queue. The d-th cutpoint is the first node in the queue at distance d. The last cutpoint is the queue size.
    • distance

      public final 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 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 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 for Runtime.availableProcessors()).
      pl - a progress logger, or null.
    • 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, or null.
    • 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 for Runtime.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 Details