Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.51 KB)

1
from itertools import combinations
2

    
3
__author__ = "\n".join(['Ben Edwards (bedwards@cs.unm.edu)',
4
                        'Huston Hedinger (hstn@hdngr.com)',
5
                        'Dan Schult (dschult@colgate.edu)'])
6

    
7
__all__ = ['dispersion']
8

    
9

    
10
def dispersion(G, u=None, v=None, normalized=True, alpha=1.0, b=0.0, c=0.0):
11
    r"""Calculate dispersion between `u` and `v` in `G`.
12

13
    A link between two actors (`u` and `v`) has a high dispersion when their
14
    mutual ties (`s` and `t`) are not well connected with each other.
15

16
    Parameters
17
    ----------
18
    G : graph
19
        A NetworkX graph.
20
    u : node, optional
21
        The source for the dispersion score (e.g. ego node of the network).
22
    v : node, optional
23
        The target of the dispersion score if specified.
24
    normalized : bool
25
        If True (default) normalize by the embededness of the nodes (u and v).
26

27
    Returns
28
    -------
29
    nodes : dictionary
30
        If u (v) is specified, returns a dictionary of nodes with dispersion
31
        score for all "target" ("source") nodes. If neither u nor v is
32
        specified, returns a dictionary of dictionaries for all nodes 'u' in the
33
        graph with a dispersion score for each node 'v'.
34

35
    Notes
36
    -----
37
    This implementation follows Lars Backstrom and Jon Kleinberg [1]_. Typical
38
    usage would be to run dispersion on the ego network $G_u$ if $u$ were
39
    specified.  Running :func:`dispersion` with neither $u$ nor $v$ specified
40
    can take some time to complete.
41

42
    References
43
    ----------
44
    .. [1] Romantic Partnerships and the Dispersion of Social Ties:
45
        A Network Analysis of Relationship Status on Facebook.
46
        Lars Backstrom, Jon Kleinberg.
47
        https://arxiv.org/pdf/1310.6753v1.pdf
48

49
    """
50

    
51
    def _dispersion(G_u, u, v):
52
        """dispersion for all nodes 'v' in a ego network G_u of node 'u'"""
53
        u_nbrs = set(G_u[u])
54
        ST = set(n for n in G_u[v] if n in u_nbrs)
55
        set_uv = set([u, v])
56
        # all possible ties of connections that u and b share
57
        possib = combinations(ST, 2)
58
        total = 0
59
        for (s, t) in possib:
60
            # neighbors of s that are in G_u, not including u and v
61
            nbrs_s = u_nbrs.intersection(G_u[s]) - set_uv
62
            # s and t are not directly connected
63
            if t not in nbrs_s:
64
                # s and t do not share a connection
65
                if nbrs_s.isdisjoint(G_u[t]):
66
                    # tick for disp(u, v)
67
                    total += 1
68
        # neighbors that u and v share
69
        embededness = len(ST)
70

    
71
        if normalized:
72
            if embededness + c != 0:
73
                norm_disp = ((total + b)**alpha) / (embededness + c)
74
            else:
75
                norm_disp = (total + b)**alpha
76
            dispersion = norm_disp
77

    
78
        else:
79
            dispersion = total
80

    
81
        return dispersion
82

    
83
    if u is None:
84
        # v and u are not specified
85
        if v is None:
86
            results = dict((n, {}) for n in G)
87
            for u in G:
88
                for v in G[u]:
89
                    results[u][v] = _dispersion(G, u, v)
90
        # u is not specified, but v is
91
        else:
92
            results = dict.fromkeys(G[v], {})
93
            for u in G[v]:
94
                results[u] = _dispersion(G, v, u)
95
    else:
96
        # u is specified with no target v
97
        if v is None:
98
            results = dict.fromkeys(G[u], {})
99
            for v in G[u]:
100
                results[v] = _dispersion(G, u, v)
101
        # both u and v are specified
102
        else:
103
            results = _dispersion(G, u, v)
104

    
105
    return results