org.jgrapht.alg.scoring

Class AlphaCentrality<V,E>

java.lang.Object

org.jgrapht.alg.scoring.AlphaCentrality<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexScoringAlgorithm<V,Double>

public final class AlphaCentrality<V,E>
extends Object
implements VertexScoringAlgorithm<V,Double>

AlphaCentrality implementation.

The wikipedia article contains a nice description of AlphaCentrality. You may also refer to this paper describing the implementation of the algorithm.

To implement EigenVector Centrality, call AlphaCentrality by passing the value of exogenous factor as zero. Further description of EigenVector Centrality can be found in wikipedia. To implement Katz Centrality, call AlphaCentrality by passing a non-zero scalar exogenous factor value. Further description of Katz Centrality can be found in wikipedia.

This is a simple iterative implementation of AlphaCentrality which stops after a given number of iterations or if the AlphaCentrality values between two iterations do not change more than a predefined value.

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

Field Summary

Fields

Modifier and Type	Field and Description
static double	DAMPING_FACTOR_DEFAULT Damping factor default value.
static double	EXOGENOUS_FACTOR_DEFAULT Exogenous 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 and Description
AlphaCentrality(Graph<V,E> g) Create and execute an instance of AlphaCentrality.
AlphaCentrality(Graph<V,E> g, double dampingFactor) Create and execute an instance of AlphaCentrality.
AlphaCentrality(Graph<V,E> g, double dampingFactor, double exogenousFactor) Create and execute an instance of AlphaCentrality.
AlphaCentrality(Graph<V,E> g, double dampingFactor, double exogenousFactor, int maxIterations) Create and execute an instance of AlphaCentrality.
AlphaCentrality(Graph<V,E> g, double dampingFactor, double exogenousFactor, int maxIterations, double tolerance) Create and execute an instance of AlphaCentrality.
AlphaCentrality(Graph<V,E> g, double dampingFactor, ToDoubleFunction<V> exogenousFactorFunction) Create and execute an instance of AlphaCentrality.
AlphaCentrality(Graph<V,E> g, double dampingFactor, ToDoubleFunction<V> exogenousFactorFunction, int maxIterations) Create and execute an instance of AlphaCentrality.
AlphaCentrality(Graph<V,E> g, double dampingFactor, ToDoubleFunction<V> exogenousFactorFunction, int maxIterations, double tolerance) Create and execute an instance of AlphaCentrality.

Method Summary

Modifier and Type	Method and Description
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 AlphaCentrality 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

EXOGENOUS_FACTOR_DEFAULT

public static final double EXOGENOUS_FACTOR_DEFAULT

Exogenous factor default value.

See Also:

Constant Field Values

Constructor Detail

AlphaCentrality

public AlphaCentrality(Graph<V,E> g)

Create and execute an instance of AlphaCentrality.

Parameters:

g - the input graph

AlphaCentrality

public AlphaCentrality(Graph<V,E> g,
                       double dampingFactor)

Create and execute an instance of AlphaCentrality.

Parameters:

g - the input graph

dampingFactor - the damping factor

AlphaCentrality

public AlphaCentrality(Graph<V,E> g,
                       double dampingFactor,
                       double exogenousFactor)

Create and execute an instance of AlphaCentrality.

Parameters:

g - the input graph

dampingFactor - the damping factor

exogenousFactor - the exogenous factor

AlphaCentrality

public AlphaCentrality(Graph<V,E> g,
                       double dampingFactor,
                       ToDoubleFunction<V> exogenousFactorFunction)

Create and execute an instance of AlphaCentrality.

Parameters:

g - the input graph

dampingFactor - the damping factor

exogenousFactorFunction - ToDoubleFunction a provider of exogenous factors per vertex

AlphaCentrality

public AlphaCentrality(Graph<V,E> g,
                       double dampingFactor,
                       double exogenousFactor,
                       int maxIterations)

Create and execute an instance of AlphaCentrality.

Parameters:

g - the input graph

dampingFactor - the damping factor

exogenousFactor - the exogenous factor

maxIterations - the maximum number of iterations to perform

AlphaCentrality

public AlphaCentrality(Graph<V,E> g,
                       double dampingFactor,
                       ToDoubleFunction<V> exogenousFactorFunction,
                       int maxIterations)

Create and execute an instance of AlphaCentrality.

Parameters:

g - the input graph

dampingFactor - the damping factor

exogenousFactorFunction - ToDoubleFunction a provider of exogenous factors per vertex

maxIterations - the maximum number of iterations to perform

AlphaCentrality

public AlphaCentrality(Graph<V,E> g,
                       double dampingFactor,
                       double exogenousFactor,
                       int maxIterations,
                       double tolerance)

Create and execute an instance of AlphaCentrality.

Parameters:

g - the input graph

dampingFactor - the damping factor

exogenousFactor - the exogenous factor

maxIterations - the maximum number of iterations to perform

tolerance - the calculation will stop if the difference of AlphaCentrality values between iterations change less than this value

AlphaCentrality

public AlphaCentrality(Graph<V,E> g,
                       double dampingFactor,
                       ToDoubleFunction<V> exogenousFactorFunction,
                       int maxIterations,
                       double tolerance)

Create and execute an instance of AlphaCentrality.

Parameters:

g - the input graph

dampingFactor - the damping factor

exogenousFactorFunction - ToDoubleFunction a provider of exogenous factors per vertex

maxIterations - the maximum number of iterations to perform

tolerance - the calculation will stop if the difference of AlphaCentrality values between iterations change less than this value

Method Detail

getScores

public Map<V,Double> getScores()

Get a map with the scores of all vertices

Specified by:

getScores in interface VertexScoringAlgorithm<V,Double>

Returns:

a map with all scores

getVertexScore

public Double getVertexScore(V v)

Get a vertex score

Specified by:

getVertexScore in interface VertexScoringAlgorithm<V,Double>

Parameters:

v - the vertex

Returns:

the score