view env/lib/python3.9/site-packages/networkx/algorithms/ @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source

r""" Computation of graph non-randomness

import math
import networkx as nx
from networkx.utils import not_implemented_for

__all__ = ["non_randomness"]

def non_randomness(G, k=None):
    """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

    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.

    G : NetworkX graph
        Graph must be binary, 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.

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

    >>> G = nx.karate_club_graph()
    >>> nr, nr_rd = nx.non_randomness(G, 2)

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

     .. [1] Xiaowei Ying and Xintao Wu,
            On Randomness Measures for Social Networks,
            SIAM International Conference on Data Mining. 2009

    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(

        import numpy as np
    except ImportError as e:
        msg = "non_randomness requires NumPy:"
        raise ImportError(msg) from e

    # eq. 4.4
    nr = np.real(np.sum(np.linalg.eigvals(nx.to_numpy_array(G))[: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