Residual core maximization: An efficient algorithm for maximizing the size of the k-core

Ricky Laishram, Ahmet Erdem Sariyüce, Tina Eliassi-Rad, Ali Pinar, Sucheta Soundarajan

Research output: Chapter in Book/Entry/PoemConference contribution

18 Scopus citations

Abstract

In many online social networking platforms, the participation of an individual is motivated by the participation of others. If an individual chooses to leave a platform, this may produce a cascade in which that person’s friends then choose to leave, causing their friends to leave, and so on. In some cases, it may be possible to incentivize key individuals to stay active within the network, thus preventing such a cascade. This problem is modeled using the anchored k-core of a network, which, for a network G and set of anchor nodes A, is the maximal subgraph of G in which every node has a total of at least k neighbors between the subgraph and anchors. In this work, we propose Residual Core Maximization (RCM), a novel algorithm for finding b anchor nodes so that the size of the anchored k-core is maximized. We perform a comprehensive experimental evaluation on numerous real-world networks and compare RCM to various baselines. We observe that RCM is more effective and efficient than the state-of-the-art methods: on average, RCM produces anchored k-cores that are 1.65 times larger than those produced by the baseline algorithm, and is approximately 500 times faster on average.

Original languageEnglish (US)
Title of host publicationProceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020
EditorsCarlotta Demeniconi, Nitesh Chawla
PublisherSociety for Industrial and Applied Mathematics Publications
Pages325-333
Number of pages9
ISBN (Electronic)9781611976236
DOIs
StatePublished - 2020
Event2020 SIAM International Conference on Data Mining, SDM 2020 - Cincinnati, United States
Duration: May 7 2020May 9 2020

Publication series

NameProceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020

Conference

Conference2020 SIAM International Conference on Data Mining, SDM 2020
Country/TerritoryUnited States
CityCincinnati
Period5/7/205/9/20

ASJC Scopus subject areas

  • Computer Science Applications
  • Software

Fingerprint

Dive into the research topics of 'Residual core maximization: An efficient algorithm for maximizing the size of the k-core'. Together they form a unique fingerprint.

Cite this