Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/current_flow_closeness.py: 30%

1"""Current-flow closeness centrality measures.""" 

2import networkx as nx 

3from networkx.algorithms.centrality.flow_matrix import ( 

4 CGInverseLaplacian, 

5 FullInverseLaplacian, 

6 SuperLUInverseLaplacian, 

7) 

8from networkx.utils import not_implemented_for, reverse_cuthill_mckee_ordering 

9 

10__all__ = ["current_flow_closeness_centrality", "information_centrality"] 

11 

12 

13@not_implemented_for("directed") 

14@nx._dispatch(edge_attrs="weight") 

15def current_flow_closeness_centrality(G, weight=None, dtype=float, solver="lu"): 

16 """Compute current-flow closeness centrality for nodes. 

17 

18 Current-flow closeness centrality is variant of closeness 

19 centrality based on effective resistance between nodes in 

20 a network. This metric is also known as information centrality. 

21 

22 Parameters 

23 ---------- 

24 G : graph 

25 A NetworkX graph. 

26 

27 weight : None or string, optional (default=None) 

28 If None, all edge weights are considered equal. 

29 Otherwise holds the name of the edge attribute used as weight. 

30 The weight reflects the capacity or the strength of the 

31 edge. 

32 

33 dtype: data type (default=float) 

34 Default data type for internal matrices. 

35 Set to np.float32 for lower memory consumption. 

36 

37 solver: string (default='lu') 

38 Type of linear solver to use for computing the flow matrix. 

39 Options are "full" (uses most memory), "lu" (recommended), and 

40 "cg" (uses least memory). 

41 

42 Returns 

43 ------- 

44 nodes : dictionary 

45 Dictionary of nodes with current flow closeness centrality as the value. 

46 

47 See Also 

48 -------- 

49 closeness_centrality 

50 

51 Notes 

52 ----- 

53 The algorithm is from Brandes [1]_. 

54 

55 See also [2]_ for the original definition of information centrality. 

56 

57 References 

58 ---------- 

59 .. [1] Ulrik Brandes and Daniel Fleischer, 

60 Centrality Measures Based on Current Flow. 

61 Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05). 

62 LNCS 3404, pp. 533-544. Springer-Verlag, 2005. 

63 https://doi.org/10.1007/978-3-540-31856-9_44 

64 

65 .. [2] Karen Stephenson and Marvin Zelen: 

66 Rethinking centrality: Methods and examples. 

67 Social Networks 11(1):1-37, 1989. 

68 https://doi.org/10.1016/0378-8733(89)90016-6 

69 """ 

70 if not nx.is_connected(G): 

71 raise nx.NetworkXError("Graph not connected.") 

72 solvername = { 

73 "full": FullInverseLaplacian, 

74 "lu": SuperLUInverseLaplacian, 

75 "cg": CGInverseLaplacian, 

76 } 

77 n = G.number_of_nodes() 

78 ordering = list(reverse_cuthill_mckee_ordering(G)) 

79 # make a copy with integer labels according to rcm ordering 

80 # this could be done without a copy if we really wanted to 

81 H = nx.relabel_nodes(G, dict(zip(ordering, range(n)))) 

82 betweenness = dict.fromkeys(H, 0.0) # b[v]=0 for v in H 

83 n = H.number_of_nodes() 

84 L = nx.laplacian_matrix(H, nodelist=range(n), weight=weight).asformat("csc") 

85 L = L.astype(dtype) 

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 / (betweenness[v]) 

94 return {ordering[k]: v for k, v in betweenness.items()} 

95 

96 

97information_centrality = current_flow_closeness_centrality