Efficient Counting of Network Motifs

Download Now Date Added: Apr 2010
Format: PDF

Counting network motifs has an important role in studying a wide range of complex networks. However, when the network size is large, as in the case of Internet Topology and WWW graphs counting the number of motifs becomes prohibitive. Devising efficient motif counting algorithms thus becomes an important goal. In this paper, the authors present efficient counting algorithms for 4- node motifs. They show how to efficiently count the total number of each type of motif, and the number of motifs adjacent to a node. They further present a new algorithm for node position-aware motif counting, namely partitioning the motif count by the node position in the motif.