Random Walks on Complex Modular Networks

Abstract

Complex modular networks appear frequently, notably in the biological or social sciences. We focus on two current challenges regarding network modularity: the ability to identify (i) the modules of a given network, and (ii) the hub states as nodes with highest importance in terms of the communication between modules. Our approach towards these goals uses random walks as a mean to global analysis of the topology and communication structure of the network. We show how to adapt recent research regarding coarse graining of random walks. The resulting algorithms are based on spectral analysis of random walks and allow (A) an optimal identification of fuzzy assignments of nodes to modules, (B) computation of the fraction of the overall communication between modules supported by certain nodes, and (C) determination of the hubs as the nodes with the highest communication load.