it.unimi.dsi.webgraph.algo

## Class TopKGeometricCentrality

• java.lang.Object
• it.unimi.dsi.webgraph.algo.TopKGeometricCentrality

• ```public class TopKGeometricCentrality
extends java.lang.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 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`.

Author:
Michele Borassi
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and 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 and 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 and Description
```TopKGeometricCentrality(ImmutableGraph g, int k, TopKGeometricCentrality.Centrality centralityType, int threads, double alpha, ProgressLogger pl)```
Creates a new instance.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `compute()`
Compute top-k geometric centralities.
`static void` `main(java.lang.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.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Field Detail

• #### centrality

`public final double[] centrality`
If 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[] topK`
The k most central vertices, from the most central to the least central.
• ### Constructor Detail

• #### TopKGeometricCentrality

```public TopKGeometricCentrality(ImmutableGraph g,
int k,
TopKGeometricCentrality.Centrality centralityType,
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 for `Runtime.availableProcessors()`.
`alpha` - the exponent (used only if `centrality` is `TopKGeometricCentrality.Centrality.EXPONENTIAL`).
`pl` - a progress logger, or `null`.
• ### Method Detail

• #### newLinCentrality

```public static TopKGeometricCentrality newLinCentrality(ImmutableGraph g,
int k,
throws java.lang.IllegalArgumentException```
Creates 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 for `Runtime.availableProcessors()`.
Returns:
the new instance.
Throws:
`java.lang.IllegalArgumentException`
• #### newHarmonicCentrality

```public static TopKGeometricCentrality newHarmonicCentrality(ImmutableGraph g,
int k,
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 for `Runtime.availableProcessors()`.
Returns:
the new instance.
• #### newExponentialCentrality

```public static TopKGeometricCentrality newExponentialCentrality(ImmutableGraph g,
int k,
double alpha,
Creates a new instance to compute the k most central vertices according to positive exponential 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 for `Runtime.availableProcessors()`.
`alpha` - the base used for the exponential centrality.
Returns:
the new instance.
• #### compute

`public void compute()`
Compute top-k geometric centralities.
• #### main

```public static void main(java.lang.String[] args)
throws JSAPException,
java.io.IOException```
Throws:
`JSAPException`
`java.io.IOException`