motifs

Contents

motifs#

graph_tool.clustering.motifs(g, k, p=1.0, motif_list=None, return_maps=False)[source]#

Count the occurrence of k-size node-induced subgraphs (motifs). A tuple with two lists is returned: the list of motifs found, and the list with their respective counts.

Parameters:
gGraph

Graph to be used.

kint

number of vertices of the motifs

pfloat or float list (optional, default: 1.0)

uniform fraction of the motifs to be sampled. If a float list is provided, it will be used as the fraction at each depth \([1,\dots,k]\) in the algorithm. See [wernicke-efficient-2006] for more details.

motif_listlist of Graph objects, optional

If supplied, the algorithms will only search for the motifs in this list (or isomorphisms).

return_mapsbool (optional, default False)

If True, a list will be returned, which provides for each motif graph a list of vertex property maps which map the motif to its location in the main graph.

Returns:
motifslist of Graph objects

List of motifs of size k found in the Graph. Graphs are grouped according to their isomorphism class, and only one of each class appears in this list. The list is sorted according to in-degree sequence, out-degree-sequence, and number of edges (in this order).

countslist of ints

The number of times the respective motif in the motifs list was counted

vertex_mapslist of lists of VertexPropertyMap objects

List for each motif graph containing the locations in the main graph. This is only returned if return_maps == True.

See also

motif_significance

significance profile of motifs

local_clustering

local clustering coefficient

global_clustering

global clustering coefficient

extended_clustering

extended (generalized) clustering coefficient

Notes

This functions implements the ESU and RAND-ESU algorithms described in [wernicke-efficient-2006].

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

[wernicke-efficient-2006] (1,2)

S. Wernicke, “Efficient detection of network motifs”, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 3, Issue 4, Pages 347-359, 2006. DOI: 10.1109/TCBB.2006.51 [sci-hub, @tor]

Examples

>>> g = gt.random_graph(1000, lambda: (5,5))
>>> motifs, counts = gt.motifs(gt.GraphView(g, directed=False), 4)
>>> print(len(motifs))
11
>>> print(counts)
[115626, 390445, 662, 763, 2816, 1686, 776, 10, 5, 11, 3]
Contents