### comparison env/lib/python3.9/site-packages/networkx/algorithms/assortativity/connectivity.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 from collections import defaultdict
2
3 __all__ = ["average_degree_connectivity", "k_nearest_neighbors"]
4
5
6 def average_degree_connectivity(
7 G, source="in+out", target="in+out", nodes=None, weight=None
8 ):
9 r"""Compute the average degree connectivity of graph.
10
11 The average degree connectivity is the average nearest neighbor degree of
12 nodes with degree k. For weighted graphs, an analogous measure can
13 be computed using the weighted average neighbors degree defined in
14 _, for a node i, as
15
16 .. math::
17
18 k_{nn,i}^{w} = \frac{1}{s_i} \sum_{j \in N(i)} w_{ij} k_j
19
20 where s_i is the weighted degree of node i,
21 w_{ij} is the weight of the edge that links i and j,
22 and N(i) are the neighbors of node i.
23
24 Parameters
25 ----------
26 G : NetworkX graph
27
28 source : "in"|"out"|"in+out" (default:"in+out")
29 Directed graphs only. Use "in"- or "out"-degree for source node.
30
31 target : "in"|"out"|"in+out" (default:"in+out"
32 Directed graphs only. Use "in"- or "out"-degree for target node.
33
34 nodes : list or iterable (optional)
35 Compute neighbor connectivity for these nodes. The default is all
36 nodes.
37
38 weight : string or None, optional (default=None)
39 The edge attribute that holds the numerical value used as a weight.
40 If None, then each edge has weight 1.
41
42 Returns
43 -------
44 d : dict
45 A dictionary keyed by degree k with the value of average connectivity.
46
47 Raises
48 ------
49 ValueError
50 If either source or target are not one of 'in',
51 'out', or 'in+out'.
52
53 Examples
54 --------
55 >>> G = nx.path_graph(4)
56 >>> G.edges[1, 2]["weight"] = 3
57 >>> nx.k_nearest_neighbors(G)
58 {1: 2.0, 2: 1.5}
59 >>> nx.k_nearest_neighbors(G, weight="weight")
60 {1: 2.0, 2: 1.75}
61
63 --------
64 neighbors_average_degree
65
66 Notes
67 -----
68 This algorithm is sometimes called "k nearest neighbors" and is also
69 available as k_nearest_neighbors.
70
71 References
72 ----------
73 ..  A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani,
74 "The architecture of complex weighted networks".
75 PNAS 101 (11): 3747–3752 (2004).
76 """
77 # First, determine the type of neighbors and the type of degree to use.
78 if G.is_directed():
79 if source not in ("in", "out", "in+out"):
80 raise ValueError('source must be one of "in", "out", or "in+out"')
81 if target not in ("in", "out", "in+out"):
82 raise ValueError('target must be one of "in", "out", or "in+out"')
83 direction = {"out": G.out_degree, "in": G.in_degree, "in+out": G.degree}
84 neighbor_funcs = {
85 "out": G.successors,
86 "in": G.predecessors,
87 "in+out": G.neighbors,
88 }
89 source_degree = direction[source]
90 target_degree = direction[target]
91 neighbors = neighbor_funcs[source]
92 # reverse indicates whether to look at the in-edge when
93 # computing the weight of an edge.
94 reverse = source == "in"
95 else:
96 source_degree = G.degree
97 target_degree = G.degree
98 neighbors = G.neighbors
99 reverse = False
100 dsum = defaultdict(int)
101 dnorm = defaultdict(int)
102 # Check if source_nodes is actually a single node in the graph.
103 source_nodes = source_degree(nodes)
104 if nodes in G:
105 source_nodes = [(nodes, source_degree(nodes))]
106 for n, k in source_nodes:
107 nbrdeg = target_degree(neighbors(n))
108 if weight is None:
109 s = sum(d for n, d in nbrdeg)
110 else: # weight nbr degree by weight of (n,nbr) edge
111 if reverse:
112 s = sum(G[nbr][n].get(weight, 1) * d for nbr, d in nbrdeg)
113 else:
114 s = sum(G[n][nbr].get(weight, 1) * d for nbr, d in nbrdeg)
115 dnorm[k] += source_degree(n, weight=weight)
116 dsum[k] += s
117
118 # normalize
119 dc = {}
120 for k, avg in dsum.items():
121 dc[k] = avg
122 norm = dnorm[k]
123 if avg > 0 and norm > 0:
124 dc[k] /= norm
125 return dc
126
127
128 k_nearest_neighbors = average_degree_connectivity