Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/assortativity/connectivity.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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 [1]_, 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 | |
62 See also | |
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 .. [1] 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 |