Community Identification in Signed Networks: A K-Truss Based Model

Jun Zhao, Renjie Sun, Qiuyu Zhu, Xiaoyang Wang, Chen Chen

Abstract

Community detection is a fundamental problem in social network analysis, and most existing studies focus on unsigned graphs, i.e., treating all relationships as positive. However, friend and foe relationships naturally exist in many real-world applications. Ignoring the signed information may lead to unstable communities. To better describe the communities, we propose a novel model, named signed k-truss, which leverages the properties of k-truss and balanced triangle. We prove that the problem of identifying the maximum signed k-truss is NP-hard. To deal with large graphs, novel pruning strategies and algorithms are developed. Finally, we conduct comprehensive experiments on real-world signed networks to evaluate the performance of proposed techniques.
BibTeX
@inproceedings{zhao2020community,
  author = {Jun Zhao and Renjie Sun and Qiuyu Zhu and Xiaoyang Wang and Chen Chen},
  title = {{Community Identification in Signed Networks: A K-Truss Based Model}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2020},
  doi = {10.1145/3340531.3412117},
}

Loading related content...

Figure