-
题名基于超图的社交网络中的预算影响力最大化
被引量:2
- 1
-
-
作者
陈彬
帅天平
宋新月
-
机构
北京邮电大学理学院
-
出处
《哈尔滨商业大学学报(自然科学版)》
CAS
2022年第3期343-351,共9页
-
基金
国家自然科学基金项目(批准号:12171052)
中央高校基本科研业务费(批准号:500421358)
北京邮电大学提升科技创新能力行动计划项目(批准号:2020XD-A01-1)。
-
文摘
影响力最大化问题是在线社交网络中的热点问题,然而社交网络的结构错综复杂,传统的影响力最大化问题并没有考虑社交网络中的群体影响.针对以上不足,利用有向超图刻画社交用户之间的群体影响,提出一种基于有向超图的预算影响力最大化问题.该问题是在有向超图的社交网络中,在给定预算下,寻找高影响力用户作为种子节点集,使得其最终的传播范围最大化.分析了该问题是NP-hard的且目标函数是非次模函数,提出了改进的贪婪算法和交换启发式算法进行求解,并分析了改进贪婪算法的近似比.通过将所提的算法应用到三个在线社交网络数据集中进行实验,验证了算法的正确性和良好性能.结果表明,改进贪婪算法基础上的交换启发式算法具有明显的性能优势.
-
关键词
社交网络
预算影响力最大化
有向超图
非次模函数
贪婪算法
启发式算法
-
Keywords
social networks
budgeted influence maximization
directed hypergraph
non-submodularity
greedy algorithm
heuristic algorithm
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-