Community detection for multi-layer social network based on local random walk

Abstract

With the fast development of information network, the scale of social network has become very significant, and it has become more difficult to obtain the information of entire network. In addition, because current mining method for complicated network community utilizes the information of node link or property, which cannot effectively detect the community with dense member links and highly similar properties. As a result, most current algorithms are impractical for online social network with large scale, and we propose a community detection algorithm for multi-layer social network based on local random walk (MRLCD); this algorithm determines the core node based on the repeatability of multi-layer nodes. It expands from a core node, has local random walk in multi-layer network, identifies and controls the random walk scope of node based on the intra-layer and interlayer trust. During the walk process, the clustering coefficient of nodes to be combined is comprehensively compared to further complete a local community search, and the optimal local community search is obtained through multiple iterations. Finally, the multi-layer modularity is used as the indicator for measurement and evaluation of algorithm performance, and its performance is compared with other network clustering algorithms such as GL, LART and PMM through four actual multi-layer network datasets. The MRLCD algorithm can autonomously explore the local community structure of given node, and effectively improve the stability and accuracy for local community detection in multi-layer social network.

Introduction

After more than 10 years’ fast development of network science, substantial research results have been achieved, and more complete and systematic disciplinary framework and theoretical system have been gradually established [1]. As researches on network science have become increasingly more mature, the research direction has started to transfer from simple graph theory to more complicated real system. In the meantime, the focus has also gradually transferred from single isolated network to coupling network or multi-layer with mutual influence on each other, or network within network [2]. This is because different complicated systems are mutually related in the real world. In the social network, the connection edges can be classified according to the property of interpersonal relationship or the behavior represented by interpersonal relationship [3], [4]. It is an extremely simplified approach for real application to depict complicated social system with simple network, because the participants in network are only connected through one relationship type. In the past several decades, not only the sociologists have realized that it is very necessary to study social relation by building diverse social network among the same individual sets based on different relation types [5], the anthropologists’ researches have also proved that it is necessary to consider diverse types of social relation [6], [7], [8]. Therefore, a new community detection method for multi-layer network has become a new topic.

With the continuous development of multi-layer social network, it has become more and more difficult to obtain the data of entire network. Even though we may obtain the global structural data, the computational cost might be too high to bear, and as a result, current community detection method cannot be applied in reality. Therefore, the local community detection method which conducts community detection of multi-layer network by only obtaining local network information has become very popular. In order to more reasonably analyze the user community organization under the environment of multi-layer social network, the community detection method for multi-layer social network based on local random walk has been proposed.

In this paper, according to the intra-layer and interlayer node connection property in multi-layer social network, we proposed the community detection method for multi-layer social network based on local random walk. From the perspective of multi-layer global network, this method was used to find multi-layer local core node based on the trust relationship. Then, according to the trust relationship between nodes, the conditional probability model based on random walk and the trust between nodes on the same layer and different layers in the social network environment were utilized to decide whether the node is in the local community. Through different random walk, we computed the probability of unclustered node belonging to each community based on different clustering coefficients, and added this unclustered node to the most probable community. Finally, we optimized the clustered community, and through massive experiments with actual datasets from MIT Media Lab, EU-AIR and CS-AARHUS, we proved the effectiveness and efficiency of our method. We found that in data set with significant trust, our method can be used to identify communities of equal or higher quality in these datasets.

This paper has the following structure. In Section 2, we reviewed related works of the basic theory of community detection for multi-layer social network and the local community detection theory based on random walk. Section 3 summarized the local community detection method and model for multi-layer network based on local random walk. Section 4 introduced the tests and performance evaluation based on actual multi-layer network and real mobile multi-layer network. Section 5 summarized this paper, and proposed suggestions for future research.