Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1import networkx as nx
2from networkx.utils import not_implemented_for, py_random_state
4__all__ = ["average_clustering"]
7@not_implemented_for("directed")
8@py_random_state(2)
9@nx._dispatchable(name="approximate_average_clustering")
10def average_clustering(G, trials=1000, seed=None):
11 r"""Estimates the average clustering coefficient of G.
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.
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]_.
25 Parameters
26 ----------
27 G : NetworkX graph
29 trials : integer
30 Number of trials to perform (default 1000).
32 seed : integer, random_state, or None (default)
33 Indicator of random number generation state.
34 See :ref:`Randomness<randomness>`.
36 Returns
37 -------
38 c : float
39 Approximated average clustering coefficient.
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
48 Raises
49 ------
50 NetworkXNotImplemented
51 If G is directed.
53 References
54 ----------
55 .. [1] Schank, Thomas, and Dorothea Wagner. Approximating clustering
56 coefficient and transitivity. Universität Karlsruhe, Fakultät für
57 Informatik, 2004.
58 https://doi.org/10.5445/IR/1000001239
60 """
61 n = len(G)
62 triangles = 0
63 nodes = list(G)
64 for i in [int(seed.random() * n) for i in range(trials)]:
65 nbrs = list(G[nodes[i]])
66 if len(nbrs) < 2:
67 continue
68 u, v = seed.sample(nbrs, 2)
69 if u in G[v]:
70 triangles += 1
71 return triangles / trials