local_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{|\{(j,k)\}|}{d_i(d_i-1)} :\, j,k \in N_i,\, (j,k) \in E\]

where \(d_i\) is the out-degree of vertex \(i\), and

\[N_i = \{j : (i,j) \in E\}\]

is the set of out-neighbors of vertex \(i\). For undirected graphs the value of \(c_i\) further normalized as

\[c_i \leftarrow 2c_i.\]

If weights are given, the following definition is used [zhang-general-2005]:

\[c_i = \frac{\sum_{jk}A_{ij}A_{jk}A_{ik}}{\sum_{j\ne k}A_{ij}A_{ik}},\]

where \(\boldsymbol A\) is the weighted adjacency matrix, and it is assumed that the weights are normalized in the unit interval, i.e. \(A_{ij} \in [0,1]\).

The implemented algorithm runs in \(O(|V|\left<k^2\right>)\) time, where \(\left<k^2\right>\) is second moment of the degree distribution.

Parallel implementation.

If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.

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]

[zhang-general-2005]

Zhang B, Horvath S, “A general framework for weighted gene co-expression network analysis”, Stat Appl Genet Mol Biol. 4 17 (2005) DOI: 10.2202/1544-6115.1128 [sci-hub, @tor]

Examples

>>> g = gt.collection.data["karate"]
>>> clust = gt.local_clustering(g)
>>> print(gt.vertex_average(g, clust))
(0.5706384782..., 0.05869813676...)
Contents