TY - GEN
T1 - Residual core maximization
T2 - 2020 SIAM International Conference on Data Mining, SDM 2020
AU - Laishram, Ricky
AU - Sariyüce, Ahmet Erdem
AU - Eliassi-Rad, Tina
AU - Pinar, Ali
AU - Soundarajan, Sucheta
N1 - Publisher Copyright:
Copyright © 2020 by SIAM.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85089182822&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089182822&partnerID=8YFLogxK
U2 - 10.1137/1.9781611976236.37
DO - 10.1137/1.9781611976236.37
M3 - Conference contribution
AN - SCOPUS:85089182822
T3 - Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020
SP - 325
EP - 333
BT - Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020
A2 - Demeniconi, Carlotta
A2 - Chawla, Nitesh
PB - Society for Industrial and Applied Mathematics Publications
Y2 - 7 May 2020 through 9 May 2020
ER -