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

Return the extended clustering coefficients for all vertices.


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

proplist of VertexPropertyMap objects

List of vertex properties containing the clustering coefficients.

See also


local clustering coefficient


global clustering coefficient


motif counting


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.



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


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