FSM: Fast and scalable network motif discovery for exploring higher-order network organizations

Tao Wang, Jiajie Peng, Qidi Peng, Yadong Wang, Jin Chen

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

Networks exhibit rich and diverse higher-order organizational structures. Network motifs, which are recurring significant patterns of inter-connections, are recognized as fundamental units to study the higher-order organizations of networks. However, the principle of selecting representative network motifs for local motif based clustering remains largely unexplored. We present a scalable algorithm called FSM for network motif discovery. FSM is advantageous in twofold. First, it accelerates the motif discovery process by effectively reducing the number of times for subgraph isomorphism labeling. Second, FSM adopts multiple heuristic optimizations for subgraph enumeration and classification to further improve its performance. Experimental results on biological networks show that, comparing with the existing network motif discovery algorithm, FSM is more efficient on computational efficiency and memory usage. Furthermore, with the large, frequent, and sparse network motifs discovered by FSM, the higher-order organizational structures of biological networks were successfully revealed, indicating that FSM is suitable to select network representative network motifs for exploring high-order network organizations.

Original languageEnglish
Pages (from-to)83-93
Number of pages11
JournalMethods
Volume173
DOIs
StatePublished - Feb 15 2020

Bibliographical note

Publisher Copyright:
© 2019 Elsevier Inc.

Keywords

  • Biological network
  • Higher-order organization
  • Network motif

ASJC Scopus subject areas

  • Molecular Biology
  • General Biochemistry, Genetics and Molecular Biology

Fingerprint

Dive into the research topics of 'FSM: Fast and scalable network motif discovery for exploring higher-order network organizations'. Together they form a unique fingerprint.

Cite this