- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
VertexScoringAlgorithm<V,java.lang.Double>
public final class EigenvectorCentrality<V,E> extends java.lang.Object implements VertexScoringAlgorithm<V,java.lang.Double>
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 ℓ2 norm of the difference between the current estimate and the next one drops below a given threshold). Correspondingly, the result will be ℓ2-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 EigenvectorCentralityEigenvectorCentrality(Graph<V,E> g, int maxIterations)
Create and execute an instance of EigenvectorCentralityEigenvectorCentrality(Graph<V,E> g, int maxIterations, double tolerance)
Create and execute an instance of EigenvectorCentrality. -
Method Summary
Modifier and Type Method Description java.util.Map<V,java.lang.Double>
getScores()
Get a map with the scores of all verticesjava.lang.Double
getVertexScore(V v)
Get a vertex score
-
Field Details
-
MAX_ITERATIONS_DEFAULT
public static final int MAX_ITERATIONS_DEFAULTDefault number of maximum iterations.- See Also:
- Constant Field Values
-
TOLERANCE_DEFAULT
public static final double TOLERANCE_DEFAULTDefault value for the tolerance. The calculation will stop if the ℓ2 norm of the difference of centrality values between iterations changes less than this value.- See Also:
- Constant Field Values
-
-
Constructor Details
-
EigenvectorCentrality
Create and execute an instance of EigenvectorCentrality- Parameters:
g
- the input graph
-
EigenvectorCentrality
Create and execute an instance of EigenvectorCentrality- Parameters:
g
- the input graphmaxIterations
- the maximum number of iterations to perform
-
EigenvectorCentrality
Create and execute an instance of EigenvectorCentrality.- Parameters:
g
- the input graphmaxIterations
- the maximum number of iterations to performtolerance
- calculation will stop if the ℓ2 norm of the difference of centrality values between iterations changes less than this value
-
-
Method Details
-
getScores
Get a map with the scores of all vertices- Specified by:
getScores
in interfaceVertexScoringAlgorithm<V,E>
- Returns:
- a map with all scores
-
getVertexScore
Get a vertex score- Specified by:
getVertexScore
in interfaceVertexScoringAlgorithm<V,E>
- Parameters:
v
- the vertex- Returns:
- the score
-