Residual Core Maximization: An Efficient Algorithm for Maximizing the Size of the k-Core
Residual Core Maximization: An Efficient Algorithm for Maximizing the Size of the k-Core
复制标题
DOI：
10.1137/1.9781611976236.37
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Ricky Laishram;Ahmet Erdem Sarıyüce;Tina Eliassi-Rad;A. Pınar;S. Soundarajan
中科院分区：
文献类型：
--
作者：
Ricky Laishram;Ahmet Erdem Sarıyüce;Tina Eliassi-Rad;A. Pınar;S. Soundarajan
在许多在线社交网络平台中，个人的参与是由其他人的参与来激励的。如果一个人选择离开一个平台，这可能会产生一个级联，其中该人的朋友然后选择离开，导致他们的朋友离开，等等。在某些情况下，可以激励关键个人在网络中保持活跃，从而防止这种级联。该问题使用网络的锚定k -核来建模，对于网络G和锚节点A的集合，锚定k-核是G的最大子图，其中每个节点在子图和锚节点之间总共具有至少k个邻居。在这项工作中，我们提出了剩余核最大化（RCM），一种新的算法，用于找到B锚节点，使锚定的k -核的大小最大化。我们对许多真实世界的网络进行了全面的实验评估，并将RCM与各种基线进行了比较。我们观察到，RCM比最先进的方法更有效和高效：平均而言，RCM产生的锚定k核为1。比基线算法产生的结果大65倍，平均快约500倍。
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.