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

Budgeted influence maximization in hypergraphs in social networks

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

The influence maximization problem is one of the current research hotspots in online social networks. However, the structure of social networks is intricate and complex, and the traditional influence maximization problem does not consider the group influence in social networks. To address these shortcomings, a budget influence maximization problem based on directed hypergraphs is proposed by using directed hypergraphs to portray the group influence among social users. The problem aims at selecting a most influential node set to maximize the number of eventually activated users under certain budget constraints. The problem has been proved to be NP-hard, and the objective function is non-submodularity. A modified greedy algorithm with theoretical analysis was proposed. A switched heuristic algorithm combined with greedy algorithm was developed to enhance performance. The experiments on three real online social network datasets verify the correctness and effectiveness of our methods. The experiments’ results showed that the switch heuristic algorithm could produce significant performance advantages.