CommPlex: Community in MultiPlexes - Definition and a Suite of Algorithms for Analysis
摘要
Multiplexes (also termed Multilayer Networks or networks of networks) are useful for modeling data sets with multiple entity types, and relationships among them. The notion of a community is well-defined for simple graphs (or a monoplex/network) and is widely used for aggregate analysis on graphs. Several simple graph algorithms (e.g., Infomap, Louvain) for computing a community and algorithms for computing other metrics (e.g., centrality, substructure, etc.) exist as well. Although multilayer networks (MLNs) are used for modeling, the concept of a community and algorithms for its computation are lacking. Ideally, an MLN community definition should be comparable to the simple graph definition and be a generalization. As MLNs have structure in terms of layers, including inter-layer edges, it is important to define a community that includes its structure and semantics. The resulting community should also be an MLN. The focus of this paper is on heterogeneous MLN (or HeMLN), which is a type of MLN with explicitly defined inter-layer edges. In this paper, we introduce a community definition for HeMLNs that is structure-preserving and is also consistent with the traditional definition. Layer semantics are also preserved for drill-down and visualization. First, we define a community for any k connected layers of a HeMLN (termed k-community (1-community is the same as the traditional community on a simple graph or a layer of HeMLN.)) using binary composition. Then, we propose an algorithm for its computation using the concept of bipartite graphs. Further, we show how weight metrics can be customized to include the semantics of participating community characteristics. Our definition: i) leverages extant simple graph community computation algorithms, ii) composes partial results from different layers for computing HeMLN communities (i.e., uses the decoupling approach), iii) is customizable using weight metrics based on participating communities, and iv) is computationally efficient. We have experimentally validated the community concept (definition and computation) on several real-world and synthetic data sets.