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,​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

  • Field Summary

    Fields 
    Modifier and Type Field Description
    static double DAMPING_FACTOR_DEFAULT
    Damping factor default value.
    static int MAX_ITERATIONS_DEFAULT
    Default number of maximum iterations.
    static double TOLERANCE_DEFAULT
    Default value for the tolerance.

  • 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

    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 Details

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

    • 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