/usr/lib/python3/dist-packages/networkx/algorithms/centrality/dispersion.py is in python3-networkx 1.11-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | from itertools import combinations
__author__ = "\n".join(['Ben Edwards (bedwards@cs.unm.edu)',
'Huston Hedinger (h@graphalchemist.com)',
'Dan Schult (dschult@colgate.edu)'])
__all__ = ['dispersion']
def dispersion(G, u=None, v=None, normalized=True, alpha=1.0, b=0.0, c=0.0):
r"""Calculate dispersion between `u` and `v` in `G`.
A link between two actors (`u` and `v`) has a high dispersion when their
mutual ties (`s` and `t`) are not well connected with each other.
Parameters
----------
G : graph
A NetworkX graph.
u : node, optional
The source for the dispersion score (e.g. ego node of the network).
v : node, optional
The target of the dispersion score if specified.
normalized : bool
If True (default) normalize by the embededness of the nodes (u and v).
Returns
-------
nodes : dictionary
If u (v) is specified, returns a dictionary of nodes with dispersion
score for all "target" ("source") nodes. If neither u nor v is
specified, returns a dictionary of dictionaries for all nodes 'u' in the
graph with a dispersion score for each node 'v'.
Notes
-----
This implementation follows Lars Backstrom and Jon Kleinberg [1]_. Typical
usage would be to run dispersion on the ego network :math:`G_u` if `u` were
specified. Running :func:`dispersion` with neither `u` nor `v` specified
can take some time to complete.
References
----------
.. [1] Romantic Partnerships and the Dispersion of Social Ties:
A Network Analysis of Relationship Status on Facebook.
Lars Backstrom, Jon Kleinberg.
http://arxiv.org/pdf/1310.6753v1.pdf
"""
def _dispersion(G_u, u, v):
"""dispersion for all nodes 'v' in a ego network G_u of node 'u'"""
u_nbrs = set(G_u[u])
ST = set(n for n in G_u[v] if n in u_nbrs)
set_uv=set([u,v])
#all possible ties of connections that u and b share
possib = combinations(ST, 2)
total = 0
for (s,t) in possib:
#neighbors of s that are in G_u, not including u and v
nbrs_s = u_nbrs.intersection(G_u[s]) - set_uv
#s and t are not directly connected
if not t in nbrs_s:
#s and t do not share a connection
if nbrs_s.isdisjoint(G_u[t]):
#tick for disp(u, v)
total += 1
#neighbors that u and v share
embededness = len(ST)
if normalized:
if embededness + c != 0:
norm_disp = ((total + b)**alpha)/(embededness + c)
else:
norm_disp = (total+b)**alpha
dispersion = norm_disp
else:
dispersion = total
return dispersion
if u is None:
# v and u are not specified
if v is None:
results = dict((n,{}) for n in G)
for u in G:
for v in G[u]:
results[u][v] = _dispersion(G, u, v)
# u is not specified, but v is
else:
results = dict.fromkeys(G[v], {})
for u in G[v]:
results[u] = _dispersion(G, v, u)
else:
# u is specified with no target v
if v is None:
results = dict.fromkeys(G[u], {})
for v in G[u]:
results[v] = _dispersion(G, u, v)
# both u and v are specified
else:
results = _dispersion(G, u, v)
return results
|