Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / centrality / harmonic.py @ 5cef0f13

History | View | Annotate | Download (2 KB)

1
#    Copyright (C) 2015 by
2
#    Alessandro Luongo
3
#    BSD license.
4
#
5
# Authors:
6
#    Alessandro Luongo <alessandro.luongo@studenti.unimi.it>
7
#
8
"""Functions for computing the harmonic centrality of a graph."""
9
from __future__ import division
10
from functools import partial
11

    
12
import networkx as nx
13

    
14
__all__ = ['harmonic_centrality']
15

    
16

    
17
def harmonic_centrality(G, nbunch=None, distance=None):
18
    r"""Compute harmonic centrality for nodes.
19

20
    Harmonic centrality [1]_ of a node `u` is the sum of the reciprocal
21
    of the shortest path distances from all other nodes to `u`
22

23
    .. math::
24

25
        C(u) = \sum_{v \neq u} \frac{1}{d(v, u)}
26

27
    where `d(v, u)` is the shortest-path distance between `v` and `u`.
28

29
    Notice that higher values indicate higher centrality.
30

31
    Parameters
32
    ----------
33
    G : graph
34
      A NetworkX graph
35

36
    nbunch : container
37
      Container of nodes. If provided harmonic centrality will be computed
38
      only over the nodes in nbunch.
39

40
    distance : edge attribute key, optional (default=None)
41
      Use the specified edge attribute as the edge distance in shortest
42
      path calculations.  If `None`, then each edge will have distance equal to 1.
43

44
    Returns
45
    -------
46
    nodes : dictionary
47
      Dictionary of nodes with harmonic centrality as the value.
48

49
    See Also
50
    --------
51
    betweenness_centrality, load_centrality, eigenvector_centrality,
52
    degree_centrality, closeness_centrality
53

54
    Notes
55
    -----
56
    If the 'distance' keyword is set to an edge attribute key then the
57
    shortest-path length will be computed using Dijkstra's algorithm with
58
    that edge attribute as the edge weight.
59

60
    References
61
    ----------
62
    .. [1] Boldi, Paolo, and Sebastiano Vigna. "Axioms for centrality."
63
           Internet Mathematics 10.3-4 (2014): 222-262.
64
    """
65
    if G.is_directed():
66
        G = G.reverse()
67
    spl = partial(nx.shortest_path_length, G, weight=distance)
68
    return {u: sum(1 / d if d > 0 else 0 for v, d in spl(source=u).items())
69
            for u in G.nbunch_iter(nbunch)}