论文标题
在签名的网络中找到大型平衡子图
Finding large balanced subgraphs in signed networks
论文作者
论文摘要
签名的网络是图形的图形，其边缘用正符号或负符号标记，可用于捕获未签名的对应物遗漏的相互作用中的细微差别。签名图理论中平衡的概念决定了是否可以将网络划分为两个完全相对的子集，因此对于建模现象（例如社交网络中两极分化社区的存在）很有用。在确定图表是否平衡很容易时，很难找到一个较大的平衡子图。为此目的，文献中可用的少数启发式方法是无效或不可降低。在本文中，我们提出了一种有效的算法，用于在签名的网络中找到大型平衡子图。该算法依赖于签名的光谱理论，并依靠图形拉普拉斯的扰动。在对现实世界数据的各种实验中，我们表明，我们的算法可以找到比现有方法检测到的算法大得多，此外，它更快。我们在最多3400万个边缘的图表上测试了它的可伸缩性。
Signed networks are graphs whose edges are labelled with either a positive or a negative sign, and can be used to capture nuances in interactions that are missed by their unsigned counterparts. The concept of balance in signed graph theory determines whether a network can be partitioned into two perfectly opposing subsets, and is therefore useful for modelling phenomena such as the existence of polarized communities in social networks. While determining whether a graph is balanced is easy, finding a large balanced subgraph is hard. The few heuristics available in the literature for this purpose are either ineffective or non-scalable. In this paper we propose an efficient algorithm for finding large balanced subgraphs in signed networks. The algorithm relies on signed spectral theory and a novel bound for perturbations of the graph Laplacian. In a wide variety of experiments on real-world data we show that our algorithm can find balanced subgraphs much larger than those detected by existing methods, and in addition, it is faster. We test its scalability on graphs of up to 34 million edges.
