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

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