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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/linalg/modularitymatrix.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,158 @@
+"""Modularity matrix of graphs.
+"""
+import networkx as nx
+from networkx.utils import not_implemented_for
+
+__all__ = ["modularity_matrix", "directed_modularity_matrix"]
+
+
+@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
+    ----------
+    .. [1] 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
+    # Expected adjacency matrix
+    X = k * k.transpose() / (2 * m)
+    return A - X
+
+
+@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
+    ----------
+    .. [1] 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()
+    # Expected adjacency matrix
+    X = k_out * k_in / m
+    return A - X