Community Detection on Multi-layer Networks with Inter-layer Dependence

考慮依賴關係的多層網絡社區發現

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date26 Jul 2022

Abstract

Studying the community structure, which is also called community detection has attracted tremendous interests in network analysis in the past few decades. Finding a precise partition of a set of nodes according to their interaction networks and designing a computationally efficient and scalable optimization algorithm are two crucial points of this topic. Massive efforts have been paid in this area in the past forty years. However, most existing methods are focused on single-layer networks and methods for multi-layer networks are still in their infancy. Moreover, in the existing community detection methods for multi-layer networks, dependence across layers is seldom considered because incorporating dependence may significantly enhance the difficulty of computation. Therefore, developing a computationally efficient and scalable optimization algorithm on multi-layer networks which also incorporates the dependence relationship across layers is really demanding and promising.

In the first part of the thesis, we propose stochastic block Ising model (SBIM) and develop two approximate algorithms built under the framework of variational EM algorithm and the profile-pseudo likelihood algorithm, with both algorithms taking dependence across layers into account. Specifically, under the assumption of stochastic block model, we apply Ising model to incorporate the dependence across layers and treat the edge in each layer as the predictor of the edges in other layers. Under the framework of variational EM algorithm, a lower bound of the objective function is considered, and the parameters are restricted to a smaller space to facilitate the computation. And under the framework of profile-pseudo likelihood method, row labels and column labels are decoupled, and a lower bound of the objective function is optimized. By this means, the algorithms developed are computationally efficient, and can be scaled to networks with large size and large number of layers. We compare two algorithms in terms of numerical performance and computational cost, analyzing their advantages and drawbacks, and then compare SBIM against some existing community detection methods. We will show our proposed method outperforms the existing community detection methods significantly in both simulated examples and real-life Yeast Saccharomyces cerevisiae data.

In the second part of the thesis, we propose stochastic block graphical model (SBGM) for multi-layer continuous networks. The graphical model is used by SBGM to characterize the dependence across layers, which overcomes some deficiencies of SBIM for community detection on multi-layer continuous networks. Then we develop an algorithm under the framework of variational EM algorithm, we will show the proposed method outperforms the existing community detection methods, including SBIM, significantly in both simulated examples and real-life Yeast Saccharomyces cerevisiae data.