A new method for quantifying network cyclic structure to improve community detection

Abstract

A distinguishing property of communities in networks is that cycles are more prevalent within communities than across communities. Thus, the detection of these communities may be aided through the incorporation of measures of the local "richness" of the cyclic structure. In this paper, we introduce renewal non-backtracking random walks (RNBRW) as a way of quantifying this structure. RNBRW gives a weight to each edge equal to the probability that a non-backtracking random walk completes a cycle with that edge. Hence, edges with larger weights may be thought of as more important to the formation of cycles. Of note, since separate random walks can be performed in parallel, RNBRW weights can be estimated very quickly, even for large graphs. We give simulation results showing that pre-weighting edges through RNBRW may substantially improve the performance of common community detection algorithms. Our results suggest that RNBRW is especially efficient for the challenging case of detecting communities in sparse graphs.

arXiv comment28 pages. his version previously appeared as arXiv:1910.01921 which was accidentally submitted as a new paper

References in corpus (18)

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• The clustering coefficient and community structure of bipartite networks
• Enhancing community detection using a network weighting strategy
• Cyclic Topology in Complex Networks
• Using Triangles to Improve Community Detection in Directed Networks
• Network clustering and community detection using modulus of families of loops
• The distribution of first hitting times of non-backtracking random walks on Erdős-Rényi networks