K-Core Maximization: An Edge Addition Approach

Zhongxin Zhou, Fan Zhang, Xuemin Lin, Wenjie Zhang, Chen Chen

IJCAI 2019 pp. 4867-4873

doi:10.24963/IJCAI.2019/676 /ijcai/2019/zhou2019ijcai-k-a/

Abstract

A popular model to measure the stability of a network is k-core - the maximal induced subgraph in which every vertex has at least k neighbors. Many studies maximize the number of vertices in k-core to improve the stability of a network. In this paper, we study the edge k-core problem: Given a graph G, an integer k and a budget b, add b edges to non-adjacent vertex pairs in G such that the k-core is maximized. We prove the problem is NP-hard and APX-hard. A heuristic algorithm is proposed on general graphs with effective optimization techniques. Comprehensive experiments on 9 real-life datasets demonstrate the effectiveness and the efficiency of our proposed methods.

PDF IJCAI Semantic Scholar

Cite

Text

Zhou et al. "K-Core Maximization: An Edge Addition Approach." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/676

Markdown

[Zhou et al. "K-Core Maximization: An Edge Addition Approach." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/zhou2019ijcai-k-a/) doi:10.24963/IJCAI.2019/676

BibTeX

@inproceedings{zhou2019ijcai-k-a,
  title     = {{K-Core Maximization: An Edge Addition Approach}},
  author    = {Zhou, Zhongxin and Zhang, Fan and Lin, Xuemin and Zhang, Wenjie and Chen, Chen},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {4867-4873},
  doi       = {10.24963/IJCAI.2019/676},
  url       = {https://mlanthology.org/ijcai/2019/zhou2019ijcai-k-a/}
}