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

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