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

1"""Copyright (c) 2015 – Thomson Licensing, SAS 

2 

3Redistribution and use in source and binary forms, with or without 

4modification, are permitted (subject to the limitations in the 

5disclaimer below) provided that the following conditions are met: 

6 

7* Redistributions of source code must retain the above copyright 

8notice, this list of conditions and the following disclaimer. 

9 

10* Redistributions in binary form must reproduce the above copyright 

11notice, this list of conditions and the following disclaimer in the 

12documentation and/or other materials provided with the distribution. 

13 

14* Neither the name of Thomson Licensing, or Technicolor, nor the names 

15of its contributors may be used to endorse or promote products derived 

16from this software without specific prior written permission. 

17 

18NO EXPRESS OR IMPLIED LICENSES TO ANY PARTY'S PATENT RIGHTS ARE 

19GRANTED BY THIS LICENSE. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT 

20HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED 

21WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 

22MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 

23DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 

24LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 

25CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 

26SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 

27BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 

28WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 

29OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN 

30IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

31""" 

32 

33import networkx as nx 

34from networkx.utils import not_implemented_for 

35 

36# Authors: Erwan Le Merrer (erwan.lemerrer@technicolor.com) 

37 

38__all__ = ["second_order_centrality"] 

39 

40 

41@not_implemented_for("directed") 

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

43def second_order_centrality(G, weight="weight"): 

44 """Compute the second order centrality for nodes of G. 

45 

46 The second order centrality of a given node is the standard deviation of 

47 the return times to that node of a perpetual random walk on G: 

48 

49 Parameters 

50 ---------- 

51 G : graph 

52 A NetworkX connected and undirected graph. 

53 

54 weight : string or None, optional (default="weight") 

55 The name of an edge attribute that holds the numerical value 

56 used as a weight. If None then each edge has weight 1. 

57 

58 Returns 

59 ------- 

60 nodes : dictionary 

61 Dictionary keyed by node with second order centrality as the value. 

62 

63 Examples 

64 -------- 

65 >>> G = nx.star_graph(10) 

66 >>> soc = nx.second_order_centrality(G) 

67 >>> print(sorted(soc.items(), key=lambda x: x[1])[0][0]) # pick first id 

68 0 

69 

70 Raises 

71 ------ 

72 NetworkXException 

73 If the graph G is empty, non connected or has negative weights. 

74 

75 See Also 

76 -------- 

77 betweenness_centrality 

78 

79 Notes 

80 ----- 

81 Lower values of second order centrality indicate higher centrality. 

82 

83 The algorithm is from Kermarrec, Le Merrer, Sericola and Trédan [1]_. 

84 

85 This code implements the analytical version of the algorithm, i.e., 

86 there is no simulation of a random walk process involved. The random walk 

87 is here unbiased (corresponding to eq 6 of the paper [1]_), thus the 

88 centrality values are the standard deviations for random walk return times 

89 on the transformed input graph G (equal in-degree at each nodes by adding 

90 self-loops). 

91 

92 Complexity of this implementation, made to run locally on a single machine, 

93 is O(n^3), with n the size of G, which makes it viable only for small 

94 graphs. 

95 

96 References 

97 ---------- 

98 .. [1] Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan 

99 "Second order centrality: Distributed assessment of nodes criticity in 

100 complex networks", Elsevier Computer Communications 34(5):619-628, 2011. 

101 """ 

102 import numpy as np 

103 

104 n = len(G) 

105 

106 if n == 0: 

107 raise nx.NetworkXException("Empty graph.") 

108 if not nx.is_connected(G): 

109 raise nx.NetworkXException("Non connected graph.") 

110 if any(d.get(weight, 0) < 0 for u, v, d in G.edges(data=True)): 

111 raise nx.NetworkXException("Graph has negative edge weights.") 

112 

113 # balancing G for Metropolis-Hastings random walks 

114 G = nx.DiGraph(G) 

115 in_deg = dict(G.in_degree(weight=weight)) 

116 d_max = max(in_deg.values()) 

117 for i, deg in in_deg.items(): 

118 if deg < d_max: 

119 G.add_edge(i, i, weight=d_max - deg) 

120 

121 P = nx.to_numpy_array(G) 

122 P /= P.sum(axis=1)[:, np.newaxis] # to transition probability matrix 

123 

124 def _Qj(P, j): 

125 P = P.copy() 

126 P[:, j] = 0 

127 return P 

128 

129 M = np.empty([n, n]) 

130 

131 for i in range(n): 

132 M[:, i] = np.linalg.solve( 

133 np.identity(n) - _Qj(P, i), np.ones([n, 1])[:, 0] 

134 ) # eq 3 

135 

136 return dict( 

137 zip(G.nodes, [np.sqrt(2 * np.sum(M[:, i]) - n * (n + 1)) for i in range(n)]) 

138 ) # eq 6