Provides algorithms for calculation of clustering coefficients, aka. transitivity.
local_clustering  Return the local clustering coefficients for all vertices. 
global_clustering  Return the global clustering coefficient. 
extended_clustering  Return the extended clustering coefficients for all vertices. 
motifs  Count the occurrence of ksize nodeinduced subgraphs (motifs). 
motif_significance  Obtain the motif significance profile, for subgraphs with k vertices. 
Return the local clustering coefficients for all vertices.
Parameters:  g : Graph
prop : PropertyMap or string, optional
undirected : bool (default: True)


Returns:  prop : PropertyMap

See also
Notes
The local clustering coefficient [wattscollective1998] \(c_i\) is defined as
where \(k_i\) is the outdegree of vertex \(i\), and
is the set of outneighbours of vertex \(i\). For undirected graphs the value of \(c_i\) is normalized as
The implemented algorithm runs in \(O(V\left< k\right>^3)\) time, where \(\left< k\right>\) is the average outdegree.
If enabled during compilation, this algorithm runs in parallel.
References
[wattscollective1998]  (1, 2) D. J. Watts and Steven Strogatz, “Collective dynamics of ‘smallworld’ networks”, Nature, vol. 393, pp 440442, 1998. DOI: 10.1038/30918 
Examples
>>> g = gt.random_graph(1000, lambda: (5,5))
>>> clust = gt.local_clustering(g)
>>> print(gt.vertex_average(g, clust))
(0.006177777777777778, 0.0003696618407994121)
Return the global clustering coefficient.
Parameters:  g : Graph


Returns:  c : tuple of floats

See also
Notes
The global clustering coefficient [newmanstructure2003] \(c\) is defined as
The implemented algorithm runs in \(O(V\left< k\right>^3)\) time, where \(\left< k\right>\) is the average (total) degree.
If enabled during compilation, this algorithm runs in parallel.
References
[newmanstructure2003]  (1, 2) M. E. J. Newman, “The structure and function of complex networks”, SIAM Review, vol. 45, pp. 167256, 2003, DOI: 10.1137/S003614450342480 
Examples
>>> g = gt.random_graph(1000, lambda: (5,5))
>>> print(gt.global_clustering(g))
(0.006177777777777778, 0.0003700318726720911)
Return the extended clustering coefficients for all vertices.
Parameters:  g : Graph
props : list of PropertyMap objects, optional
max_depth : int, optional
undirected : bool, optional


Returns:  prop : list of PropertyMap objects

See also
Notes
The extended clustering coefficient \(c^d_i\) of order \(d\) is defined as
where \(d_G(u,v)\) is the shortest distance from vertex \(u\) to \(v\) in graph \(G\), and
is the set of outneighbours 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{maxdepth}})\) worst time, where \(\left< k\right>\) is the average outdegree.
If enabled during compilation, this algorithm runs in parallel.
References
[abdoclustering]  A. H. Abdo, A. P. S. de Moura, “Clustering as a measure of the local topology of networks”, arXiv: physics/0605235 
Examples
>>> g = gt.random_graph(1000, lambda: (5,5))
>>> clusts = gt.extended_clustering(g, max_depth=5)
>>> for i in range(0, 5):
... print(gt.vertex_average(g, clusts[i]))
...
(0.00421, 0.00041685103920811916)
(0.027226666666666666, 0.0010073522830778825)
(0.11549166666666667, 0.002081399085417734)
(0.41280666666666666, 0.0029479221231987185)
(0.4205716666666666, 0.003156465741141506)
Count the occurrence of ksize nodeinduced subgraphs (motifs). A tuple with two lists is returned: the list of motifs found, and the list with their respective counts.
Parameters:  g : Graph
k : int
p : float or float list (optional, default: 1.0)
motif_list : list of Graph objects, optional
return_maps : bool (optional, default False)


Returns:  motifs : list of Graph objects
counts : list of ints
vertex_maps : list of lists of PropertyMap objects

See also
Notes
This functions implements the ESU and RANDESU algorithms described in [wernickeefficient2006].
If enabled during compilation, this algorithm runs in parallel.
References
[wernickeefficient2006]  (1, 2, 3, 4) S. Wernicke, “Efficient detection of network motifs”, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 3, Issue 4, Pages 347359, 2006. DOI: 10.1109/TCBB.2006.51 
[inducedsubgraphisomorphism]  http://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem 
Examples
>>> g = gt.random_graph(1000, lambda: (5,5))
>>> motifs, counts = gt.motifs(gt.GraphView(g, directed=False), 4)
>>> print(len(motifs))
52
>>> print(counts)
[29259, 29111, 28420, 28618, 163659, 96696, 96821, 31366, 295, 162, 185, 257, 58, 74, 562, 300, 80, 240, 273, 112, 379, 167, 329, 536, 605, 641, 176, 540, 340, 317, 298, 87, 306, 275, 252, 9, 3, 11, 5, 9, 7, 2, 2, 1, 3, 1, 2, 1, 2, 1, 1, 1]
Obtain the motif significance profile, for subgraphs with k vertices. A tuple with two lists is returned: the list of motifs found, and their respective zscores.
Parameters:  g : Graph
k : int
n_shuffles : int (optional, default: 100)
p : float or float list (optional, default: 1.0)
motif_list : list of Graph objects (optional, default: None)
threshold : int (optional, default: 0)
self_loops : bool (optional, default: False)
parallel_edges : bool (optional, default: False)
full_output : bool (optional, default: False)
shuffle_model : string (optional, default: “uncorrelated”)


Returns:  motifs : list of Graph objects
zscores : list of floats

See also
Notes
The zscore \(z_i\) of motif i is defined as
where \(N_i\) is the number of times motif i found, and \(N^s_i\) is the count of the same motif but on a shuffled network. It measures how many standard deviations is each motif count, in respect to an ensemble of randomly shuffled graphs with the same degree sequence.
The zscores values are not normalized.
If enabled during compilation, this algorithm runs in parallel.
Examples
>>> from numpy import random
>>> random.seed(10)
>>> g = gt.random_graph(100, lambda: (3,3))
>>> motifs, zscores = gt.motif_significance(g, 3)
>>> print(len(motifs))
11
>>> print(zscores)
[0.04162670293683441, 0.046769781223679897, 0.55888261369689918, 0.82906624302416043, 0.41384527710386287, 0.42070845824900477, 1.3262411347517733, 1.82, 0.13, 0.37, 0.22]