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.

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