Quantum Social Computing Approaches for Influence Maximization
Quantum Social Computing Approaches for Influence Maximization
复制标题
DOI：
10.1109/globecom48099.2022.10000698
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Thang N. Dinh;An Nguyen;Uyen Nguyen;Giang Nguyen
中科院分区：
文献类型：
--
作者：
Thang N. Dinh;An Nguyen;Uyen Nguyen;Giang Nguyen
影响力最大化（IM）寻求一小组重要节点将影响力广泛传播到网络中，是社交网络中的一个基本问题。它可应用于病毒式营销、流行病控制和评估复杂系统内的级联故障。尽管付出了巨大的努力，但由于 IM 的 NP 完整性，找到接近最优的解决方案仍然很困难。在本文中，我们提出了第一个用于 IM 的社会量子计算方法，旨在检索接近最优的解决方案。我们提出了一种两阶段算法，1）将 IM 转换为 Max-Cover 实例，2）提供高效的二次无约束二进制优化公式来求解量子退火器上的 Max-Cover 实例。我们在最先进的 D-Wave 退火机上进行的实验表明，与经典模拟退火相比，解决方案质量更好，这表明应用量子退火来寻找高质量 IM 解决方案的潜力。
Influence Maximization (IM), which seeks a small set of important nodes that spread the influence widely into the network, is a fundamental problem in social networks. It finds applications in viral marketing, epidemic control, and assessing cascading failures within complex systems. Despite the huge amount of effort, finding near-optimal solutions for IM is difficult due to its NP-completeness. In this paper, we propose the first social quantum computing approaches for IM, aiming to retrieve near-optimal solutions. We propose a two-phase algorithm that 1) converts IM into a Max-Cover instance and 2) provides efficient quadratic unconstrained binary optimization formulations to solve the Max-Cover instance on quantum annealers. Our experiments on the state-of-the-art D-Wave annealer indicate better solution quality compared to classical simulated annealing, suggesting the potential of applying quantum annealing to find high-quality solutions for IM.