graph_tool.clustering.local_clustering#
- graph_tool.clustering.local_clustering(g, weight=None, prop=None, undirected=True)[source]#
Return the local clustering coefficients for all vertices.
- Parameters:
- g
Graph
Graph to be used.
- weight
EdgePropertyMap
, optional (default: None) Edge weights. If omitted, a constant value of 1 will be used.
- prop
VertexPropertyMap
or string, optional Vertex property map where results will be stored. If specified, this parameter will also be the return value.
- undirectedbool (default:
True
) Calculate the undirected clustering coefficient, if graph is directed (this option has no effect if the graph is undirected).
- g
- Returns:
- prop
VertexPropertyMap
Vertex property containing the clustering coefficients.
- prop
See also
global_clustering
global clustering coefficient
extended_clustering
extended (generalized) clustering coefficient
motifs
motif counting
Notes
The local clustering coefficient [watts-collective-1998] \(c_i\) is defined as
\[c_i = \frac{|\{e_{jk}\}|}{k_i(k_i-1)} :\, v_j,v_k \in N_i,\, e_{jk} \in E\]where \(k_i\) is the out-degree of vertex \(i\), and
\[N_i = \{v_j : e_{ij} \in E\}\]is the set of out-neighbors of vertex \(i\). For undirected graphs the value of \(c_i\) is normalized as
\[c'_i = 2c_i.\]The implemented algorithm runs in \(O(|V|\left<k^2\right>)\) time, where \(\left<k^2\right>\) is second moment of the degree distribution.
If enabled during compilation, this algorithm runs in parallel.
References
[watts-collective-1998]D. J. Watts and Steven Strogatz, “Collective dynamics of ‘small-world’ networks”, Nature, vol. 393, pp 440-442, 1998. DOI: 10.1038/30918 [sci-hub, @tor]
Examples
>>> g = gt.collection.data["karate"] >>> clust = gt.local_clustering(g) >>> print(gt.vertex_average(g, clust)) (0.5706384782..., 0.05869813676...)