# 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:
gGraph

Graph to be used.

weightEdgePropertyMap, optional (default: None)

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

propVertexPropertyMap 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).

Returns:
propVertexPropertyMap

Vertex property containing the clustering coefficients.

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

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...)