Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/non_randomness.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 r""" Computation of graph non-randomness | |
2 """ | |
3 | |
4 import math | |
5 import networkx as nx | |
6 from networkx.utils import not_implemented_for | |
7 | |
8 __all__ = ["non_randomness"] | |
9 | |
10 | |
11 @not_implemented_for("directed") | |
12 @not_implemented_for("multigraph") | |
13 def non_randomness(G, k=None): | |
14 """Compute the non-randomness of graph G. | |
15 | |
16 The first returned value nr is the sum of non-randomness values of all | |
17 edges within the graph (where the non-randomness of an edge tends to be | |
18 small when the two nodes linked by that edge are from two different | |
19 communities). | |
20 | |
21 The second computed value nr_rd is a relative measure that indicates | |
22 to what extent graph G is different from random graphs in terms | |
23 of probability. When it is close to 0, the graph tends to be more | |
24 likely generated by an Erdos Renyi model. | |
25 | |
26 Parameters | |
27 ---------- | |
28 G : NetworkX graph | |
29 Graph must be binary, symmetric, connected, and without self-loops. | |
30 | |
31 k : int | |
32 The number of communities in G. | |
33 If k is not set, the function will use a default community | |
34 detection algorithm to set it. | |
35 | |
36 Returns | |
37 ------- | |
38 non-randomness : (float, float) tuple | |
39 Non-randomness, Relative non-randomness w.r.t. | |
40 Erdos Renyi random graphs. | |
41 | |
42 Examples | |
43 -------- | |
44 >>> G = nx.karate_club_graph() | |
45 >>> nr, nr_rd = nx.non_randomness(G, 2) | |
46 | |
47 Notes | |
48 ----- | |
49 This computes Eq. (4.4) and (4.5) in Ref. [1]_. | |
50 | |
51 References | |
52 ---------- | |
53 .. [1] Xiaowei Ying and Xintao Wu, | |
54 On Randomness Measures for Social Networks, | |
55 SIAM International Conference on Data Mining. 2009 | |
56 """ | |
57 | |
58 if not nx.is_connected(G): | |
59 raise nx.NetworkXException("Non connected graph.") | |
60 if len(list(nx.selfloop_edges(G))) > 0: | |
61 raise nx.NetworkXError("Graph must not contain self-loops") | |
62 | |
63 if k is None: | |
64 k = len(tuple(nx.community.label_propagation_communities(G))) | |
65 | |
66 try: | |
67 import numpy as np | |
68 except ImportError as e: | |
69 msg = "non_randomness requires NumPy: http://numpy.org/" | |
70 raise ImportError(msg) from e | |
71 | |
72 # eq. 4.4 | |
73 nr = np.real(np.sum(np.linalg.eigvals(nx.to_numpy_array(G))[:k])) | |
74 | |
75 n = G.number_of_nodes() | |
76 m = G.number_of_edges() | |
77 p = (2 * k * m) / (n * (n - k)) | |
78 | |
79 # eq. 4.5 | |
80 nr_rd = (nr - ((n - 2 * k) * p + k)) / math.sqrt(2 * k * p * (1 - p)) | |
81 | |
82 return nr, nr_rd |