Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/non_randomness.py: 36%

1r""" Computation of graph non-randomness 

2""" 

3 

4import math 

5 

6import networkx as nx 

7from networkx.utils import not_implemented_for 

8 

9__all__ = ["non_randomness"] 

10 

11 

12@not_implemented_for("directed") 

13@not_implemented_for("multigraph") 

14@nx._dispatch(edge_attrs="weight") 

15def non_randomness(G, k=None, weight="weight"): 

16 """Compute the non-randomness of graph G. 

17 

18 The first returned value nr is the sum of non-randomness values of all 

19 edges within the graph (where the non-randomness of an edge tends to be 

20 small when the two nodes linked by that edge are from two different 

21 communities). 

22 

23 The second computed value nr_rd is a relative measure that indicates 

24 to what extent graph G is different from random graphs in terms 

25 of probability. When it is close to 0, the graph tends to be more 

26 likely generated by an Erdos Renyi model. 

27 

28 Parameters 

29 ---------- 

30 G : NetworkX graph 

31 Graph must be symmetric, connected, and without self-loops. 

32 

33 k : int 

34 The number of communities in G. 

35 If k is not set, the function will use a default community 

36 detection algorithm to set it. 

37 

38 weight : string or None, optional (default=None) 

39 The name of an edge attribute that holds the numerical value used 

40 as a weight. If None, then each edge has weight 1, i.e., the graph is 

41 binary. 

42 

43 Returns 

44 ------- 

45 non-randomness : (float, float) tuple 

46 Non-randomness, Relative non-randomness w.r.t. 

47 Erdos Renyi random graphs. 

48 

49 Raises 

50 ------ 

51 NetworkXException 

52 if the input graph is not connected. 

53 NetworkXError 

54 if the input graph contains self-loops. 

55 

56 Examples 

57 -------- 

58 >>> G = nx.karate_club_graph() 

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

60 >>> nr, nr_rd = nx.non_randomness(G, 2, 'weight') 

61 

62 Notes 

63 ----- 

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

65 

66 If a weight field is passed, this algorithm will use the eigenvalues 

67 of the weighted adjacency matrix to compute Eq. (4.4) and (4.5). 

68 

69 References 

70 ---------- 

71 .. [1] Xiaowei Ying and Xintao Wu, 

72 On Randomness Measures for Social Networks, 

73 SIAM International Conference on Data Mining. 2009 

74 """ 

75 import numpy as np 

76 

77 if not nx.is_connected(G): 

78 raise nx.NetworkXException("Non connected graph.") 

79 if len(list(nx.selfloop_edges(G))) > 0: 

80 raise nx.NetworkXError("Graph must not contain self-loops") 

81 

82 if k is None: 

83 k = len(tuple(nx.community.label_propagation_communities(G))) 

84 

85 # eq. 4.4 

86 eigenvalues = np.linalg.eigvals(nx.to_numpy_array(G, weight=weight)) 

87 nr = np.real(np.sum(eigenvalues[:k])) 

88 

89 n = G.number_of_nodes() 

90 m = G.number_of_edges() 

91 p = (2 * k * m) / (n * (n - k)) 

92 

93 # eq. 4.5 

94 nr_rd = (nr - ((n - 2 * k) * p + k)) / math.sqrt(2 * k * p * (1 - p)) 

95 

96 return nr, nr_rd