Class 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 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 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 of queue.
      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.
    • 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)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • 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 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 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 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 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