### comparison env/lib/python3.9/site-packages/networkx/algorithms/non_randomness.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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