  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.
