Efficiently Enumerating All Connected Induced Subgraphs of a Large Molecular Network
summary
Algorithm enumerates every connected induced subgraph on graphs with thousands of nodes and tens of thousands of edges by using anchor vertices and a hybrid extension/cloning search that generates each subgraph exactly once, guarantees completeness and no overhead, and eliminates redundant rejections per anchor. Benchmarks on human PPI and citation networks show a large runtime gap versus DFS depth‑first enumeration when the instance is hard, and the method speeds up a glioblastoma subnetwork search that produced protein‑level validated markers; original MATLAB prototype is messy but the cleaned implementation is practical.
AI-written summary · about
chapters (18)
- 0:00Start
- 2:39Applications
- 5:34Bounding Combinatorial Dysregulation
- 6:09Efficient Enumeration
- 8:25Redundant Rejections
- 9:02Existing Algorithms
- 10:33Reverse Search
- 11:17Our Algorithm: BDDE
- 12:13Anchor Vertices
- 14:18Pruning The Search Space
- 15:51Joining Local Search Trees
- 16:40Correctness
- 17:21Simulation Results
- 19:13arXiv Network
- 19:31Runtime (secs.)
- 19:58Performance on CRANE
- 21:01Conclusion
- 21:43Acknowledgments