Weighted network motifs as random walk patterns

Abstract

Over the last two decades, network theory has shown to be a fruitful paradigm in understanding the organization and functioning of real-world complex systems. One technique helpful to this endeavor is identifying functionally influential subgraphs, shedding light on underlying evolutionary processes. Such overrepresented subgraphs, motifs , have received much attention in simple networks, where edges are either on or off. However, for weighted networks, motif analysis is still undeveloped. Here, we proposed a novel methodology—based on a random walker taking a fixed maximum number of steps—to study weighted motifs of limited size. We introduce a sink node to balance the network and allow the detection of configurations within an a priori fixed number of steps for the random walker. We applied this approach to different real networks and selected a specific null model based on maximum-entropy to test the significance of weighted motifs occurrence. We found that identified similarities enable the classifications of systems according to functioning mechanisms associated with specific configurations: economic networks exhibit close patterns while differentiating from ecological systems without any a priori assumption.

Keywords

• weighted motifs
• random walk
• null models
• complex networks
• weighted networks