Faster counting of complex network patterns by scanning network edges
Faster network motif discovery by counting isomorphic subtrees
Data Structures and Algorithms
Summary
Finding small, repeated connection patterns called motifs in large networks is very hard because some nodes connect to many others, causing huge numbers of possibilities. The authors created a faster way to count these motifs by breaking the network into cores and focusing on simpler tree-like structures on the network edges. They proved that an important counting step is very hard in theory, but their method still speeds up motif searches in real-world networks. Their tests on 11 different networks show substantial practical improvements.
What this means in practice
- •For network analysts: Count complex connection patterns faster in large real-world networks to identify structural motifs more efficiently.
- •For bioinformatics teams: Accelerate motif discovery in biological networks, aiding the understanding of cellular processes by more quickly identifying important substructures.
Authors
Tarek Tohme, Joshua A. Grochow
Abstract
We develop a new algorithm for counting the number of subgraphs of a network isomorphic to a given query graph (#SubgraphIsomorphism), motivated by network motif search. High-degree vertices (hubs), common in real-world networks, contribute to a combinatorial explosion in the number of subgraphs, making existing motif search algorithms intractable for motif sizes greater than $\approx 8$ on a wide variety of networks of interest. Our procedure leverages the $k$-core decomposition and a novel subtree-counting technique to quickly scan the periphery of a network. These two innovations allow our algorithm to significantly speed up its predecessors in practice, especially as most real-world networks have a relatively large periphery. We prove that #RootedSubtreeIsomorphism, a key subroutine in our algorithm, is #P-complete via a reduction from counting bipartite matchings. We provide analytic upper bounds on our algorithm's execution time, and evaluate its performance on 11 real-world networks of varying topologies.