Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / clustering_coefficient.py @ 5cef0f13

History | View | Annotate | Download (2.16 KB)

1
# -*- coding: utf-8 -*-
2
#   Copyright (C) 2013 by
3
#   Fred Morstatter <fred.morstatter@asu.edu>
4
#   Jordi Torrents <jtorrents@milnou.net>
5
#   All rights reserved.
6
#   BSD license.
7
import random
8
from networkx.utils import not_implemented_for
9
from networkx.utils import py_random_state
10

    
11
__all__ = ['average_clustering']
12
__author__ = """\n""".join(['Fred Morstatter <fred.morstatter@asu.edu>',
13
                            'Jordi Torrents <jtorrents@milnou.net>'])
14

    
15

    
16
@py_random_state(2)
17
@not_implemented_for('directed')
18
def average_clustering(G, trials=1000, seed=None):
19
    r"""Estimates the average clustering coefficient of G.
20

21
    The local clustering of each node in `G` is the fraction of triangles
22
    that actually exist over all possible triangles in its neighborhood.
23
    The average clustering coefficient of a graph `G` is the mean of
24
    local clusterings.
25

26
    This function finds an approximate average clustering coefficient
27
    for G by repeating `n` times (defined in `trials`) the following
28
    experiment: choose a node at random, choose two of its neighbors
29
    at random, and check if they are connected. The approximate
30
    coefficient is the fraction of triangles found over the number
31
    of trials [1]_.
32

33
    Parameters
34
    ----------
35
    G : NetworkX graph
36

37
    trials : integer
38
        Number of trials to perform (default 1000).
39

40
    seed : integer, random_state, or None (default)
41
        Indicator of random number generation state.
42
        See :ref:`Randomness<randomness>`.
43

44
    Returns
45
    -------
46
    c : float
47
        Approximated average clustering coefficient.
48

49
    References
50
    ----------
51
    .. [1] Schank, Thomas, and Dorothea Wagner. Approximating clustering
52
       coefficient and transitivity. Universität Karlsruhe, Fakultät für
53
       Informatik, 2004.
54
       http://www.emis.ams.org/journals/JGAA/accepted/2005/SchankWagner2005.9.2.pdf
55

56
    """
57
    n = len(G)
58
    triangles = 0
59
    nodes = list(G)
60
    for i in [int(seed.random() * n) for i in range(trials)]:
61
        nbrs = list(G[nodes[i]])
62
        if len(nbrs) < 2:
63
            continue
64
        u, v = seed.sample(nbrs, 2)
65
        if u in G[v]:
66
            triangles += 1
67
    return triangles / float(trials)