Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/algorithms/centrality/current_flow_closeness.py: 35%

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

2 

3import networkx as nx 

4from networkx.algorithms.centrality.flow_matrix import ( 

5 CGInverseLaplacian, 

6 FullInverseLaplacian, 

7 SuperLUInverseLaplacian, 

8) 

9from networkx.utils import not_implemented_for, reverse_cuthill_mckee_ordering 

10 

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

12 

13 

14@not_implemented_for("directed") 

15@nx._dispatchable(edge_attrs="weight") 

16def 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 The weight reflects the capacity or the strength of the 

32 edge. 

33 

34 dtype: data type (default=float) 

35 Default data type for internal matrices. 

36 Set to np.float32 for lower memory consumption. 

37 

38 solver: string (default='lu') 

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

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

41 "cg" (uses least memory). 

42 

43 Returns 

44 ------- 

45 nodes : dictionary 

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

47 

48 See Also 

49 -------- 

50 closeness_centrality 

51 

52 Notes 

53 ----- 

54 The algorithm is from Brandes [1]_. 

55 

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

57 

58 References 

59 ---------- 

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

61 Centrality Measures Based on Current Flow. 

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

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

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

65 

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

67 Rethinking centrality: Methods and examples. 

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

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

70 """ 

71 if not nx.is_connected(G): 

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

73 solvername = { 

74 "full": FullInverseLaplacian, 

75 "lu": SuperLUInverseLaplacian, 

76 "cg": CGInverseLaplacian, 

77 } 

78 N = G.number_of_nodes() 

79 ordering = list(reverse_cuthill_mckee_ordering(G)) 

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

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

82 H = nx.relabel_nodes(G, dict(zip(ordering, range(N)))) 

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

84 N = H.number_of_nodes() 

85 L = nx.laplacian_matrix(H, nodelist=range(N), weight=weight).asformat("csc") 

86 L = L.astype(dtype) 

87 C2 = solvername[solver](L, width=1, dtype=dtype) # initialize solver 

88 for v in H: 

89 col = C2.get_row(v) 

90 for w in H: 

91 betweenness[v] += col.item(v) - 2 * col.item(w) 

92 betweenness[w] += col.item(v) 

93 return {ordering[node]: 1 / value for node, value in betweenness.items()} 

94 

95 

96information_centrality = current_flow_closeness_centrality