Pivotal Relationship Identification: The K-Truss Minimization Problem

Weijie Zhu, Mengqi Zhang, Chen Chen, Xiaoyang Wang, Fan Zhang, Xuemin Lin

IJCAI 2019 pp. 4874-4880

doi:10.24963/IJCAI.2019/677 /ijcai/2019/zhu2019ijcai-pivotal/

Abstract

In a social network, the strength of relationships between users can significantly affect the stability of the network. In this paper, we use the k-truss model to measure the stability of a social network. To identify critical connections, we propose a novel problem, named k-truss minimization. Given a social network G and a budget b, it aims to find b edges for deletion which can lead to the maximum number of edge breaks in the k-truss of G. We show that the problem is NP-hard. To accelerate the computation, novel pruning rules are developed to reduce the candidate size. In addition, we propose an upper bound based strategy to further reduce the searching space. Comprehensive experiments are conducted over real social networks to demonstrate the efficiency and effectiveness of the proposed techniques.

PDF IJCAI Semantic Scholar

Cite

Text

Zhu et al. "Pivotal Relationship Identification: The K-Truss Minimization Problem." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/677

Markdown

[Zhu et al. "Pivotal Relationship Identification: The K-Truss Minimization Problem." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/zhu2019ijcai-pivotal/) doi:10.24963/IJCAI.2019/677

BibTeX

@inproceedings{zhu2019ijcai-pivotal,
  title     = {{Pivotal Relationship Identification: The K-Truss Minimization Problem}},
  author    = {Zhu, Weijie and Zhang, Mengqi and Chen, Chen and Wang, Xiaoyang and Zhang, Fan and Lin, Xuemin},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {4874-4880},
  doi       = {10.24963/IJCAI.2019/677},
  url       = {https://mlanthology.org/ijcai/2019/zhu2019ijcai-pivotal/}
}