Random Walks on Complex Modular Networks

Natasa Djurdjevac , Sharon Bruckner, Tim OF Conrad, Christof Schuette
Fachbereich Mathematik und Informatik
Institut fuer Mathematik
Freie Universitaet Berlin
{djurdjev,sharonb,conrad,schuette}@math.fu-berlin.de
Received 20 February, 2011; accepted in revised form 10 March, 2011
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 communi-
cation load.

 

Scroll to Top