Online Program Home
My Program

Abstract Details

Activity Number: 79 - Statistical Analysis for Networks
Type: Contributed
Date/Time: Sunday, July 29, 2018 : 4:00 PM to 5:50 PM
Sponsor: Section on Statistical Learning and Data Science
Abstract #329489 Presentation
Title: New Methods for Incorporating Network Cyclic Structures to Improve Community Detection
Author(s): Behnaz Moradijamei* and Michael Higgins and Heman Shakeri
Companies: Kansas State University and KANSAS STATE UNIVERSITY and Kansas State University
Keywords: Cyclic topologies; modularity function; retraced non-backtracking random walk; loop modulus

A distinguishing property of communities in networks is that cycles are more prevalent within communities than across communities. Hence, the detection of these communities may be aided through the use of measures of the local ``richness'' of cyclic structures. We investigate the use of two methods for quantifying this richness---loop modulus (LM) and retraced non-backtracking random walks (RNBRW)---to improve the performance of existing community detection algorithms. LM solves a quadratic program to find an optimal allocation of edge usage across cycles to minimize cycle overlap, thereby giving a rigorous way to quantify the importance of edges. RNBRW, introduced for the first time in this paper, quantifies edge importance as the likelihood of an edge completing a cycle in a non-backtracking random walk. We argue that RNBRW provides an efficient and scalable heuristic approximation to LM. We give simulation results that suggest pre-weighting edges by the proposed methods can improve the performance of popular community detection algorithms substantially. Our methods are especially efficient for the challenging case of detecting communities in sparse graphs.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2018 program