Community detection for multi-layer social network based on local random walk
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.
Section snippets
Related works
With the fast development of social network, related problems have become the research hotspot recently, including the structural characteristics of social network and the network formation model. More and more researchers have given priority to the research on social network that can reflect the diversity of interpersonal relationship. Watts defined the concept of small-world network for the first time [9], Barabasi proposed the concept of scale-free network [10], and these two important
Community detection algorithm for multi-layer social network based on local random walk
In this part, first of all, we described the multi-layer network, and then proposed the community detection algorithm for multi-layer social network based on local random walk (MLCDL). This algorithm mainly consists of two stages: the community core node identification stage and the core node clustering stage based on random walk. Finally, obtain the algorithm framework of local community detection for multi-layer network according to the core node.
Experimental results
Modularity is a common optimization method for detection of community structure in the network, and it is designed to measure the intensity of dividing network into different modules (also called group, cluster or community). The network with high modularity degree has dense node connection within the module, while the node connection between different modules is sparse. In the experiments in this section, we used four actual multi-layer network datasets to compare the performance of the MRLCD
Conclusion
In this paper, local community detection was conducted in the multi-layer network. First of all, the core node in multi-layer network was obtained according to the node repeatability of multi-layer network. Then, the similarity trust between nodes was computed according to the similarity relation between nodes. Finally, the node random walk method was used to determine the clustering coefficient between nodes in this study. Local community detection was conducted according the clustering
Conflict of interest
There is no conflict of interest.
Acknowledgement
I am very grateful to Roberto Interdonato of the University of Calabria for his unselfish guidance to my paper. He provided Literature [23], experimental code and data set, and provided data and code for comparative experiments.
Funding
This word was by the Major Project of Fundamental Research of Xinjiang Corps [2016AC015], the Applied Basic Research Project of Qinghai Province [No: 2018-ZJ-707], National Social Science Fund of China [14ZDB153], and the National Science Foundation of China [61572355].
References (46)
Cognitive social structures
Social Networks
(1987)- et al.
Community detection in networks: A user guide
Phys. Rep.
(2016) Community detection in graphs
Phys. Rep.
(2010)- et al.
The structure and dynamics of multilayer networks
Phys. Rep.
(2014) - et al.
Link prediction in complex networks: A survey
Phys. A Stat. Mech. Appl.
(2011) A measure of betweenness centrality based on random walks
Social Networks
(2005)- et al.
Random graphs with arbitrary degree distributions and their applications
Phys. Rev. E
(2001) - et al.
Networks of networks: The last frontier of complexity
(2014) - et al.
Social Network Analysis: Methods and Applications
(1994) Social network analysis: methods and applications
Am. Ethnol.
(1995)
Reply to review of “In the Ngombe tradition: continuity and change in the Congo”
Am. Anthropol.
The Politics of Tradition: Continuity and Change in Northern Nigeria, 1946–1966. The Politics of Tradition Continuity and Change in Northern Nigeria, 1946–1966 /
The politics of tradition: continuity and change in Northern Nigeria 1946–1966
Afr. Historical Stud.
Emergence of scaling in random networks
The Structure and Dynamics of Networks
Catastrophic cascade of failures in interdependent networks
Nature
Congestion induced by the structure of multiplex networks
Phys. Rev. Lett.
Structural reducibility of multilayer networks
NatureCommun.
Emergence of network features from multiplexity
Sci. Rep.
Multiplexity versus correlation: the role of local constraints in real multiplexes
Sci. Rep.
Exploring intracity taxi mobility during the holidays for location-based marketing
Mobile Inf. Syst.
Quantifying dynamical spillover in co-evolving multiplex networks
Sci. Rep.
Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems
Comput. Sci.
Cited by (21)
Community detection in multi-relational directional networks
2023, Journal of Computational ScienceThe trade-off between topology and content in community detection: An adaptive encoder–decoder-based NMF approach
2022, Expert Systems with ApplicationsAttributed multiplex graph clustering: A heuristic clustering-aware network embedding approach
2022, Physica A: Statistical Mechanics and its ApplicationsCitation Excerpt :However, some valuable information (such as the interactions or relevance between different relationships) will be ignored. Direct methods, which are often extensions of graph clustering methods for single-layer graph networks (such as modularity-based methods [22], algebraic methods [23], probabilistic methods [24], and graph-feature-based methods [25]), can be directly used on the multi-relationship graph networks directly. However, most of these above methods overlook the node attributes, which are heterogeneous information compared to the graph network topology.
DarkNetExplorer (DNE): Exploring dark multi-layer networks beyond the resolution limit
2021, Decision Support SystemsCitation Excerpt :Like Bahulkar et al. [55], Saxena et al. [9] also used Louvain [38] to identify the communities in the aggregated weighted network. Both have their shortcomings, according to Li et al. [67], around the mutual inference among layers of a network. By aggregating the layers for analysis, the resultant network is weakened owing to the loss of structural topology information in each layer.
Multi-sector partnerships in the urban development context: A scoping review
2020, Journal of Cleaner ProductionCitation Excerpt :Choosing the most suitable partnerships with the relevant sectors is crucial. However, there is a lack of summaries of the typical modes concerning choice of sectors for a multi-sector partnership, as well as analyses and comparative studies among the various modes of partnerships, which makes it difficult to choose an appropriate one for a specific project (Liu et al. 2016; Young and Brans, 2017; Knoeri et al., 2016; Li et al., 2018). To solve this gap, this paper will identify the main modes of multi-sector partnerships, and provide analysis concerning their applicable sectors, level of maturity, suitable situations, as well as advantages and disadvantages.
Spatiotemporal analysis of global grain trade multilayer networks considering topological clustering
2024, Transactions in GIS