Markov random walk under constraint for discovering overlapping communities in complex networks

Abstract

Detection of overlapping communities in complex networks has motivated recent research in the relevant fields. Aiming this problem, we propose a Markov dynamics based algorithm, called UEOC, which means, 'unfold and extract overlapping communities'. In UEOC, when identifying each natural community that overlaps, a Markov random walk method combined with a constraint strategy, which is based on the corresponding annealed network (degree conserving random network), is performed to unfold the community. Then, a cutoff criterion with the aid of a local community function, called conductance, which can be thought of as the ratio between the number of edges inside the community and those leaving it, is presented to extract this emerged community from the entire network. The UEOC algorithm depends on only one parameter whose value can be easily set, and it requires no prior knowledge on the hidden community structures. The proposed UEOC has been evaluated both on synthetic benchmarks and on some real-world networks, and was compared with a set of competing algorithms. Experimental result has shown that UEOC is highly effective and efficient for discovering overlapping communities.

21 pages, 8 pages, 2 tables

References in corpus (21)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Random graphs with arbitrary degree distributions and their applications
• Comparing community structure identification
• Defining and identifying communities in networks
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Self-similar community structure in organisations
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Detect overlapping and hierarchical community structure in networks
• Line Graphs, Link Partitions and Overlapping Communities
• A Local Method for Detecting Communities
• Clique Graphs and Overlapping Communities
• Line Graphs of Weighted Networks for Overlapping Communities
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Taxonomy and clustering in collaborative systems: the case of the on-line encyclopedia Wikipedia

Cited by in corpus (7)

• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
• Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach
• Identifying multi-scale communities in networks by asymptotic surprise
• Detecting Overlapping Communities from Local Spectral Subspaces
• Community detection based on significance optimization in complex networks
• Overlapping Community Detection via Local Spectral Clustering