### comparison env/lib/python3.9/site-packages/networkx/linalg/modularitymatrix.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """Modularity matrix of graphs.
2 """
3 import networkx as nx
4 from 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 def modularity_matrix(G, nodelist=None, weight=None):
12 r"""Returns the modularity matrix of G.
13
14 The modularity matrix is the matrix B = A - <A>, where A is the adjacency
15 matrix and <A> is the average adjacency matrix, assuming that the graph
16 is described by the configuration model.
17
18 More specifically, the element B_ij of B is defined as
19
20 .. math::
21 A_{ij} - {k_i k_j \over 2 m}
22
23 where k_i is the degree of node i, and where m is the number of edges
24 in the graph. When weight is set to a name of an attribute edge, Aij, k_i,
25 k_j and m are computed using its value.
26
27 Parameters
28 ----------
29 G : Graph
30 A NetworkX graph
31
32 nodelist : list, optional
33 The rows and columns are ordered according to the nodes in nodelist.
34 If nodelist is None, then the ordering is produced by G.nodes().
35
36 weight : string or None, optional (default=None)
37 The edge attribute that holds the numerical value used for
38 the edge weight. If None then all edge weights are 1.
39
40 Returns
41 -------
42 B : Numpy matrix
43 The modularity matrix of G.
44
45 Examples
46 --------
47 >>> k = [3, 2, 2, 1, 0]
48 >>> G = nx.havel_hakimi_graph(k)
49 >>> B = nx.modularity_matrix(G)
50
51
53 --------
54 to_numpy_array
55 modularity_spectrum
57 directed_modularity_matrix
58
59 References
60 ----------
61 ..  M. E. J. Newman, "Modularity and community structure in networks",
62 Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006.
63 """
64 if nodelist is None:
65 nodelist = list(G)
66 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
67 k = A.sum(axis=1)
68 m = k.sum() * 0.5
70 X = k * k.transpose() / (2 * m)
71 return A - X
72
73
74 @not_implemented_for("undirected")
75 @not_implemented_for("multigraph")
76 def directed_modularity_matrix(G, nodelist=None, weight=None):
77 """Returns the directed modularity matrix of G.
78
79 The modularity matrix is the matrix B = A - <A>, where A is the adjacency
80 matrix and <A> is the expected adjacency matrix, assuming that the graph
81 is described by the configuration model.
82
83 More specifically, the element B_ij of B is defined as
84
85 .. math::
86 B_{ij} = A_{ij} - k_i^{out} k_j^{in} / m
87
88 where :math:k_i^{in} is the in degree of node i, and :math:k_j^{out} is the out degree
89 of node j, with m the number of edges in the graph. When weight is set
90 to a name of an attribute edge, Aij, k_i, k_j and m are computed using
91 its value.
92
93 Parameters
94 ----------
95 G : DiGraph
96 A NetworkX DiGraph
97
98 nodelist : list, optional
99 The rows and columns are ordered according to the nodes in nodelist.
100 If nodelist is None, then the ordering is produced by G.nodes().
101
102 weight : string or None, optional (default=None)
103 The edge attribute that holds the numerical value used for
104 the edge weight. If None then all edge weights are 1.
105
106 Returns
107 -------
108 B : Numpy matrix
109 The modularity matrix of G.
110
111 Examples
112 --------
113 >>> G = nx.DiGraph()
115 ... (
116 ... (1, 2),
117 ... (1, 3),
118 ... (3, 1),
119 ... (3, 2),
120 ... (3, 5),
121 ... (4, 5),
122 ... (4, 6),
123 ... (5, 4),
124 ... (5, 6),
125 ... (6, 4),
126 ... )
127 ... )
128 >>> B = nx.directed_modularity_matrix(G)
129
130
131 Notes
132 -----
133 NetworkX defines the element A_ij of the adjacency matrix as 1 if there
134 is a link going from node i to node j. Leicht and Newman use the opposite
135 definition. This explains the different expression for B_ij.
136
138 --------
139 to_numpy_array
140 modularity_spectrum
142 modularity_matrix
143
144 References
145 ----------
146 ..  E. A. Leicht, M. E. J. Newman,
147 "Community structure in directed networks",
148 Phys. Rev Lett., vol. 100, no. 11, p. 118703, 2008.
149 """
150 if nodelist is None:
151 nodelist = list(G)
152 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
153 k_in = A.sum(axis=0)
154 k_out = A.sum(axis=1)
155 m = k_in.sum()