Triangular Stability Maximization by Influence Spread over Social Networks
Triangular Stability Maximization by Influence Spread over Social Networks
复制标题
DOI：
10.14778/3611479.3611490
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
Zheng Hu;Weiguo Zheng;Xiang Lian
中科院分区：
文献类型：
--
作者：
Zheng Hu;Weiguo Zheng;Xiang Lian
在许多现实世界的应用中，如社交网络分析和在线广告/营销，最重要和最流行的问题之一是所谓的影响最大化（IM），它找到一组k种子用户，最大化受影响的用户节点的预期数量。然而，在实践中，最大化受影响的节点的数量可能远远不能满足真实的应用，如意见推广和集体购买。本文探讨了稳定性和三角形在社交网络中的重要性，提出了一个新的社交网络影响扩散问题--三角形稳定性最大化问题，并将其推广为一般的三角形影响最大化问题，证明了该问题是NP-难的.我们开发了一个有效的反向影响采样（RIS）为基础的框架与理论保证的三角IM。为了实现无偏估计，它需要三角形的概率抽样，即根据它们的概率对三角形进行抽样。我们提出了一种基于边的三重抽样方法，它完全等同于概率抽样，避免了昂贵的三角枚举和物化。我们还设计了一些修剪和减少技术，以及成本模型引导的启发式算法。大量的实验和对真实世界图的案例研究证实了我们提出的算法的有效性和三角稳定性最大化和三角影响最大化的优越性。
In many real-world applications such as social network analysis and online advertising/marketing, one of the most important and popular problems is called influence maximization (IM), which finds a set of k seed users that maximize the expected number of influenced user nodes. In practice, however, maximizing the number of influenced nodes may be far from satisfactory for real applications such as opinion promotion and collective buying. In this paper, we explore the importance of stability and triangles in social networks, and formulate a novel problem in the influence spread scenario, named triangular stability maximization , over social networks, and generalize it to a general triangle influence maximization problem, which is proved to be NP-hard. We develop an efficient reverse influence sampling (RIS) based framework for the triangle IM with theoretical guarantees. To enable unbiased estimators, it demands probabilistic sampling of triangles, that is, sampling triangles according to their probabilities. We propose an edge-based triple sampling approach, which is exactly equivalent to probabilistic sampling and avoids costly triangle enumeration and materialization. We also design several pruning and reduction techniques, as well as a cost-model-guided heuristic algorithm. Extensive experiments and a case study over real-world graphs confirm the effectiveness of our proposed algorithms and the superiority of triangular stability maximization and triangle influence maximization.