Package it.unimi.dsi.webgraph.algo

Class TopKGeometricCentrality

java.lang.Object

it.unimi.dsi.webgraph.algo.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.

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 top-k 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

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 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 for Runtime.availableProcessors().

alpha - the exponent (used only if centrality is TopKGeometricCentrality.Centrality.EXPONENTIAL).

pl - a progress logger, or null.

Method Details

newLinCentrality

public static TopKGeometricCentrality newLinCentrality(ImmutableGraph g,
int k,
int threads)
                                                throws 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:

IllegalArgumentException

newHarmonicCentrality

public 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.

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,
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 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(String[] args)
                 throws JSAPException,
IOException

Throws:

JSAPException

IOException