Class GeometricCentralities
- java.lang.Object
-
- it.unimi.dsi.webgraph.algo.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 fieldscloseness
,lin
,harmonic
,exponential
andreachable
.
-
-
Field Summary
Fields Modifier and Type Field Description double
alpha
double[]
closeness
Closeness centrality.static double
DEFAULT_ALPHA
The default value foralpha
.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)
-
-
-
Field Detail
-
DEFAULT_ALPHA
public static final double DEFAULT_ALPHA
The default value foralpha
.- See Also:
- Constant Field Values
-
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
-
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 forRuntime.availableProcessors()
).pl
- a progress logger, ornull
.
-
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, ornull
.
-
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 forRuntime.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 incloseness
,lin
,harmonic
,exponential
andreachable
.- 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
-
-