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 - Funding Information:
curity CRA), and the Under Secretary of Defense for Research and Engineering under Air Force Contract No. FA8702-15-D-0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the funding agencies or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes not withstanding any copyright notation here on.
Funding Information:
∗Syracuse University, Syracuse, NY. (rlaishra, su-sounda@syr.edu) †University at Buffalo, Buffalo, NY. (erdem@buffalo.edu) ‡Northeastern University, Boston, MA. (eliassi@ccs.neu.edu) §Sandia National Laboratories, Livermore, CA. (ap-inar@sandia.gov) Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.
Funding Information:
Laishram and Soundarajan were supported by Army Research Office award W911NF-18-1-0047. Soundara-jan was additionally supported by NSF award 1908048. Sariyuce was supported by NSF-1910063. Eliassi-Rad was supported in parts by NSF CNS-1314603, NSF IIS-1741197, the Combat Capabilities Development Command Army Research Laboratory under Cooperative Agreement Number W911NF-13-2-0045 (ARL Cyber Se-
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 -