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 final 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 ℓ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 Details

    • MAX_ITERATIONS_DEFAULT

      public static final int MAX_ITERATIONS_DEFAULT
      Default number of maximum iterations.
      See Also:
    • TOLERANCE_DEFAULT

      public static final double TOLERANCE_DEFAULT
      Default 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

      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 ℓ2 norm of the difference of centrality values between iterations changes less than this value
  • Method Details