V
 the graph vertex typeE
 the graph edge typepublic class ClosenessCentrality<V,E> extends Object implements VertexScoringAlgorithm<V,Double>
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 $n1$ where $n$ is the total number of vertices in the graph. For more details see wikipedia and
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 FloydWarshall 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.
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 and Description 

ClosenessCentrality(Graph<V,E> graph)
Construct a new instance.

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

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

protected final boolean incoming
protected final boolean normalize
public ClosenessCentrality(Graph<V,E> graph)
graph
 the input graphpublic ClosenessCentrality(Graph<V,E> graph, boolean incoming, boolean normalize)
graph
 the input graphincoming
 if true incoming paths are used, otherwise outgoing pathsnormalize
 whether to normalize by multiplying the closeness by n1, where n is the
number of vertices of the graphpublic Map<V,Double> getScores()
getScores
in interface VertexScoringAlgorithm<V,Double>
public Double getVertexScore(V v)
getVertexScore
in interface VertexScoringAlgorithm<V,Double>
v
 the vertexprotected ShortestPathAlgorithm<V,E> getShortestPathAlgorithm()
protected void compute()
Copyright © 2017. All rights reserved.