Global Spectral Clustering in Dynamic Networks

• Activity Number: 613 - Recent Advances in Network Data Inference
• Type: Topic Contributed
• Date/Time: Thursday, August 2, 2018 : 8:30 AM to 10:20 AM
• Sponsor: Social Statistics Section
• Author(s): David Choi* and Fuchen Liu and Kathryn Roeder
• Companies: Carnegie Mellon University and Carnegie Mellon University and Carnegie Mellon University
• Keywords: networks; community detection; dynamic networks; nonconvex optimization; spectral methods; clustering

Abstract

In this talk, we present a new method (PisCES) for finding time-varying community structure in dynamic networks. The method implements degree-corrected spectral clustering, with a smoothing term to promote similarity across time periods. We prove that this method converges to the global solution of a nonconvex optimization problem, which can be interpreted as the spectral relaxation of a smoothed K-means clustering objective. We also show that smoothing is applied in a time-varying and data-dependent manner; for example, when a drastic change point exists in the data, smoothing is automatically suppressed at the time of the change point. Finally, we show that the detected time-varying communities can be effectively visualized through the use of sankey plots.