Class 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
    • Method Summary

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

      • getScores

        public java.util.Map<V,​java.lang.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 java.lang.Double getVertexScore​(V v)
        Get a vertex score
        Specified by:
        getVertexScore in interface VertexScoringAlgorithm<V,​E>
        Parameters:
        v - the vertex
        Returns:
        the score