Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/linalg/modularitymatrix.py: 39%

1"""Modularity matrix of graphs. 

2""" 

3import networkx as nx 

4from networkx.utils import not_implemented_for 

5 

6__all__ = ["modularity_matrix", "directed_modularity_matrix"] 

7 

8 

9@not_implemented_for("directed") 

10@not_implemented_for("multigraph") 

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

12def modularity_matrix(G, nodelist=None, weight=None): 

13 r"""Returns the modularity matrix of G. 

14 

15 The modularity matrix is the matrix B = A - <A>, where A is the adjacency 

16 matrix and <A> is the average adjacency matrix, assuming that the graph 

17 is described by the configuration model. 

18 

19 More specifically, the element B_ij of B is defined as 

20 

21 .. math:: 

22 A_{ij} - {k_i k_j \over 2 m} 

23 

24 where k_i is the degree of node i, and where m is the number of edges 

25 in the graph. When weight is set to a name of an attribute edge, Aij, k_i, 

26 k_j and m are computed using its value. 

27 

28 Parameters 

29 ---------- 

30 G : Graph 

31 A NetworkX graph 

32 

33 nodelist : list, optional 

34 The rows and columns are ordered according to the nodes in nodelist. 

35 If nodelist is None, then the ordering is produced by G.nodes(). 

36 

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

38 The edge attribute that holds the numerical value used for 

39 the edge weight. If None then all edge weights are 1. 

40 

41 Returns 

42 ------- 

43 B : Numpy array 

44 The modularity matrix of G. 

45 

46 Examples 

47 -------- 

48 >>> k = [3, 2, 2, 1, 0] 

49 >>> G = nx.havel_hakimi_graph(k) 

50 >>> B = nx.modularity_matrix(G) 

51 

52 

53 See Also 

54 -------- 

55 to_numpy_array 

56 modularity_spectrum 

57 adjacency_matrix 

58 directed_modularity_matrix 

59 

60 References 

61 ---------- 

62 .. [1] M. E. J. Newman, "Modularity and community structure in networks", 

63 Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006. 

64 """ 

65 import numpy as np 

66 

67 if nodelist is None: 

68 nodelist = list(G) 

69 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, format="csr") 

70 k = A.sum(axis=1) 

71 m = k.sum() * 0.5 

72 # Expected adjacency matrix 

73 X = np.outer(k, k) / (2 * m) 

74 

75 return A - X 

76 

77 

78@not_implemented_for("undirected") 

79@not_implemented_for("multigraph") 

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

81def directed_modularity_matrix(G, nodelist=None, weight=None): 

82 """Returns the directed modularity matrix of G. 

83 

84 The modularity matrix is the matrix B = A - <A>, where A is the adjacency 

85 matrix and <A> is the expected adjacency matrix, assuming that the graph 

86 is described by the configuration model. 

87 

88 More specifically, the element B_ij of B is defined as 

89 

90 .. math:: 

91 B_{ij} = A_{ij} - k_i^{out} k_j^{in} / m 

92 

93 where :math:`k_i^{in}` is the in degree of node i, and :math:`k_j^{out}` is the out degree 

94 of node j, with m the number of edges in the graph. When weight is set 

95 to a name of an attribute edge, Aij, k_i, k_j and m are computed using 

96 its value. 

97 

98 Parameters 

99 ---------- 

100 G : DiGraph 

101 A NetworkX DiGraph 

102 

103 nodelist : list, optional 

104 The rows and columns are ordered according to the nodes in nodelist. 

105 If nodelist is None, then the ordering is produced by G.nodes(). 

106 

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

108 The edge attribute that holds the numerical value used for 

109 the edge weight. If None then all edge weights are 1. 

110 

111 Returns 

112 ------- 

113 B : Numpy array 

114 The modularity matrix of G. 

115 

116 Examples 

117 -------- 

118 >>> G = nx.DiGraph() 

119 >>> G.add_edges_from( 

120 ... ( 

121 ... (1, 2), 

122 ... (1, 3), 

123 ... (3, 1), 

124 ... (3, 2), 

125 ... (3, 5), 

126 ... (4, 5), 

127 ... (4, 6), 

128 ... (5, 4), 

129 ... (5, 6), 

130 ... (6, 4), 

131 ... ) 

132 ... ) 

133 >>> B = nx.directed_modularity_matrix(G) 

134 

135 

136 Notes 

137 ----- 

138 NetworkX defines the element A_ij of the adjacency matrix as 1 if there 

139 is a link going from node i to node j. Leicht and Newman use the opposite 

140 definition. This explains the different expression for B_ij. 

141 

142 See Also 

143 -------- 

144 to_numpy_array 

145 modularity_spectrum 

146 adjacency_matrix 

147 modularity_matrix 

148 

149 References 

150 ---------- 

151 .. [1] E. A. Leicht, M. E. J. Newman, 

152 "Community structure in directed networks", 

153 Phys. Rev Lett., vol. 100, no. 11, p. 118703, 2008. 

154 """ 

155 import numpy as np 

156 

157 if nodelist is None: 

158 nodelist = list(G) 

159 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, format="csr") 

160 k_in = A.sum(axis=0) 

161 k_out = A.sum(axis=1) 

162 m = k_in.sum() 

163 # Expected adjacency matrix 

164 X = np.outer(k_out, k_in) / m 

165 

166 return A - X