extended_clustering

graph_tool.clustering.extended_clustering(g, props=None, max_depth=3, undirected=False)

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.

See also

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