Speaker: Lucas Jeub, Postdoctoral Fellow, School of Informatics & Computing, Indiana University

Title: Local Communities, Mesoscopic Structure, and Multilayer Networks

Date: 09/12/2016

Time: 11:30 am

Room: Informatics East 322

Abstract: There are many methods to detect dense “communities” of nodes in networks,  and there are now several methods to detect communities in multilayer networks. One way to define a community is as a set of nodes that trap a diffusion-like dynamical process (usually a random walk) for a long time. In this view, communities are sets of nodes that create bottlenecks to the spreading of a dynamical process on a network. We analyze the local behavior of different random walks on synthetic and empirical monolayer and multiplex networks (the latter are multilayer networks in which different layers correspond to different types of edges). We show that bottlenecks to random walks can reveal interesting mesoscale structure in networks that go beyond classical communities. There are different ways to generalize a random walk to multilayer networks.  We show that they have very different bottlenecks that hence correspond to rather different notions of what it means for a set of nodes to be a good community. This has direct implications for the behavior of community-detection methods that are based on these random walks. The ill-defined nature of the community-detection problem makes it crucial to develop generative models of networks to use as a common test of community-detection tools. For mono-layer networks different types of benchmark models are available. We develop a family of benchmarks for detecting mesoscale structures in multilayer networks by introducing a generative model that can explicitly incorporate dependency structure between layers. Our benchmark provides a standardized set of null models, together with an associated set of principles from which they are derived, for studies of mesoscale structures in multilayer networks. We discuss the parameters and properties of our generative model, and we illustrate its use by comparing a variety of community-detection methods.