# extended_clustering#

graph_tool.clustering.extended_clustering(g, props=None, max_depth=3, undirected=False)[source]#

Return the extended clustering coefficients for all vertices.

Parameters:
gGraph

Graph to be used.

propslist of VertexPropertyMap objects (optional, default: None)

list of vertex property maps where results will be stored. If specified, this parameter will also be the return value.

max_depthint (optional, default: 3)

Maximum clustering order.

undirectedboolean (optional, default: False)

Calculate the undirected clustering coefficients, if graph is directed (this option has no effect if the graph is undirected).

Returns:
proplist of VertexPropertyMap objects

List of vertex properties containing the clustering coefficients.

local_clustering

local clustering coefficient

global_clustering

global clustering coefficient

motifs

motif counting

Notes

The extended clustering coefficient $$c^d_i$$ of order $$d$$ is defined as

$c^d_i = \frac{\left|\right\{ \{u,v\}; u,v \in N_i | d_{G(V\setminus \{i\})}(u,v) = d \left\}\right|}{{\left|N_i\right| \choose 2}},$

where $$d_G(u,v)$$ is the shortest distance from vertex $$u$$ to $$v$$ in graph $$G$$, and

$N_i = \{v_j : e_{ij} \in E\}$

is the set of out-neighbors of $$i$$. According to the above definition, we have that the traditional local clustering coefficient is recovered for $$d=1$$, i.e., $$c^1_i = c_i$$.

The implemented algorithm runs in $$O(|V|\left<k\right>^{2+\text{max-depth}})$$ worst time, where $$\left< k\right>$$ is the average out-degree.

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

[abdo-clustering]

A. H. Abdo, A. P. S. de Moura, “Clustering as a measure of the local topology of networks”, arXiv: physics/0605235

Examples

>>> g = gt.collection.data["karate"]
>>> clusts = gt.extended_clustering(g, max_depth=5)
>>> for i in range(0, 5):
...    print(gt.vertex_average(g, clusts[i]))
...
(0.5706384782076..., 0.05869813676256...)
(0.3260389360735..., 0.04810773205917...)
(0.0530678759917..., 0.01513061504691...)
(0.0061658977316..., 0.00310690511463...)
(0.0002162629757..., 0.00021305890271...)