Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/dispersion.py: 13%

1from itertools import combinations 

2 

3import networkx as nx 

4 

5__all__ = ["dispersion"] 

6 

7 

8@nx._dispatch 

9def dispersion(G, u=None, v=None, normalized=True, alpha=1.0, b=0.0, c=0.0): 

10 r"""Calculate dispersion between `u` and `v` in `G`. 

11 

12 A link between two actors (`u` and `v`) has a high dispersion when their 

13 mutual ties (`s` and `t`) are not well connected with each other. 

14 

15 Parameters 

16 ---------- 

17 G : graph 

18 A NetworkX graph. 

19 u : node, optional 

20 The source for the dispersion score (e.g. ego node of the network). 

21 v : node, optional 

22 The target of the dispersion score if specified. 

23 normalized : bool 

24 If True (default) normalize by the embeddedness of the nodes (u and v). 

25 alpha, b, c : float 

26 Parameters for the normalization procedure. When `normalized` is True, 

27 the dispersion value is normalized by:: 

28 

29 result = ((dispersion + b) ** alpha) / (embeddedness + c) 

30 

31 as long as the denominator is nonzero. 

32 

33 Returns 

34 ------- 

35 nodes : dictionary 

36 If u (v) is specified, returns a dictionary of nodes with dispersion 

37 score for all "target" ("source") nodes. If neither u nor v is 

38 specified, returns a dictionary of dictionaries for all nodes 'u' in the 

39 graph with a dispersion score for each node 'v'. 

40 

41 Notes 

42 ----- 

43 This implementation follows Lars Backstrom and Jon Kleinberg [1]_. Typical 

44 usage would be to run dispersion on the ego network $G_u$ if $u$ were 

45 specified. Running :func:`dispersion` with neither $u$ nor $v$ specified 

46 can take some time to complete. 

47 

48 References 

49 ---------- 

50 .. [1] Romantic Partnerships and the Dispersion of Social Ties: 

51 A Network Analysis of Relationship Status on Facebook. 

52 Lars Backstrom, Jon Kleinberg. 

53 https://arxiv.org/pdf/1310.6753v1.pdf 

54 

55 """ 

56 

57 def _dispersion(G_u, u, v): 

58 """dispersion for all nodes 'v' in a ego network G_u of node 'u'""" 

59 u_nbrs = set(G_u[u]) 

60 ST = {n for n in G_u[v] if n in u_nbrs} 

61 set_uv = {u, v} 

62 # all possible ties of connections that u and b share 

63 possib = combinations(ST, 2) 

64 total = 0 

65 for s, t in possib: 

66 # neighbors of s that are in G_u, not including u and v 

67 nbrs_s = u_nbrs.intersection(G_u[s]) - set_uv 

68 # s and t are not directly connected 

69 if t not in nbrs_s: 

70 # s and t do not share a connection 

71 if nbrs_s.isdisjoint(G_u[t]): 

72 # tick for disp(u, v) 

73 total += 1 

74 # neighbors that u and v share 

75 embeddedness = len(ST) 

76 

77 dispersion_val = total 

78 if normalized: 

79 dispersion_val = (total + b) ** alpha 

80 if embeddedness + c != 0: 

81 dispersion_val /= embeddedness + c 

82 

83 return dispersion_val 

84 

85 if u is None: 

86 # v and u are not specified 

87 if v is None: 

88 results = {n: {} for n in G} 

89 for u in G: 

90 for v in G[u]: 

91 results[u][v] = _dispersion(G, u, v) 

92 # u is not specified, but v is 

93 else: 

94 results = dict.fromkeys(G[v], {}) 

95 for u in G[v]: 

96 results[u] = _dispersion(G, v, u) 

97 else: 

98 # u is specified with no target v 

99 if v is None: 

100 results = dict.fromkeys(G[u], {}) 

101 for v in G[u]: 

102 results[v] = _dispersion(G, u, v) 

103 # both u and v are specified 

104 else: 

105 results = _dispersion(G, u, v) 

106 

107 return results