Class TopKGeometricCentrality
public class TopKGeometricCentrality extends Object
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.
In more detail, this class can compute the top k nodes for a centrality
out of TopKGeometricCentrality.Centrality
. You must build a suitable instance using one of the
static factory method (i.e., newHarmonicCentrality(ImmutableGraph, int, int)
) and
then invoke compute()
on the instance. After the computation, the results will be available
in the public arrays centrality
and topK
.
The algorithm implemented in this class is the CutClos algorithm proposed by Michele Borassi, Pierluigi Crescenzi and Andrea Marino in “Fast and Simple Computation of Topk Closeness Centralities”, CoRR, abs/1507.01490, 2015. The implementation performs a number of parallel breadthfirst visits.
If k is small, the algorithm is much faster than the standard algorithm
which computes all centralities. For example, if k is 1
the difference can
be several orders of magnitude. For bigger values of k, the performance
improvement decreases, and for k equal to the number of nodes the performance is the same as the
trivial algorithm that computes all centralities. In that case, you might consider using
an approximate algorithm like HyperBall
.
 Author:
 Michele Borassi

Nested Class Summary
Nested Classes Modifier and Type Class Description static class
TopKGeometricCentrality.Centrality
The centralities with respect to which it is possible to find the top k nodes. 
Field Summary
Fields Modifier and Type Field Description double[]
centrality
If x is one of the k most central vertices,centrality[x]
will contain its centrality.int[]
topK
The k most central vertices, from the most central to the least central. 
Constructor Summary
Constructors Constructor Description TopKGeometricCentrality(ImmutableGraph g, int k, TopKGeometricCentrality.Centrality centralityType, int threads, double alpha, ProgressLogger pl)
Creates a new instance. 
Method Summary
Modifier and Type Method Description void
compute()
Compute topk geometric centralities.static void
main(String[] args)
static TopKGeometricCentrality
newExponentialCentrality(ImmutableGraph g, int k, double alpha, int threads)
Creates a new instance to compute the k most central vertices according to positive exponential centrality, logging every 10 seconds.static TopKGeometricCentrality
newHarmonicCentrality(ImmutableGraph g, int k, int threads)
Creates a new instance to compute the k most central vertices according to positive harmonic centrality, logging every 10 seconds.static TopKGeometricCentrality
newLinCentrality(ImmutableGraph g, int k, int threads)
Creates a new instance to compute the k most central vertices according to positive Lin's centrality, logging every 10 seconds.

Field Details

centrality
public final double[] centralityIf x is one of the k most central vertices,centrality[x]
will contain its centrality. On all other nodes, this array contains either 1 or the centrality of the node. 
topK
public int[] topKThe k most central vertices, from the most central to the least central.


Constructor Details

TopKGeometricCentrality
public TopKGeometricCentrality(ImmutableGraph g, int k, TopKGeometricCentrality.Centrality centralityType, int threads, double alpha, ProgressLogger pl)Creates a new instance. Parameters:
g
 the input graph.k
 the number of vertices required.centralityType
 the type of centrality.threads
 the number of threads, or 0 forRuntime.availableProcessors()
.alpha
 the exponent (used only ifcentrality
isTopKGeometricCentrality.Centrality.EXPONENTIAL
).pl
 a progress logger, ornull
.


Method Details

newLinCentrality
public static TopKGeometricCentrality newLinCentrality(ImmutableGraph g, int k, int threads) throws IllegalArgumentExceptionCreates a new instance to compute the k most central vertices according to positive Lin's centrality, logging every 10 seconds. Parameters:
g
 the input graph.k
 the number of vertices to be output.threads
 the number of threads, or 0 forRuntime.availableProcessors()
. Returns:
 the new instance.
 Throws:
IllegalArgumentException

newHarmonicCentrality
Creates a new instance to compute the k most central vertices according to positive harmonic centrality, logging every 10 seconds. Parameters:
g
 the input graph.k
 the number of vertices to be output.threads
 the number of threads, or 0 forRuntime.availableProcessors()
. Returns:
 the new instance.

newExponentialCentrality
public static TopKGeometricCentrality newExponentialCentrality(ImmutableGraph g, int k, double alpha, int threads)Creates a new instance to compute the k most central vertices according to positive exponential centrality, logging every 10 seconds. Parameters:
g
 the input graphk
 the number of vertices to be output.threads
 the number of threads, or 0 forRuntime.availableProcessors()
.alpha
 the base used for the exponential centrality. Returns:
 the new instance.

compute
public void compute()Compute topk geometric centralities. 
main
 Throws:
JSAPException
IOException
