An improved limited random walk approach for identification of overlapping communities in complex networks

摘要

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.