Finding Gangs in War from Signed Networks
Lingyang Chu*, Simon Fraser University; Zhefeng Wang, University of Science and Technology of China; Jian Pei, Simon Fraser University; Jiannan Wang, Simon Fraser University; Zijin Zhao, Simon Fraser University; Enhong Chen,
Given a signed network where edges are weighted in real number, and positive weights indicate cohesion between vertices and negative weights indicate opposition, we are interested in ﬁnding k-Oppositive Cohesive Groups (k-OCG). Each k-OCG is a group of k subgraphs such that (1) the edges within each subgraph are dense and cohesive; and (2) the edges crossing diﬀerent subgraphs are dense and oppositive. Finding k-OCGs is challenging since the subgraphs are often small, there are multiple k-OCGs in a large signed net-work, and many existing dense subgraph extraction methods cannot handle edges of two signs. We model k-OCG ﬁnding task as a quadratic optimization problem. However, the classical Proximal Gradient method is very costly since it has to use the entire adjacency matrix, which is huge on large networks. Thus, we develop FOCG, an algorithm that is two orders of magnitudes faster than the Proximal Gradient method. The main idea is to only search in small subgraphs and thus avoids using a major portion of the adjacency matrix. Our experimental results on synthetic and real data sets as well as a case study clearly demonstrate the eﬀectiveness and eﬃciency of our method.
Filed under: Graph Mining and Social Networks | Mining Rich Data Types