Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3269206.3269254acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
short-paper

K-core Minimization: An Edge Manipulation Approach

Published: 17 October 2018 Publication History

Abstract

In social networks, dense relationships among users contribute to stable networks. Breakdowns of some relationships may cause users to leave the network hence decrease the network stability. A popular metric to measure the stability of a network is k-core, i.e., the maximal subgraph of a social network in which each node has at least k neighbors. In this paper, we propose a novel problem, called k-core minimization. Given a graph G, an integer k and a budget b, we aim to identify a set B of edges with size b, so that we can get the minimum k-core by deleting B from G. We first formally define the problem and prove its NP-hardness. Then a baseline greedy algorithm is proposed. To handle large graphs, an optimized algorithm, named KC-Edge, is developed by adopting novel pruning rules. Finally, comprehensive experiments on 6 real social networks are conducted to demonstrate the efficiency and effectiveness of our proposed methods.

References

[1]
R. Albert, H. Jeong, and A.L. Barabasi. 2000. Error and attack tolerance of complex networks . Nature, Vol. 406 (2000), 378--382.
[2]
Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. 2015. Preventing unraveling in social networks: the anchored k-core problem. SIAM Journal on Discrete Mathematics, Vol. 29, 3 (2015), 1452--1475.
[3]
Chen Chen, Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2016. Eigen-Optimization on Large Graphs by Edge Manipulation. TKDD, Vol. 10, 4 (2016).
[4]
Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations . 85--103.
[5]
Elias Boutros Khalil, Bistra Dilkina, and Le Song. 2014. Scalable Diffusion-aware Optimization of Network Topology. In KDD.
[6]
Subhash Khot. 2004. Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. In FOCS. 136--145.
[7]
Rong-Hua Li and Jeffrey Xu Yu. 2015. Triangle minimization in large networks. Knowl. Inf. Syst., Vol. 45, 3 (2015), 617--643.
[8]
Stephen B. Seidman. 1983. Network structure and minimum degree. Social Networks, Vol. 5, 3 (1983), 269--287.
[9]
Dong Wen, Lu Qin, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. 2016. I/O efficient Core Graph Decomposition at web scale. In ICDE.
[10]
Fan Zhang, Wenjie Zhang, Ying Zhang, Lu Qin, and Xuemin Lin. 2017b. OLAK: an efficient algorithm to prevent unraveling in social networks. PVLDB, Vol. 10, 6 (2017), 649--660.
[11]
Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017a. Finding Critical Users for Social Network Engagement: The Collapsed k-Core Problem. In AAAI.
[12]
Yao Zhang, Abhijin Adiga, Sudip Saha, Anil Vullikanti, and B. Aditya Prakash. 2016. Near-Optimal Algorithms for Controlling Propagation at Group Scale on Networks. TKDE, Vol. 28, 12 (2016), 3339--3352.

Cited By

View all
  • (2024)On Breaking Truss-Based and Core-Based CommunitiesACM Transactions on Knowledge Discovery from Data10.1145/3644077Online publication date: 14-Feb-2024
  • (2024)Optimizing Network Resilience via Vertex AnchoringProceedings of the ACM Web Conference 202410.1145/3589334.3645465(606-617)Online publication date: 13-May-2024
  • (2024)Local Centrality Minimization with Quality GuaranteesProceedings of the ACM Web Conference 202410.1145/3589334.3645382(410-421)Online publication date: 13-May-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
CIKM '18: Proceedings of the 27th ACM International Conference on Information and Knowledge Management
October 2018
2362 pages
ISBN:9781450360142
DOI:10.1145/3269206
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2018

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. critical edges
  2. k-core
  3. network engagement

Qualifiers

  • Short-paper

Funding Sources

  • NSFC
  • YFB

Conference

CIKM '18
Sponsor:

Acceptance Rates

CIKM '18 Paper Acceptance Rate 147 of 826 submissions, 18%;
Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)43
  • Downloads (Last 6 weeks)5
Reflects downloads up to 25 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)On Breaking Truss-Based and Core-Based CommunitiesACM Transactions on Knowledge Discovery from Data10.1145/3644077Online publication date: 14-Feb-2024
  • (2024)Optimizing Network Resilience via Vertex AnchoringProceedings of the ACM Web Conference 202410.1145/3589334.3645465(606-617)Online publication date: 13-May-2024
  • (2024)Local Centrality Minimization with Quality GuaranteesProceedings of the ACM Web Conference 202410.1145/3589334.3645382(410-421)Online publication date: 13-May-2024
  • (2024) MONA: An Efficient and Scalable Strategy for Targeted k -Nodes Collapse IEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2024.335710271:6(3106-3110)Online publication date: Jun-2024
  • (2024) Robustness analysis of multi-dependency networks: -core percolation and deliberate attacks Chaos, Solitons & Fractals10.1016/j.chaos.2024.115559188(115559)Online publication date: Nov-2024
  • (2024)Discovering critical vertices for reinforcement of large-scale bipartite networksThe VLDB Journal10.1007/s00778-024-00871-y33:6(1861-1886)Online publication date: 24-Aug-2024
  • (2024)Detecting Critical Nodes in Hypergraphs via Hypergraph Convolutional NetworkWeb and Big Data10.1007/978-981-97-2421-5_4(47-62)Online publication date: 12-May-2024
  • (2023)Edge-Based Minimal k-Core Subgraph SearchMathematics10.3390/math1115340711:15(3407)Online publication date: 4-Aug-2023
  • (2023)Quantifying Node Importance over Network Structural StabilityProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599480(3217-3228)Online publication date: 6-Aug-2023
  • (2023)Attacking the Core Structure of Complex NetworkIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.318852210:4(1428-1442)Online publication date: Aug-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media