Higher-Order Random Walkers: Blob Diffusion on Complex Networks

Abstract: Random walks are among the most fundamental types of dynamics on networks. They have not only been used as the basis for community detection (Rosval & Bergstrom, 2008), centrality measures (Bring & Page, 1998) and opinion formation (Cooper etal., 2013), but also have been the subject of intensive study in their own right (Masuda, Porter, & Lambiotte, 2017). In this work, we extend the notion of a random walker to higher-order objects of arbitrary size. We refer to this dynamical process as subgraph diffusion or more colloquially blob diffusion. In this framework, diffusion involves a connected subgraph (a “blob”), \(B_t\) with size \(b\) traversing the network. A blob of size b occupies not only a single node but an entire connected subgraph of size \(b\). At every timestep, the blob transitions into a new configuration \(B_(t+1)\) subject to the constraint that the new configuration retains \(b-1\) nodes in \(B_t\) while again forming a connected subgraph. Note as well that a classic random walker in this framework is simply a blob of size \(b=1\). While dynamics on the microscopic scale of single nodes and the macroscale of whole networks have been thoroughly explored, dynamics of mesoscopic objects in networks have seen far less attention. Here we explicitly focus on the behavior of the interaction of a mesoscopic object—the blob—with the structure of the underlying network. We examine the properties of this novel dynamical system and explore its connections to previous work on community detection (Derényi, Palla, & Vicsek, 2005; Rosvall et al., 2014), motif counting (Han & Sethu, 2016) and higher-order random walks (Battiston et al, 2020). Moreover, we investigate the mereological properties of these higher-order random walkers. This means we study the relationship between the blob and its constituents. From this perspective, we can think of blob diffusion as a toy model for context dependence in complex systems and the role of the individual in the collective. In our view blob diffusion represents a new family of dynamics on networks that has both theoretical importance and practical relevance.

References

• M. Rosvall and C. T. Bergstrom; Proc. Natl. Acad. Sci. 105, 1118 (2008).
• S. Brin and L. Page; Comput. Netw. ISDN Syst. 30, 107 (1998).
• C. Cooper et al.; SIAM J. Discrete Math. 27, 1748 (2013).
• N. Masuda, M. A. Porter & R. Lambiotte; Phys. Rep. 716–717, 1 (2017).
• M. Rosvall et al.; Nat. Commun. 5, 1 (2014).
• I. Derényi, G. Palla, & T. Vicsek; Phys. Rev. Lett. 94, 160202 (2005).
• G. Han & H. Sethu;2016 IEEE 16th ICDM (2016), pp. 181–190.
• F. Battiston et al.; Phys. Rep. 874, 1 (2020).