Maximum Signed (k,r)-Truss Identification in Signed Networks

Abstract

Mining cohesive subgraphs is a fundamental problem in social network analysis. The k-truss model has been widely used to measure the cohesiveness of subgraphs. Most existing studies about k-truss focus on unsigned graphs. However, in real applications, the edges in the networks can be either positive or negative, e.g., friend or foe relationships, which represents more information than unsigned networks. Therefore, the traditional k-truss model is not applicable for the signed networks. Motivated by this, in this paper, we propose a novel model, named signed (k,r)-truss, which leverages the property of balanced triangle in singed network analysis. Specifically, a signed (k,r)-truss is a subgraph where each edge has no less than k balanced support and no more than r unbalanced support. We prove that the problem of identifying the maximum signed (k,r)-truss is NP-hard. Due to the hardness of the problem, we tend to the heuristic strategies. A trivial algorithm is first presented. Then, two greedy algorithms are developed to enhance the processing. Finally, we conduct comprehensive experiments on real-world signed networks to verify the performance of proposed techniques.