# Source code for networkx.linalg.modularitymatrix

"""Modularity matrix of graphs.
"""
import networkx as nx
from networkx.utils import not_implemented_for

__all__ = ["modularity_matrix", "directed_modularity_matrix"]

[docs]@not_implemented_for("directed")
@not_implemented_for("multigraph")
def modularity_matrix(G, nodelist=None, weight=None):
r"""Returns the modularity matrix of G.

The modularity matrix is the matrix B = A - <A>, where A is the adjacency
matrix and <A> is the average adjacency matrix, assuming that the graph
is described by the configuration model.

More specifically, the element B_ij of B is defined as

.. math::
A_{ij} - {k_i k_j \over 2 m}

where k_i is the degree of node i, and where m is the number of edges
in the graph. When weight is set to a name of an attribute edge, Aij, k_i,
k_j and m are computed using its value.

Parameters
----------
G : Graph
A NetworkX graph

nodelist : list, optional
The rows and columns are ordered according to the nodes in nodelist.
If nodelist is None, then the ordering is produced by G.nodes().

weight : string or None, optional (default=None)
The edge attribute that holds the numerical value used for
the edge weight.  If None then all edge weights are 1.

Returns
-------
B : Numpy matrix
The modularity matrix of G.

Examples
--------
>>> k = [3, 2, 2, 1, 0]
>>> G = nx.havel_hakimi_graph(k)
>>> B = nx.modularity_matrix(G)

--------
to_numpy_array
modularity_spectrum
directed_modularity_matrix

References
----------
..  M. E. J. Newman, "Modularity and community structure in networks",
Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006.
"""
if nodelist is None:
nodelist = list(G)
A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
k = A.sum(axis=1)
m = k.sum() * 0.5
X = k * k.transpose() / (2 * m)
return A - X

[docs]@not_implemented_for("undirected")
@not_implemented_for("multigraph")
def directed_modularity_matrix(G, nodelist=None, weight=None):
"""Returns the directed modularity matrix of G.

The modularity matrix is the matrix B = A - <A>, where A is the adjacency
matrix and <A> is the expected adjacency matrix, assuming that the graph
is described by the configuration model.

More specifically, the element B_ij of B is defined as

.. math::
B_{ij} = A_{ij} - k_i^{out} k_j^{in} / m

where :math:k_i^{in} is the in degree of node i, and :math:k_j^{out} is the out degree
of node j, with m the number of edges in the graph. When weight is set
to a name of an attribute edge, Aij, k_i, k_j and m are computed using
its value.

Parameters
----------
G : DiGraph
A NetworkX DiGraph

nodelist : list, optional
The rows and columns are ordered according to the nodes in nodelist.
If nodelist is None, then the ordering is produced by G.nodes().

weight : string or None, optional (default=None)
The edge attribute that holds the numerical value used for
the edge weight.  If None then all edge weights are 1.

Returns
-------
B : Numpy matrix
The modularity matrix of G.

Examples
--------
>>> G = nx.DiGraph()
...     (
...         (1, 2),
...         (1, 3),
...         (3, 1),
...         (3, 2),
...         (3, 5),
...         (4, 5),
...         (4, 6),
...         (5, 4),
...         (5, 6),
...         (6, 4),
...     )
... )
>>> B = nx.directed_modularity_matrix(G)

Notes
-----
NetworkX defines the element A_ij of the adjacency matrix as 1 if there
is a link going from node i to node j. Leicht and Newman use the opposite
definition. This explains the different expression for B_ij.

--------
to_numpy_array
modularity_spectrum
modularity_matrix

References
----------
..  E. A. Leicht, M. E. J. Newman,
"Community structure in directed networks",
Phys. Rev Lett., vol. 100, no. 11, p. 118703, 2008.
"""
if nodelist is None:
nodelist = list(G)
A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
k_in = A.sum(axis=0)
k_out = A.sum(axis=1)
m = k_in.sum()