Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/current_flow_closeness.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 """Current-flow closeness centrality measures.""" | |
2 import networkx as nx | |
3 | |
4 from networkx.utils import not_implemented_for, reverse_cuthill_mckee_ordering | |
5 from networkx.algorithms.centrality.flow_matrix import ( | |
6 CGInverseLaplacian, | |
7 FullInverseLaplacian, | |
8 laplacian_sparse_matrix, | |
9 SuperLUInverseLaplacian, | |
10 ) | |
11 | |
12 __all__ = ["current_flow_closeness_centrality", "information_centrality"] | |
13 | |
14 | |
15 @not_implemented_for("directed") | |
16 def current_flow_closeness_centrality(G, weight=None, dtype=float, solver="lu"): | |
17 """Compute current-flow closeness centrality for nodes. | |
18 | |
19 Current-flow closeness centrality is variant of closeness | |
20 centrality based on effective resistance between nodes in | |
21 a network. This metric is also known as information centrality. | |
22 | |
23 Parameters | |
24 ---------- | |
25 G : graph | |
26 A NetworkX graph. | |
27 | |
28 weight : None or string, optional (default=None) | |
29 If None, all edge weights are considered equal. | |
30 Otherwise holds the name of the edge attribute used as weight. | |
31 | |
32 dtype: data type (default=float) | |
33 Default data type for internal matrices. | |
34 Set to np.float32 for lower memory consumption. | |
35 | |
36 solver: string (default='lu') | |
37 Type of linear solver to use for computing the flow matrix. | |
38 Options are "full" (uses most memory), "lu" (recommended), and | |
39 "cg" (uses least memory). | |
40 | |
41 Returns | |
42 ------- | |
43 nodes : dictionary | |
44 Dictionary of nodes with current flow closeness centrality as the value. | |
45 | |
46 See Also | |
47 -------- | |
48 closeness_centrality | |
49 | |
50 Notes | |
51 ----- | |
52 The algorithm is from Brandes [1]_. | |
53 | |
54 See also [2]_ for the original definition of information centrality. | |
55 | |
56 References | |
57 ---------- | |
58 .. [1] Ulrik Brandes and Daniel Fleischer, | |
59 Centrality Measures Based on Current Flow. | |
60 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05). | |
61 LNCS 3404, pp. 533-544. Springer-Verlag, 2005. | |
62 http://algo.uni-konstanz.de/publications/bf-cmbcf-05.pdf | |
63 | |
64 .. [2] Karen Stephenson and Marvin Zelen: | |
65 Rethinking centrality: Methods and examples. | |
66 Social Networks 11(1):1-37, 1989. | |
67 https://doi.org/10.1016/0378-8733(89)90016-6 | |
68 """ | |
69 if not nx.is_connected(G): | |
70 raise nx.NetworkXError("Graph not connected.") | |
71 solvername = { | |
72 "full": FullInverseLaplacian, | |
73 "lu": SuperLUInverseLaplacian, | |
74 "cg": CGInverseLaplacian, | |
75 } | |
76 n = G.number_of_nodes() | |
77 ordering = list(reverse_cuthill_mckee_ordering(G)) | |
78 # make a copy with integer labels according to rcm ordering | |
79 # this could be done without a copy if we really wanted to | |
80 H = nx.relabel_nodes(G, dict(zip(ordering, range(n)))) | |
81 betweenness = dict.fromkeys(H, 0.0) # b[v]=0 for v in H | |
82 n = H.number_of_nodes() | |
83 L = laplacian_sparse_matrix( | |
84 H, nodelist=range(n), weight=weight, dtype=dtype, format="csc" | |
85 ) | |
86 C2 = solvername[solver](L, width=1, dtype=dtype) # initialize solver | |
87 for v in H: | |
88 col = C2.get_row(v) | |
89 for w in H: | |
90 betweenness[v] += col[v] - 2 * col[w] | |
91 betweenness[w] += col[v] | |
92 for v in H: | |
93 betweenness[v] = 1.0 / (betweenness[v]) | |
94 return {ordering[k]: float(v) for k, v in betweenness.items()} | |
95 | |
96 | |
97 information_centrality = current_flow_closeness_centrality |