Overlapped Community Detection in Multiplex Networks

Abstract

Community detection is a fast-growing field in computer science, and it is easy to see why, as it enables the breakdown of complex networks into their principal components, which may accelerate the understanding of them. These intricate network structures frequently involve several relations and various kinds of component interactions. To fully leverage the dataset information, these complex systems are commonly represented as multiplex networks consisting of multiple layers to more explicitly model their multi-relational structure. In this thesis, we propose several extensions of two mono-layered community detection methods, namely belief propagation and cluster-driven low-rank matrix completion, in order to generalize them to the case of multiplex networks. These extensions include a flattening technique that converts the multiplex network into a mono-layered network by projecting the edges of each layer onto a single layer; a layer-by-layer technique that determines a consensus community structure by assembling the community structures obtained by running the algorithm for each layer; and lastly, a global extension that works directly on the multiplex network itself. The extended versions show an enhanced ability to detect communities in multiplex networks compared to their mono-layered equivalent; the increased detectability is even more prominent in sparse multiplex networks with a high number of overlaps.