Package networkx :: Module cluster

Module cluster

Compute clustering coefficients and transitivity of graphs.

Clustering coefficient

For each node find the fraction of possible triangles that are triangles, c_i = triangles_i / (k_i*(k_i-1)/2) where k_i is the degree of node i.

A coefficient for the whole graph is the average C = avg(c_i)

Transitivity

Find the fraction of all possible triangles which are in fact triangles. Possible triangles are identified by the number of "triads" (two edges with a shared vertex)

T = 3*triangles/triads

Date: $Date: 2005-06-14 12:48:10 -0600 (Tue, 14 Jun 2005) $

Author: Aric Hagberg (hagberg@lanl.gov) Pieter Swart (swart@lanl.gov) Dan Schult (dschult@colgate.edu)

Functions

[hide private]

triangles(G, nbunch=None, with_labels=False)
Return number of triangles for nbunch of nodes.

source code

average_clustering(G)
Average clustering coefficient for a graph.

source code

clustering(G, nbunch=None, with_labels=False, weights=False)
Clustering coefficient for each node in nbunch.

source code

transitivity(G)
Transitivity (fraction of transitive triangles) for a graph

source code

_test_suite()

source code

Variables

[hide private]

__credits__ = ''

__revision__ = '$Revision: 1012 $'

Function Details

[hide private]

triangles(G, nbunch=None, with_labels=False)

source code

Return number of triangles for nbunch of nodes. If nbunch is None, then return triangles for every node. If with_labels is True, return a dict keyed by node.

Note: Each triangle is counted three times: once at each vertex.

average_clustering(G)

source code

Average clustering coefficient for a graph.

Note: this is a space saving routine; It might be faster to use clustering to get a list and then take average.

clustering(G, nbunch=None, with_labels=False, weights=False)

source code

Clustering coefficient for each node in nbunch.

If with_labels is True, return a dict keyed by node.

If both with_labels and weights are True, return both a clustering coefficient dict keyed by node and a dict of weights based on degree. The weights are the fraction of connected triples in the graph which include the keyed node. Ths is useful in moving from transitivity for clustering coefficient and back.