Synchronization over $Z_2$ and community detection in multiplex signed networks with constraints

Abstract

Finding group elements from noisy measurements of their pairwise ratios is also known as the group synchronization problem, first introduced in the context of the group SO(2) of planar rotations, whose usefulness has been demonstrated recently in engineering and structural biology. Here, we focus on synchronization over ${\mathbb{Z}}_2$, and consider the problem of identifying communities in a multiplex network when the interaction between the nodes is described by a signed (possibly weighted) measure of similarity, and when the multiplex network has a natural partition into two communities. When one has the additional information that certain subsets of nodes represent the same unknown group element, we consider and compare several algorithms based on spectral, semidefinite programming (SDP) and message passing algorithms. In other words, all nodes within such a subset represent the same unknown group element, and one has available noisy pairwise measurements between pairs of nodes that belong to different non-overlapping subsets. Following a recent analysis of the eigenvector method for synchronization over SO(2), we analyze the robustness to noise of the eigenvector method for synchronization over ${\mathbb{Z}}_2$, when the underlying graph of pairwise measurements is the Erdős-Rényi random graph, using results from the random matrix theory literature. We also propose a message passing synchronization algorithm that outperforms the existing eigenvector synchronization algorithm only for certain classes of graphs and noise models, and enjoys the flexibility of incorporating constraints that may not be easily accommodated by other spectral or SDP-based methods. We apply our methods both to several synthetic models and a real data set of roll call voting patterns in the U.S. Congress across time, to identify the two existing communities, i.e., the Democratic and Republican parties.

28 pages in Journal of Complex Networks, 2015

References in corpus (24)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Synchronization in complex networks
• Multilayer Networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Link communities reveal multiscale complexity in networks
• Mathematical Formulation of Multi-Layer Networks
• An efficient and principled method for detecting communities in networks
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Community Structure in Congressional Cosponsorship Networks
• Community structure and ethnic preferences in school friendship networks
• Universality of the Threshold for Complete Consensus for the Opinion Dynamics of Deffuant et al
• Party Polarization in Congress: A Network Science Approach
• Eigenvector Synchronization, Graph Rigidity and the Molecule Problem
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
• Detecting modules in dense weighted networks with the Potts method
• Localization on low-order eigenvectors of data matrices
• A Generalized Sznajd Model

Cited by in corpus (7)

• Phase Transitions in Semidefinite Relaxations
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Robust Group Synchronization via Cycle-Edge Message Passing
• The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups
• Multiple Partitioning of Multiplex Signed Networks: Application to European Parliament Votes
• Tightness of the semidefinite relaxation for orthogonal trace-sum maximization
• Strong Recovery In Group Synchronization