Skip to main content
`Ctrl`+`K`

# Source code for networkx.algorithms.non_randomness

    r"""Computation of graph non-randomness"""

    import math

    import networkx as nx
    from networkx.utils import not_implemented_for

    __all__ = ["non_randomness"]

    @not_implemented_for("directed")
    @not_implemented_for("multigraph")
    @nx._dispatchable(edge_attrs="weight")
    def non_randomness(G, k=None, weight="weight"):
        """Compute the non-randomness of graph G.

        The first returned value nr is the sum of non-randomness values of all
        edges within the graph (where the non-randomness of an edge tends to be
        small when the two nodes linked by that edge are from two different
        communities).

        The second computed value nr_rd is a relative measure that indicates
        to what extent graph G is different from random graphs in terms
        of probability. When it is close to 0, the graph tends to be more
        likely generated by an Erdos Renyi model.

        Parameters
        ----------
        G : NetworkX graph
            Graph must be symmetric, connected, and without self-loops.

        k : int
            The number of communities in G.
            If k is not set, the function will use a default community
            detection algorithm to set it.

        weight : string or None, optional (default=None)
            The name of an edge attribute that holds the numerical value used
            as a weight. If None, then each edge has weight 1, i.e., the graph is
            binary.

        Returns
        -------
        non-randomness : (float, float) tuple
            Non-randomness, Relative non-randomness w.r.t.
            Erdos Renyi random graphs.

        Raises
        ------
        NetworkXException
            if the input graph is not connected.
        NetworkXError
            if the input graph contains self-loops or if graph has no edges.

        Examples
        --------
        >>> G = nx.karate_club_graph()
        >>> nr, nr_rd = nx.non_randomness(G, 2)
        >>> nr, nr_rd = nx.non_randomness(G, 2, "weight")

        Notes
        -----
        This computes Eq. (4.4) and (4.5) in Ref. [1]_.

        If a weight field is passed, this algorithm will use the eigenvalues
        of the weighted adjacency matrix to compute Eq. (4.4) and (4.5).

        References
        ----------
        .. [1] Xiaowei Ying and Xintao Wu,
               On Randomness Measures for Social Networks,
               SIAM International Conference on Data Mining. 2009
        """
        import numpy as np

        # corner case: graph has no edges
        if nx.is_empty(G):
            raise nx.NetworkXError("non_randomness not applicable to empty graphs")
        if not nx.is_connected(G):
            raise nx.NetworkXException("Non connected graph.")
        if len(list(nx.selfloop_edges(G))) > 0:
            raise nx.NetworkXError("Graph must not contain self-loops")

        if k is None:
            k = len(tuple(nx.community.label_propagation_communities(G)))

        # eq. 4.4
        eigenvalues = np.linalg.eigvals(nx.to_numpy_array(G, weight=weight))
        nr = float(np.real(np.sum(eigenvalues[:k])))

        n = G.number_of_nodes()
        m = G.number_of_edges()
        p = (2 * k * m) / (n * (n - k))

        # eq. 4.5
        nr_rd = (nr - ((n - 2 * k) * p + k)) / math.sqrt(2 * k * p * (1 - p))

        return nr, nr_rd