在OSNs中整合群体共识以实现竞争影响力最大化

《ACM Transactions on Knowledge Discovery from Data》：Integrating Group Consensus for Competitive Influence Maximization in OSNs

在线社交网络中群体共识对竞争影响力传播的影响研究，提出GCLT模型并证明其NP难解性及目标函数非单调特性，构建等效GCLE模型，通过Sandwich近似框架设计SBG算法求解上下界，实验验证了方法在六组真实数据中的有效性及可扩展性，揭示了群体共识对竞争性信息扩散的关键作用。

　　

摘要

在在线社交网络（OSNs）中，人们通常加入群体进行交流。信息传播往往需要付出一定的代价，无论是在个体之间还是群体内部/群体之间；不同的观点可能会相互竞争。群体可以根据大多数成员的意见做出决策。这种群体共识在群体活动中很常见。然而，现有关于最大化竞争影响力的研究往往忽略了群体共识的影响。为此，我们引入了在影响力最大化过程中达成群体共识的机制，并提出了一种基于群体共识的竞争线性阈值（GCLT）传播模型；随后我们在GCLT模型下研究了预算竞争影响力最大化（BCIM）问题。我们发现该问题属于NP难问题，并且证明目标函数既不是次模的也不是超模的。为此，我们通过抽样方法构建了一个等价的基于群体共识的竞争活边（GCLE）模型。基于GCLE，我们开发了两个次模函数来表示上下界。然后，我们应用三明治近似框架提出了SBG算法来解决GCLT模型下的BCIM问题。在SBG算法中，我们通过提出的OPIM-B算法得到了下界和上界的近似解。接着，我们在蒙特卡洛模拟中选择了能够实现最佳影响力传播的解决方案集合。我们还提出了两种优化SBG算法的策略。在六个真实社交网络数据集上的实验验证了我们方法的有效性和可扩展性，并证实了群体共识对竞争影响力传播过程的影响，以及考虑达成群体共识过程的重要性。