- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
VertexScoringAlgorithm<V,
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
Modifier and TypeFieldDescriptionstatic final int
Default number of maximum iterations.static final double
Default value for the tolerance. -
Constructor Summary
ConstructorDescriptionEigenvectorCentrality
(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
-
Field Details
-
MAX_ITERATIONS_DEFAULT
public static final int MAX_ITERATIONS_DEFAULTDefault number of maximum iterations.- See Also:
-
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:
-
-
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
-