 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
VertexScoringAlgorithm<V,
Double>
 Direct Known Subclasses:
HarmonicCentrality
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
 Alex Bavelas. Communication patterns in taskoriented 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 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.
 Author:
 Dimitrios Michail

Field Summary

Constructor Summary
ConstructorDescriptionClosenessCentrality
(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 TypeMethodDescriptionprotected void
compute()
Compute the centrality indexGet a map with the scores of all verticesprotected ShortestPathAlgorithm<V,
E> Get the shortest path algorithm for the paths computation.getVertexScore
(V v) Get a vertex score

Field Details

graph
Underlying graph 
incoming
protected final boolean incomingWhether to use incoming or outgoing paths 
normalize
protected final boolean normalizeWhether to normalize scores 
scores
The actual scores


Constructor Details

ClosenessCentrality
Construct a new instance. By default the centrality is normalized and computed using outgoing paths. Parameters:
graph
 the input graph

ClosenessCentrality
Construct a new instance. Parameters:
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 graph


Method Details

getScores
Get a map with the scores of all vertices Specified by:
getScores
in interfaceVertexScoringAlgorithm<V,
E>  Returns:
 a map with all scores

getVertexScore
Get a vertex score Specified by:
getVertexScore
in interfaceVertexScoringAlgorithm<V,
E>  Parameters:
v
 the vertex Returns:
 the score

getShortestPathAlgorithm
Get the shortest path algorithm for the paths computation. Returns:
 the shortest path algorithm

compute
protected void compute()Compute the centrality index
