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

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