Class GeometricCentralities


  • public class GeometricCentralities
    extends java.lang.Object
    Computes exactly a set of positive geometric centralitites (more precisely, closeness, Lin's, harmonic and exponential centrality) and the number of reachable nodes using multiple parallel breadth-first visits. Terminal nodes will have closeness centrality equal to zero and Lin's centrality equal to one. A survey about geometric centralities can be found “Axioms for centrality”, by Paolo Boldi and Sebastiano Vigna, Internet Math., 10(3-4):222−262, 2014. Explicit definitions can be found here.

    Note that usually one is interested in the negative version of a centrality measure, that is, the version that depends on the incoming arcs. This class can compute only positive centralities: if you are interested (as it usually happens) in the negative version, you must pass to this class the transpose of the graph.

    Every visit is independent and is carried out by a separate thread. The only contention point is the update of the array accumulating the betweenness score, which is negligible. The downside is that running on k cores requires approximately k times the memory of the sequential algorithm, as only the graph and the betweenness array will be shared.

    To use this class you first create an instance, and then invoke compute(). After that, you can peek at the fields closeness, lin, harmonic, exponential and reachable.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      double alpha
      The α parameter for exponential centrality: you can modify this field before calling compute() (its default value is 0.5).
      double[] closeness
      Closeness centrality.
      static double DEFAULT_ALPHA
      The default value for alpha.
      double[] exponential
      Exponential centrality.
      double[] harmonic
      Harmonic centrality.
      double[] lin
      Lin's centrality.
      protected java.util.concurrent.atomic.AtomicInteger nextNode
      The next node to be visited.
      long[] reachable
      Number of reachable nodes.
      protected boolean stop
      Whether to stop abruptly the visiting process.
    • Constructor Summary

      Constructors 
      Constructor Description
      GeometricCentralities​(ImmutableGraph graph)
      Creates a new class for computing positive geometric centralities and the number of reachable nodes, using as many threads as the number of available processors.
      GeometricCentralities​(ImmutableGraph graph, int requestedThreads)
      Creates a new class for computing positive geometric centralities and the number of reachable nodes.
      GeometricCentralities​(ImmutableGraph graph, int requestedThreads, it.unimi.dsi.logging.ProgressLogger pl)
      Creates a new class for computing positive geometric centralities and the number reachable nodes.
      GeometricCentralities​(ImmutableGraph graph, it.unimi.dsi.logging.ProgressLogger pl)
      Creates a new class for computing positive geometric centralities and the number of reachable nodes, 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()
      Computes geometric centralities and the number of reachable nodes.
      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

      • harmonic

        public final double[] harmonic
        Harmonic centrality.
      • closeness

        public final double[] closeness
        Closeness centrality.
      • lin

        public final double[] lin
        Lin's centrality.
      • exponential

        public final double[] exponential
        Exponential centrality.
      • alpha

        public double alpha
        The α parameter for exponential centrality: you can modify this field before calling compute() (its default value is 0.5).
      • reachable

        public final long[] reachable
        Number of reachable nodes.
      • nextNode

        protected final java.util.concurrent.atomic.AtomicInteger nextNode
        The next node to be visited.
      • stop

        protected volatile boolean stop
        Whether to stop abruptly the visiting process.
    • Constructor Detail

      • GeometricCentralities

        public GeometricCentralities​(ImmutableGraph graph,
                                     int requestedThreads,
                                     it.unimi.dsi.logging.ProgressLogger pl)
        Creates a new class for computing positive geometric centralities and the number reachable nodes.
        Parameters:
        graph - a graph.
        requestedThreads - the requested number of threads (0 for Runtime.availableProcessors()).
        pl - a progress logger, or null.
      • GeometricCentralities

        public GeometricCentralities​(ImmutableGraph graph,
                                     it.unimi.dsi.logging.ProgressLogger pl)
        Creates a new class for computing positive geometric centralities and the number of reachable nodes, using as many threads as the number of available processors.
        Parameters:
        graph - a graph.
        pl - a progress logger, or null.
      • GeometricCentralities

        public GeometricCentralities​(ImmutableGraph graph,
                                     int requestedThreads)
        Creates a new class for computing positive geometric centralities and the number of reachable nodes.
        Parameters:
        graph - a graph.
        requestedThreads - the requested number of threads (0 for Runtime.availableProcessors()).
      • GeometricCentralities

        public GeometricCentralities​(ImmutableGraph graph)
        Creates a new class for computing positive geometric centralities and the number of reachable nodes, using as many threads as the number of available processors.
        Parameters:
        graph - a graph.
    • Method Detail

      • compute

        public void compute()
                     throws java.lang.InterruptedException
        Computes geometric centralities and the number of reachable nodes. Results can be found in closeness, lin, harmonic, exponential and reachable.
        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