org.jgrapht.alg.scoring

Class ClosenessCentrality<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexScoringAlgorithm<V,Double>

Direct Known Subclasses:

HarmonicCentrality

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

Closeness centrality.

Computes the closeness centrality of each vertex of a graph. The closeness of a vertex $x$ is defined as the reciprocal of the farness, that is $H(x)= 1 / \sum_{y \neq x} d(x,y)$, where $d(x,y)$ is the shortest path distance from $x$ to $y$. When normalization is used, the score is multiplied by $n-1$ where $n$ is the total number of vertices in the graph. For more details see wikipedia and

• Alex Bavelas. Communication patterns in task-oriented groups. J. Acoust. Soc. Am, 22(6):725–730, 1950.

This implementation computes by default the closeness centrality using outgoing paths and normalizes the scores. This behavior can be adjusted by the constructor arguments.

When the graph is disconnected, the closeness centrality score equals $0$ for all vertices. In the case of weakly connected digraphs, the closeness centrality of several vertices might be 0. See HarmonicCentrality for a different approach in case of disconnected graphs.

Shortest paths are computed either by using Dijkstra's algorithm or Floyd-Warshall depending on whether the graph has edges with negative edge weights. Thus, the running time is either $O(n (m +n \log n))$ or $O(n^3)$ respectively, where $n$ is the number of vertices and $m$ the number of edges of the graph.

Since:

January 2017

Author:

Dimitrios Michail

Field Summary

Fields

Modifier and Type	Field and Description
protected Graph<V,E>	graph Underlying graph
protected boolean	incoming Whether to use incoming or outgoing paths
protected boolean	normalize Whether to normalize scores
protected Map<V,Double>	scores The actual scores

Constructor Summary

Constructors

Constructor and Description
ClosenessCentrality(Graph<V,E> graph) Construct a new instance.
ClosenessCentrality(Graph<V,E> graph, boolean incoming, boolean normalize) Construct a new instance.

Method Summary

Modifier and Type	Method and Description
protected void	compute() Compute the centrality index
Map<V,Double>	getScores() Get a map with the scores of all vertices
protected ShortestPathAlgorithm<V,E>	getShortestPathAlgorithm() Get the shortest path algorithm for the paths computation.
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

graph

protected final Graph<V,E> graph

Underlying graph

incoming

protected final boolean incoming

Whether to use incoming or outgoing paths

normalize

protected final boolean normalize

Whether to normalize scores

scores

protected Map<V,Double> scores

The actual scores

Constructor Detail

ClosenessCentrality

public ClosenessCentrality(Graph<V,E> graph)

Construct a new instance. By default the centrality is normalized and computed using outgoing paths.

Parameters:

graph - the input graph

ClosenessCentrality

public ClosenessCentrality(Graph<V,E> graph,
                           boolean incoming,
                           boolean normalize)

Construct a new instance.

Parameters:

graph - the input graph

incoming - if true incoming paths are used, otherwise outgoing paths

normalize - whether to normalize by multiplying the closeness by n-1, where n is the number of vertices of the graph

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

getShortestPathAlgorithm

protected ShortestPathAlgorithm<V,E> getShortestPathAlgorithm()

Get the shortest path algorithm for the paths computation.

Returns:

the shortest path algorithm

compute

protected void compute()

Compute the centrality index