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:
- g
Graph
Graph to be used.
- weight
EdgePropertyMap
, optional (default: None) Edge weights. If omitted, a constant value of 1 will be used.
- ret_counts
boolean
(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.
- g
- 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...)