面向大规模社会网络Top-k影响力节点挖掘的并行算法

摘要：

　　社会网络传播最大化问题是指在一定规模的网络数据中，限定传播源头进行网络传播，使得最终传播的群体数量范围达到最大，该问题已被证明为NP难的。以hill-climbing为代表的贪婪算法在该问题上能够得到(1-1/e)的近似最优解，但是时间代价过大。因此，从并行的角度给出了解决该问题的算法，该算法通过社群划分，定义社群计算量，采用递减贪心法实时保证计算节点(核)负载均衡来提高效率，同时，算法考虑了跨社群间的传播，提高了精度。实验表明，该算法在保证精度的情况下，大幅度提高了时间效率。

关键词： 社会网络 数据挖掘 并行算法 传播效应

作者: Zhou Xiabing 周夏冰 Song Guojie 宋国杰 Xie Kunqing 谢昆青

作者单位: Key Laboratory of Machine Perception(Peking University), Ministry of Education, Beijing 100871 北京大学机器感知与智能教育部重点实验室 北京 100871

会议类型: 国内会议

会议名称: 第29届中国数据库学术会议

会议地点: 合肥

会议语种:中文

页码: 215-221

在线出版日期: 2012-10-01（万方平台首次上网日期，不代表论文的发表时间）