Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/percolation.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 """Percolation centrality measures.""" | |
2 | |
3 import networkx as nx | |
4 | |
5 from networkx.algorithms.centrality.betweenness import ( | |
6 _single_source_dijkstra_path_basic as dijkstra, | |
7 ) | |
8 from networkx.algorithms.centrality.betweenness import ( | |
9 _single_source_shortest_path_basic as shortest_path, | |
10 ) | |
11 | |
12 __all__ = ["percolation_centrality"] | |
13 | |
14 | |
15 def percolation_centrality(G, attribute="percolation", states=None, weight=None): | |
16 r"""Compute the percolation centrality for nodes. | |
17 | |
18 Percolation centrality of a node $v$, at a given time, is defined | |
19 as the proportion of ‘percolated paths’ that go through that node. | |
20 | |
21 This measure quantifies relative impact of nodes based on their | |
22 topological connectivity, as well as their percolation states. | |
23 | |
24 Percolation states of nodes are used to depict network percolation | |
25 scenarios (such as during infection transmission in a social network | |
26 of individuals, spreading of computer viruses on computer networks, or | |
27 transmission of disease over a network of towns) over time. In this | |
28 measure usually the percolation state is expressed as a decimal | |
29 between 0.0 and 1.0. | |
30 | |
31 When all nodes are in the same percolated state this measure is | |
32 equivalent to betweenness centrality. | |
33 | |
34 Parameters | |
35 ---------- | |
36 G : graph | |
37 A NetworkX graph. | |
38 | |
39 attribute : None or string, optional (default='percolation') | |
40 Name of the node attribute to use for percolation state, used | |
41 if `states` is None. | |
42 | |
43 states : None or dict, optional (default=None) | |
44 Specify percolation states for the nodes, nodes as keys states | |
45 as values. | |
46 | |
47 weight : None or string, optional (default=None) | |
48 If None, all edge weights are considered equal. | |
49 Otherwise holds the name of the edge attribute used as weight. | |
50 | |
51 Returns | |
52 ------- | |
53 nodes : dictionary | |
54 Dictionary of nodes with percolation centrality as the value. | |
55 | |
56 See Also | |
57 -------- | |
58 betweenness_centrality | |
59 | |
60 Notes | |
61 ----- | |
62 The algorithm is from Mahendra Piraveenan, Mikhail Prokopenko, and | |
63 Liaquat Hossain [1]_ | |
64 Pair dependecies are calculated and accumulated using [2]_ | |
65 | |
66 For weighted graphs the edge weights must be greater than zero. | |
67 Zero edge weights can produce an infinite number of equal length | |
68 paths between pairs of nodes. | |
69 | |
70 References | |
71 ---------- | |
72 .. [1] Mahendra Piraveenan, Mikhail Prokopenko, Liaquat Hossain | |
73 Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes | |
74 during Percolation in Networks | |
75 http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0053095 | |
76 .. [2] Ulrik Brandes: | |
77 A Faster Algorithm for Betweenness Centrality. | |
78 Journal of Mathematical Sociology 25(2):163-177, 2001. | |
79 http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf | |
80 """ | |
81 percolation = dict.fromkeys(G, 0.0) # b[v]=0 for v in G | |
82 | |
83 nodes = G | |
84 | |
85 if states is None: | |
86 states = nx.get_node_attributes(nodes, attribute) | |
87 | |
88 # sum of all percolation states | |
89 p_sigma_x_t = 0.0 | |
90 for v in states.values(): | |
91 p_sigma_x_t += v | |
92 | |
93 for s in nodes: | |
94 # single source shortest paths | |
95 if weight is None: # use BFS | |
96 S, P, sigma = shortest_path(G, s) | |
97 else: # use Dijkstra's algorithm | |
98 S, P, sigma = dijkstra(G, s, weight) | |
99 # accumulation | |
100 percolation = _accumulate_percolation( | |
101 percolation, G, S, P, sigma, s, states, p_sigma_x_t | |
102 ) | |
103 | |
104 n = len(G) | |
105 | |
106 for v in percolation: | |
107 percolation[v] *= 1 / (n - 2) | |
108 | |
109 return percolation | |
110 | |
111 | |
112 def _accumulate_percolation(percolation, G, S, P, sigma, s, states, p_sigma_x_t): | |
113 delta = dict.fromkeys(S, 0) | |
114 while S: | |
115 w = S.pop() | |
116 coeff = (1 + delta[w]) / sigma[w] | |
117 for v in P[w]: | |
118 delta[v] += sigma[v] * coeff | |
119 if w != s: | |
120 # percolation weight | |
121 pw_s_w = states[s] / (p_sigma_x_t - states[w]) | |
122 percolation[w] += delta[w] * pw_s_w | |
123 return percolation |