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.
|Number of pages||11|
|State||Published - Feb 15 2020|
Bibliographical noteFunding Information:
This project is supported by US NSF ABI (grant nos. 1458556, 1716340), US DOE BES (grant no. DEFG0291ER20021), NSFC (grant nos. 61702421, 61332014), National Key Research and Development Program of China (Nos: 2017YFC0907503 and 2017YFC1201201). This manuscript is based on an earlier work presented at the IEEE International Conference on Bioinformatics and Biomedicine (BIBM-2018).
© 2019 Elsevier Inc.
- Biological network
- Higher-order organization
- Network motif
ASJC Scopus subject areas
- Molecular Biology
- Biochemistry, Genetics and Molecular Biology (all)