Identifying Representative Network Motifs for Inferring Higher-order Structure of Biological Networks

Abstract

Network motifs are recurring significant patterns of inter-connections, which 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 accelerates the motif discovery process by effectively reducing the number of times to do subgraph isomorphism labeling. Multiple heuristic optimizations for subgraph enumeration and subgraph classification are also adopted in FSM to further improve its performance. Experimental results show that FSM is more efficient than the compared models on computational efficiency and memory usage. Furthermore, our experiments indicate that large and frequent network motifs may be more appropriate to be selected as the representative network motifs for discovering higher-order organizational structures in biological networks than small or low-frequency network motifs.