Module org.jgrapht.core

Package org.jgrapht.alg.scoring

Class EigenvectorCentrality<V,E>

java.lang.Object

org.jgrapht.alg.scoring.EigenvectorCentrality<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexScoringAlgorithm<V,Double>

public class EigenvectorCentrality<V,E>
extends Object
implements VertexScoringAlgorithm<V,Double>

Eigenvector-centrality implementation.

Eigenvector centrality, introduced in 1895 by Edmund Landau for chess tournaments, associates with a (weighted) graph the left dominant eigenvector of its adjacency matrix. More information can be found on wikipedia.

This is a simple iterative implementation of the power method which stops after a given number of iterations or if centrality values between two iterations do not change more than a predefined value (technically, we stop when the ℓ₂ norm of the difference between the current estimate and the next one drops below a given threshold). Correspondingly, the result will be ℓ₂-normalized.

Each iteration of the algorithm runs in linear time O(n+m) when n is the number of nodes and m the number of edges of the graph. The maximum number of iterations can be adjusted by the caller. The default value is MAX_ITERATIONS_DEFAULT. Also in case of weighted graphs, negative weights are not expected.

Author:

Sebastiano Vigna

Field Summary

Fields

Modifier and Type	Field	Description
static int	MAX_ITERATIONS_DEFAULT	Default number of maximum iterations.
static double	TOLERANCE_DEFAULT	Default value for the tolerance.

Constructor Summary

Constructors

Constructor	Description
EigenvectorCentrality(Graph<V,E> g)	Create and execute an instance of EigenvectorCentrality
EigenvectorCentrality(Graph<V,E> g, int maxIterations)	Create and execute an instance of EigenvectorCentrality
EigenvectorCentrality(Graph<V,E> g, int maxIterations, double tolerance)	Create and execute an instance of EigenvectorCentrality.

Method Summary

Modifier and Type	Method	Description
Map<V,Double>	getScores()	Get a map with the scores of all vertices
Double	getVertexScore(V v)	Get a vertex score

Methods inherited from class java.lang.Object

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

Field Detail

MAX_ITERATIONS_DEFAULT

public static final int MAX_ITERATIONS_DEFAULT

Default number of maximum iterations.

See Also:

Constant Field Values

TOLERANCE_DEFAULT

public static final double TOLERANCE_DEFAULT

Default value for the tolerance. The calculation will stop if the ℓ₂ norm of the difference of centrality values between iterations changes less than this value.

See Also:

Constant Field Values

Constructor Detail

EigenvectorCentrality

public EigenvectorCentrality(Graph<V,E> g)

Create and execute an instance of EigenvectorCentrality

Parameters:

g - the input graph

EigenvectorCentrality

public EigenvectorCentrality(Graph<V,E> g,
                             int maxIterations)

Create and execute an instance of EigenvectorCentrality

Parameters:

g - the input graph

maxIterations - the maximum number of iterations to perform

EigenvectorCentrality

public EigenvectorCentrality(Graph<V,E> g,
                             int maxIterations,
                             double tolerance)

Create and execute an instance of EigenvectorCentrality.

Parameters:

g - the input graph

maxIterations - the maximum number of iterations to perform

tolerance - calculation will stop if the ℓ₂ norm of the difference of centrality values between iterations changes less than this value

Method Detail

getScores

public Map<V,Double> getScores()

Get a map with the scores of all vertices

Specified by:

getScores in interface VertexScoringAlgorithm<V,E>

Returns:

a map with all scores

getVertexScore

public Double getVertexScore(V v)

Get a vertex score

Specified by:

getVertexScore in interface VertexScoringAlgorithm<V,E>

Parameters:

v - the vertex

Returns:

the score