Tarek Tohme1 and Joshua A. Grochow2
Abstract: We develop a new algorithm for counting the number of subgraphs of a network isomorphic to a given query graph, 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 7 on a wide variety of networks of interest. Our procedure leverages the k-core decomposition and a novel subtree-counting procedure to quickly scan the periphery of a network. These two innovations make our algorithm significantly faster than its predecessor in practice, especially as most real-world networks have a relatively large periphery (1-shell). More specifically, we prove that #RootedSubtreeIsomorphism is #P-complete via a reduction from counting bipartite matchings. We build on this result to propose a fast subgraph-counting algorithm, provide analytic upper bounds on its execution time, and evaluate its performance on a corpus of real network data.
PDF and arXiv link coming soon!
[1] American University of Beirut, Beirut, Lebanon
[2] Departments of Computer Science and Mathematics, University of Colorado Boulder, Boulder, CO, USA
Last updated: Dec 14, 2020