Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/clustering_coefficient.py: 39%

1import networkx as nx 

2from networkx.utils import not_implemented_for, py_random_state 

3 

4__all__ = ["average_clustering"] 

5 

6 

7@not_implemented_for("directed") 

8@py_random_state(2) 

9@nx._dispatch(name="approximate_average_clustering") 

10def average_clustering(G, trials=1000, seed=None): 

11 r"""Estimates the average clustering coefficient of G. 

12 

13 The local clustering of each node in `G` is the fraction of triangles 

14 that actually exist over all possible triangles in its neighborhood. 

15 The average clustering coefficient of a graph `G` is the mean of 

16 local clusterings. 

17 

18 This function finds an approximate average clustering coefficient 

19 for G by repeating `n` times (defined in `trials`) the following 

20 experiment: choose a node at random, choose two of its neighbors 

21 at random, and check if they are connected. The approximate 

22 coefficient is the fraction of triangles found over the number 

23 of trials [1]_. 

24 

25 Parameters 

26 ---------- 

27 G : NetworkX graph 

28 

29 trials : integer 

30 Number of trials to perform (default 1000). 

31 

32 seed : integer, random_state, or None (default) 

33 Indicator of random number generation state. 

34 See :ref:`Randomness<randomness>`. 

35 

36 Returns 

37 ------- 

38 c : float 

39 Approximated average clustering coefficient. 

40 

41 Examples 

42 -------- 

43 >>> from networkx.algorithms import approximation 

44 >>> G = nx.erdos_renyi_graph(10, 0.2, seed=10) 

45 >>> approximation.average_clustering(G, trials=1000, seed=10) 

46 0.214 

47 

48 References 

49 ---------- 

50 .. [1] Schank, Thomas, and Dorothea Wagner. Approximating clustering 

51 coefficient and transitivity. Universität Karlsruhe, Fakultät für 

52 Informatik, 2004. 

53 https://doi.org/10.5445/IR/1000001239 

54 

55 """ 

56 n = len(G) 

57 triangles = 0 

58 nodes = list(G) 

59 for i in [int(seed.random() * n) for i in range(trials)]: 

60 nbrs = list(G[nodes[i]]) 

61 if len(nbrs) < 2: 

62 continue 

63 u, v = seed.sample(nbrs, 2) 

64 if u in G[v]: 

65 triangles += 1 

66 return triangles / trials