Module org.jgrapht.core
Package org.jgrapht.alg.scoring

Class KatzCentrality<V,E>

java.lang.Object
org.jgrapht.alg.scoring.KatzCentrality<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
VertexScoringAlgorithm<V,Double>
public final class KatzCentrality<V,E> extends Object implements VertexScoringAlgorithm<V,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

  • 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 difference of Katz centrality values between iterations change less than this value.
      See Also:

    • DAMPING_FACTOR_DEFAULT

      public static final double DAMPING_FACTOR_DEFAULT
      Damping factor default value.
      See Also:

  • Constructor Details

    • 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, 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, 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, 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 Details

    • exogenousFactorDefaultFunction

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