Class TopKGeometricCentrality


public class TopKGeometricCentrality
extends Object
Computes the k most central vertices according to a positive geometric centrality. 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.

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 Top-k Closeness Centralities”, CoRR, abs/1507.01490, 2015. The implementation performs a number of parallel breadth-first 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.

Michele Borassi