Package org.jgrapht.alg.scoring

Class HarmonicCentrality<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    VertexScoringAlgorithm<V,​Double>
    public final class HarmonicCentrality<V,​E>
extends ClosenessCentrality<V,​E>
    Harmonic centrality.

    The harmonic centrality of a vertex $x$ is defined as $H(x)=\sum_{y \neq x} 1/d(x,y)$, where $d(x,y)$ is the shortest path distance from $x$ to $y$. In case a distance $d(x,y)=\infinity$, then $1/d(x,y)=0$. When normalization is used the score is divided by $n-1$ where $n$ is the total number of vertices in the graph. For details see the following papers:

    • Yannick Rochat. Closeness centrality extended to unconnected graphs: The harmonic centrality index. Applications of Social Network Analysis, 2009.
    • Newman, Mark. 2003. The Structure and Function of Complex Networks. SIAM Review, 45(mars), 167–256.
    and the wikipedia article.

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

    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.

    Author:
    Dimitrios Michail

    • Constructor Detail

      • HarmonicCentrality

        public HarmonicCentrality​(Graph<V,​E> graph)
        Construct a new instance. By default the centrality is normalized and computed using outgoing paths.
        Parameters:
        graph - the input graph

      • HarmonicCentrality

        public HarmonicCentrality​(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 dividing the closeness by $n-1$, where $n$ is the number of vertices of the graph