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,​java.lang.Double>

public final class EigenvectorCentrality<V,​E>
extends java.lang.Object
implements VertexScoringAlgorithm<V,​java.lang.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 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
    java.util.Map<V,​java.lang.Double> getScores()
    Get a map with the scores of all vertices
    java.lang.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 Details

  • 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