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 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 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, ToDoubleFunction<V> exogenousFactorFunction)	Create and execute an instance of KatzCentrality.
KatzCentrality(Graph<V,E> g, double dampingFactor, ToDoubleFunction<V> exogenousFactorFunction, int maxIterations)	Create and execute an instance of KatzCentrality.
KatzCentrality(Graph<V,E> g, double dampingFactor, ToDoubleFunction<V> exogenousFactorFunction, int maxIterations, double tolerance)	Create and execute an instance of KatzCentrality.

Method Summary

Modifier and Type	Method	Description
static <V> ToDoubleFunction<V>	exogenousFactorDefaultFunction()	Exogenous factor default function (the constant function returning 1).
Map<V,Double>	getScores()	Get a map with the scores of all vertices
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,
                      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 Detail

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