基于超图的社交网络中的预算影响力最大化

影响力最大化问题是在线社交网络中的热点问题，然而社交网络的结构错综复杂，传统的影响力最大化问题并没有考虑社交网络中的群体影响.针对以上不足，利用有向超图刻画社交用户之间的群体影响，提出一种基于有向超图的预算影响力最大化问题.该问题是在有向超图的社交网络中，在给定预算下，寻找高影响力用户作为种子节点集，使得其最终的传播范围最大化.分析了该问题是NP-hard的且目标函数是非次模函数，提出了改进的贪婪算法和交换启发式算法进行求解，并分析了改进贪婪算法的近似比.通过将所提的算法应用到三个在线社交网络数据集中进行实验，验证了算法的正确性和良好性能.结果表明，改进贪婪算法基础上的交换启发式算法具有明显的性能优势.