graph_tool.clustering.global_clustering#

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

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:

\[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, i.e. \(A_{ij} \le 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.

If enabled during compilation, this algorithm runs in parallel.

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]

Examples

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