Class KatzCentrality<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 KatzCentrality<V,​E>
    extends java.lang.Object
    implements VertexScoringAlgorithm<V,​java.lang.Double>
    Katz centrality implementation.

    The wikipedia article contains a nice description of Katz centrality. Every path coming into a node contributes to its Katz centrality by αk, where α is the damping factor and k is the length of the path.

    This is a simple iterative implementation of Katz centrality which stops after a given number of iterations or if the Katz centrality values between two iterations do not change more than a predefined value. Each iteration increases the length of the paths contributing to the centrality value. Note that unless the damping factor is smaller than the reciprocal of the spectral radius of the adjacency matrix, the computation will not converge.

    This implementation makes it possible to provide an exogenous factor in the form of a ToDoubleFunction mapping each vertex to its exogenous score. Each path is then multiplied by the exogenous score of its starting vertex. The default exogenous function maps all vertices to one, as in standard Katz centrality.

    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:
    Dimitrios Michail, Pratik Tibrewal, Sebastiano Vigna
    • Constructor Summary

      Constructors 
      Constructor Description
      KatzCentrality​(Graph<V,​E> g)
      Create and execute an instance of KatzCentrality.
      KatzCentrality​(Graph<V,​E> g, double dampingFactor)
      Create and execute an instance of KatzCentrality.
      KatzCentrality​(Graph<V,​E> g, double dampingFactor, int maxIterations)
      Create and execute an instance of KatzCentrality.
      KatzCentrality​(Graph<V,​E> g, double dampingFactor, int maxIterations, double tolerance)
      Create and execute an instance of KatzCentrality.
      KatzCentrality​(Graph<V,​E> g, double dampingFactor, java.util.function.ToDoubleFunction<V> exogenousFactorFunction)
      Create and execute an instance of KatzCentrality.
      KatzCentrality​(Graph<V,​E> g, double dampingFactor, java.util.function.ToDoubleFunction<V> exogenousFactorFunction, int maxIterations)
      Create and execute an instance of KatzCentrality.
      KatzCentrality​(Graph<V,​E> g, double dampingFactor, java.util.function.ToDoubleFunction<V> exogenousFactorFunction, int maxIterations, double tolerance)
      Create and execute an instance of KatzCentrality.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static <V> java.util.function.ToDoubleFunction<V> exogenousFactorDefaultFunction()
      Exogenous factor default function (the constant function returning 1).
      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 difference of Katz centrality values between iterations change less than this value.
        See Also:
        Constant Field Values
      • DAMPING_FACTOR_DEFAULT

        public static final double DAMPING_FACTOR_DEFAULT
        Damping factor default value.
        See Also:
        Constant Field Values
    • Constructor Detail

      • KatzCentrality

        public KatzCentrality​(Graph<V,​E> g)
        Create and execute an instance of KatzCentrality.
        Parameters:
        g - the input graph
      • KatzCentrality

        public KatzCentrality​(Graph<V,​E> g,
                              double dampingFactor)
        Create and execute an instance of KatzCentrality.
        Parameters:
        g - the input graph
        dampingFactor - the damping factor
      • KatzCentrality

        public KatzCentrality​(Graph<V,​E> g,
                              double dampingFactor,
                              int maxIterations)
        Create and execute an instance of KatzCentrality.
        Parameters:
        g - the input graph
        dampingFactor - the damping factor
        maxIterations - the maximum number of iterations to perform
      • KatzCentrality

        public KatzCentrality​(Graph<V,​E> g,
                              double dampingFactor,
                              int maxIterations,
                              double tolerance)
        Create and execute an instance of KatzCentrality.
        Parameters:
        g - the input graph
        dampingFactor - the damping factor
        maxIterations - the maximum number of iterations to perform
        tolerance - the calculation will stop if the difference of Katz centrality values between iterations change less than this value
      • KatzCentrality

        public KatzCentrality​(Graph<V,​E> g,
                              double dampingFactor,
                              java.util.function.ToDoubleFunction<V> exogenousFactorFunction)
        Create and execute an instance of KatzCentrality.
        Parameters:
        g - the input graph
        dampingFactor - the damping factor
        exogenousFactorFunction - a provider of exogenous factor per vertex
      • KatzCentrality

        public KatzCentrality​(Graph<V,​E> g,
                              double dampingFactor,
                              java.util.function.ToDoubleFunction<V> exogenousFactorFunction,
                              int maxIterations)
        Create and execute an instance of KatzCentrality.
        Parameters:
        g - the input graph
        dampingFactor - the damping factor
        exogenousFactorFunction - a provider of exogenous factor per vertex
        maxIterations - the maximum number of iterations to perform
      • KatzCentrality

        public KatzCentrality​(Graph<V,​E> g,
                              double dampingFactor,
                              java.util.function.ToDoubleFunction<V> exogenousFactorFunction,
                              int maxIterations,
                              double tolerance)
        Create and execute an instance of KatzCentrality.
        Parameters:
        g - the input graph
        dampingFactor - the damping factor
        exogenousFactorFunction - a provider of exogenous factor per vertex
        maxIterations - the maximum number of iterations to perform
        tolerance - the calculation will stop if the difference of Katz centrality values between iterations change less than this value
    • Method Detail

      • exogenousFactorDefaultFunction

        public static final <V> java.util.function.ToDoubleFunction<V> exogenousFactorDefaultFunction()
        Exogenous factor default function (the constant function returning 1).
        Type Parameters:
        V - the input type of the function.
        Returns:
        always 1.
      • 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