改进投票模型,提升影响力节点选择与收敛性分析。
A Generalisation of Voter Model: Influential Nodes and Convergence Properties
- 引入有影响力的节点和更新阻力机制,扩展经典投票模型。
- 证明最优种子选择为NP难,并给出最佳近似算法。
- 在真实与合成数据上验证效果,揭示收敛时间特性。
考虑一个无向图G,代表社交网络,每个节点为蓝色或红色,对应对某一话题的正面或负面意见。在经典投票模型中,每个节点在离散时间轮次中随机选择一个邻居并采纳其颜色。尽管该模型广受欢迎,却无法捕捉现实中的关键特征,如个体间连接强度差异、中立态度个体以及不愿更新观点的个体。为解决这些问题,我们提出并研究了投票模型的推广版本。受竞选策略启发,我们探讨选择一组初始蓝色节点作为种子以最大化若干轮后蓝色节点期望数量的问题。我们证明该问题为NP难,并提供具有最优近似保证的多项式时间近似算法。在真实世界和合成图数据上的实验表明,所提算法优于其他方法。此外,我们研究了该模型的收敛性质:证明过程可能需要指数轮次才能收敛;但在强连通图中,收敛时间为多项式,且收敛周期(收敛状态数)整除图中所有环的长度。
原文摘要 · Abstract (English)
Consider an undirected graph G, representing a social network, where each node is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of individuals connections, individuals with neutral opinion on a topic, and individuals who are reluctant to update their opinion. To address these issues, we introduce and study a generalisation of the voter model. Motivating by campaigning strategies, we study the problem of selecting a set of seeds blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP- hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms. We also investigate the convergence properties of the model. We prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the period (the number of states in convergence) divides the length of all cycles in the graph.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。