| 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") |
| 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. |
| |
| 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 |
|
|
| 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))) |
|
|
| |
| eigenvalues = np.linalg.eigvals(nx.to_numpy_array(G, weight=weight)) |
| nr = np.real(np.sum(eigenvalues[:k])) |
|
|
| n = G.number_of_nodes() |
| m = G.number_of_edges() |
| p = (2 * k * m) / (n * (n - k)) |
|
|
| |
| nr_rd = (nr - ((n - 2 * k) * p + k)) / math.sqrt(2 * k * p * (1 - p)) |
|
|
| return nr, nr_rd |
|
|
