Synchronization over Z2 and community detection in signed multiplex networks with constraints
Synchronization over Z2 and community detection in signed multiplex networks with constraints
复制标题
DOI：
10.1093/comnet/cnu050
复制
发表时间：
2015-09-01
影响因子：
2.1
通讯作者：
Cucuringu, Mihai
中科院分区：
文献类型：
--
作者：
Cucuringu, Mihai
从它们的成对比率的噪声测量中找到群元素也被称为群同步问题，首先在平面旋转的群SO(2)的背景下引入。在最近的传感器网络定位和分子三维结构的算法中，已经证明了Z(2)群同步的有用性。在本文中，我们关注Z(2)上的同步，并考虑在多路网络中识别社区的问题，当节点之间的交互由一个有符号的（可能加权的）相似性度量来描述，并且当多路网络自然划分为两个可能不同大小的社区时。在具有节点的某些子集表示相同（未知）组元素的附加信息的情况下，我们考虑并比较了几种基于谱松弛和SDP松弛以及消息传递算法的Z(2)上同步算法。换句话说，这样一个子集内的所有节点表示相同的未知群元素，并且在属于不同非重叠子集的节点对之间具有可用的噪声成对测量。在最近对SO(2)上的同步特征向量方法进行分析之后，我们分析了Z(2)上同步特征向量方法对噪声的鲁棒性，当两两测量的底层图是Erdos-Renyi随机图时，使用随机矩阵理论文献中关于大型随机矩阵的秩1变形的最大特征值的结果。我们还提出了一种消息传递同步算法，该算法受到标准信念传播算法的启发，仅在某些类别的图和噪声模型中优于现有的特征向量同步算法，并且具有灵活性，可以纳入其他任何基于谱或sdp的方法都不容易适应的附加约束。我们将同步方法应用于几个合成模型和美国国会跨时间的唱名投票模式的真实数据集，以确定两个现有的社区，即民主党和共和党。最后，我们讨论了一些相关的开放性问题和未来的研究方向。
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. The usefulness of synchronization over the group Z(2) has been demonstrated in recent algorithms for localization of sensor networks and three-dimensional structuring of molecules. In this paper, we focus on synchronization over Z(2), and consider the problem of identifying communities in a multiplex network when the interaction between the nodes is described by a signed (and possibly weighted) measure of similarity, and when the multiplex network has a natural partition into two communities, of possibly different sizes. In the setting where one has the additional information that certain subsets of nodes represent the same (unknown) group element, we consider and compare several algorithms for synchronization over Z(2), based on spectral and SDP relaxations, 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 analyse the robustness to noise of the eigenvector method for synchronization over Z(2), when the underlying graph of pairwise measurements is the Erdos-Renyi random graph, using results from the random matrix theory literature on the largest eigenvalue of rank-1 deformation of large random matrices. We also propose a message passing synchronization algorithm, inspired by the standard belief propagation algorithm, that outperforms the existing eigenvector synchronization algorithm only for certain classes of graphs and noise models, and enjoys the flexibility of incorporating additional constraints that may not be easily accommodated by any of the other spectral or SDP-based methods. We apply the synchronization methods both to several synthetic models and a real data set of roll call voting patterns in the US Congress across time, to identify the two existing communities, i.e., the Democratic and Republican parties. Finally, we discuss a number of related open problems and future research directions.