Maximum Signed θ-Clique Identification in Large Signed Graphs

The maximum clique problem, which is to find the clique with the largest size, can find many real-world applications and is notable for its capability of modeling many combinatorial problems. However, most existing research focuses on processing unsigned graphs, i.e., treat each connection equally. In real applications, edges of graphs are usually associated with signed information, i.e., positive or negative edges, and signed graph analysis has attracted great attentions in the recent. In this paper, we first analyze the disadvantages of existing signed clique models, and then propose a novel clique model, named signed theta-clique. Given a signed graph G and a subgraph S, let d(S)(+)(u) and d(S)(-)(u) be the number of positive and negative neighbors of vertex u in S. We say a subgraph S is a signed theta-clique if i) S is a clique and ii) each vertex u in S fulfills d(S)(+)(u) - d(S)(-)(u) >= theta. We show that the problem of identifying the maximum signed theta-clique is NP-hard. Novel pruning techniques are proposed to reduce the searching space. In addition, efficient searching strategies are developed to scale for large graphs. Comprehensive experiments on 8 real-world datasets are conducted to demonstrate the effectiveness and efficiency of the proposed approaches.