Split Likelihood-based Method For Community Detection Of Multi-layer Networks

Network science has been widely used in computer science,statistics,social science and biology and other disciplines.Typical examples include social networks,transportation networks,power networks and communication networks.In recent years,the application of network science in practice has also been continuously deepened and expanded with the increase of network scale and network complexity and the continuous progress of network science technology and theory.Community structure is the most important network structure feature in the research of complex networks,and it is one of the important research directions in this field.Network community discovery plays a key role in the process of in-depth analysis of large-scale actual community structure.At present,the main task of network science is still focused on a single network.In practice,many networks do not exist in isolation,and there may be interdependence or cooperation and competition with other networks.Multi-layer networks simultaneously obtain multiple types of relationships between nodes,such as dynamic networks formed by these nodes at different times,and multi-layer social networks formed by different social software.In order to comprehensively utilize the structural information between slices in a multi-layer network and comprehensively study the shared communities of these nodes,people have proposed a variety of multi-layer community discovery methods instead of single-slice community discovery methods.Among these multi-layer community discovery methods,statistical methods have received more and more attention in recent years because they are very helpful in describing the generation mode of multi-layer networks.The stochastic block model(SBM),as a typical random graph generation model,has been widely used in network community discovery tasks.Since the theoretical optimization problem of community label recovery under SBM is NP-hard,accurate likelihood inference cannot be achieved.Based on SBM,the multi-layer stochastic block model(MLSBM)is a probabilistic model widely used to describe the structure of multi-layer communities in multi-layer networks.Its main idea is that all network layers have shared community allocation to this nodes,and the model parameters of each layer of the network can be set independently.In large-scale networks environment,accurate likelihood inference of MLSBM is also computationally infeasible.Thus,people have developed many approximation strategies to improve the computational efficiency.However,most of these methods still cannot be extended to large-scale networks.Thus,in order to solve the problem of community discovery in large-scale multi-layer networks,this paper generalizes the SL algorithm to multi-layer networks and proposes a fast multi-layer split likelihood algorithm.In this algorithm,we have established an inference function suitable for multi-slice networks,named the split likelihood function.By dividing the variables of the original SBM into two sets of random variables with independent and identical distributions to avoid the problem of intractable inference of the original observation likelihood,it is used to recover the shared community allocation of all network layers and estimate the parameters of all network layers in MLSBM,and the convergence of its parameters is proved.At the same time,this paper gives a proof of weak consistency for the ML-SL algorithm,providing a theoretical guarantee for the community discovery of the ML-SL algorithm.Moreover,there are many networks with hub nodes or those with substantial degrees of variation within communities in the reality.These networks do not satisfy the assumption of the stochastic block model,and ML-SL cannot be used at this time.In order to solve the problem of community discovery of such multi-layer networks,this paper proposes an improved version of the ML-SL algorithm,called conditional split likelihood algorithm(ML-CSL).Finally,we demonstrate the superiority of the proposed methods in terms of both the accuracy of community detection and computational efficiency through a large number of numerical experiments as well as two analyses of empirically obtained data.