An improved limited random walk approach for identification of overlapping communities in complex networks
- PDF / 2,281,875 Bytes
- 20 Pages / 595.276 x 790.866 pts Page_size
- 8 Downloads / 196 Views
An improved limited random walk approach for identification of overlapping communities in complex networks Sondos Bahadori 1 & Parham Moradi 2 & Hadi Zare 3 Accepted: 1 October 2020 # Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Detection of community structures in complex networks provides an effective tool for studying the relationships between nodes and revealing the hidden structures. In many real applications, the communities overlap, which means that the nodes can belong to different communities. Recently, random walk methods have been successfully applied for identification of overlapping communities in social networks. However, most of the existing random-walk-based methods require information on the entire network, which is difficult to obtain. Moreover, most networks have gained very large scales with the rapid development of Internet technologies, and it is impractical to scale the existing works for online social networks. Another issue concerning the existing methods is the need for information on the number of communities before the algorithm begins, which is impossible to meet for most real-world networks. To resolve the above issues, a random walk method is proposed in this paper for detection of overlapping community structures in complex networks. The proposed method employs the Markov transition matrix to calculate the transferability of the agent from one node to the others. These probabilities are then used as an attribute vector and feature set for each node, and the feature sets are used for identification of initial communities. Nodes that are available in the feature sets of more than one community, or exhibit high ratios of neighborhood with the other communities are identified as overlapping nodes. The proposed method is examined on various real-world and synthetic datasets. The results reported in terms of various evaluation metrics demonstrate its high efficiency as compared to the existing works. Keywords Overlapping community detection . Complex network . Random walk . Node feature set . Neighborhood ratio
1 Introduction Many real-world systems in various domains, such as biology, sociology, and power systems, can be modeled as networks. A common approach to analysis of such networks is to reveal their hidden community structures while attempting to extract * Parham Moradi [email protected] Sondos Bahadori [email protected] Hadi Zare [email protected] 1
Department of Computer Engineering, Sanandaj Bracnch, Islamic Azad University, Sanandaj, Iran
2
Department of Computer Engineering, University of Kurdistan, Sanandaj, Iran
3
Faculty of New Sciences and Technologies, University of Tehran, Tehran, Iran
the patterns. In general, a community is considered as a set of nodes with relatively high intra-connection and low inter-connection. Community detection methods have been applied in many real-world applications such as sentiment analysis [1], recommender systems [2], skill formation in intelligent robots [3, 4], discovery of opinion leade
Data Loading...
