global_clustering

graph_tool.clustering.global_clustering(g, weight=None, ret_counts=False, sampled=False, m=1000)

Return the global clustering coefficient.

Parameters:

gGraph

Graph to be used.

weightEdgePropertyMap, optional (default: None)

Edge weights. If omitted, a constant value of 1 will be used.

ret_countsboolean (optional, default: False)

If True the number of triangles and connected triples are also returned.

sampledbool (default: False)

If True a much faster, assymptotically exact, sampling estimate is performed. In this case the, weight option is ignored.

mint (default: 1000)

If sampled is True, this will be the number of samples used for the estimation.

Returns:

ctuple of floats or float

Global clustering coefficient and standard deviation (jackknife method). If sampled is True only the clustering coefficient is returned.

trianglesint (if ret_counts is True)

Number of triangles. Not returned if sampled is True.

triplesint (if ret_counts is True)

Number of connected triples. Not returned if sampled is True.

See also

local_clustering

local clustering coefficient

extended_clustering

extended (generalized) clustering coefficient

motifs

motif counting

Notes

The global clustering coefficient [newman-structure-2003] \(c\) is defined as

\[c = 3 \times \frac{\text{number of triangles}} {\text{number of connected triples}}\]

If weights are given, the following definition is used [zhang-general-2005]:

\[c = \frac{\mathrm{Tr}{{\boldsymbol A}^3}}{\sum_{i\ne j}[{\boldsymbol A}^2]_{ij}},\]

where \(\boldsymbol A\) is the weighted adjacency matrix, and it is assumed that the weights are normalized in the unit interval, i.e. \(A_{ij} \in [0,1]\).

The implemented algorithm runs in time \(O(|V|\left<k^2\right>)\), where \(\left< k^2\right>\) is the second moment of the degree distribution.

Parallel implementation.

If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.

References

[newman-structure-2003]

M. E. J. Newman, “The structure and function of complex networks”, SIAM Review, vol. 45, pp. 167-256, 2003, DOI: 10.1137/S003614450342480 [sci-hub, @tor]

[zhang-general-2005]

Zhang B, Horvath S, “A general framework for weighted gene co-expression network analysis”, Stat Appl Genet Mol Biol. 4 17 (2005) DOI: 10.2202/1544-6115.1128 [sci-hub, @tor]

Examples

>>> g = gt.collection.data["karate"]
>>> print(gt.global_clustering(g))
(0.2556818181..., 0.06314746595...)