基于反向PageRank的影响力最大化算法

doi:10.11772/j.issn.1001-9081.2019061066

计算机应用 ›› 2020, Vol. 40 ›› Issue (1): 96-102.DOI: 10.11772/j.issn.1001-9081.2019061066

基于反向PageRank的影响力最大化算法

张宪立, 唐建新, 曹来成

兰州理工大学计算机与通信学院, 兰州 730050

收稿日期:2019-06-24 修回日期:2019-09-02 出版日期:2020-01-10 发布日期:2019-09-29
通讯作者: 张宪立
作者简介:张宪立(1979-),男,甘肃陇南人,讲师,主要研究方向:社会网络分析、影响力最大化;唐建新(1985-),男,河南商丘人,讲师,博士,主要研究方向:传播动力学、智能计算;曹来成(1965-),男,甘肃平凉人,教授,博士,主要研究方向:网络空间安全、大数据智能分析与安全。
基金资助:
国家自然科学基金资助项目（61562059）。

Influence maximization algorithm based on reverse PageRank

ZHANG Xianli, TANG Jianxin, CAO Laicheng

School of Computer and Communication, Lanzhou University of Technology, Lanzhou Gansu 730050, China

Received:2019-06-24 Revised:2019-09-02 Online:2020-01-10 Published:2019-09-29
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61562059).

摘要/Abstract

摘要： 针对社会网络上的影响力最大化算法在大规模网络上难以同时满足传播范围、时间效率和空间效率要求的问题，提出一种混合PageRank和度中心性的启发式算法（MPRD）。首先，基于PageRank，引入一种反向PageRank思想来评估节点影响力；然后，结合局部指标度中心性，设计一种混合的指标来评估节点的最终影响力；最后，通过相似性方法去掉影响力重合严重的节点，选出种子节点集。在6个数据集和两种传播模型上进行实验，实验结果表明，所提的MPRD在传播范围上优于现有的启发式算法，在时间效率上比贪心算法快四、五个数量级，在空间效率上优于基于反向抽样的IMM算法。所提的MPRD在处理大规模网络上的影响力最大化问题时能够取得传播范围、时间效率和空间效率的平衡。

关键词: 影响力最大化, PageRank, 度中心性, 启发式算法, 贪心算法

Abstract: Concerning the problem that the existing influence maximization algorithms on social networks are difficult to meet the requirements of propagation range, time cost and memory usage on large scale networks simultaneously, a heuristic algorithm of Mixed PageRank and Degree (MPRD) was proposed. Firstly, the idea of reverse PageRank was introduced for evaluating the influence of nodes based on PageRank. Secondly, a mixed index based on reverse PageRank and degree centrality was designed for evaluating final influence of nodes. Finally, the seed node set was selected by using the similarity method to filter out the node with serious overlapping influence. The experiments were conducted on six datasets and two propagation models. The experimental results show that the proposed MPRD is superior to the existing heuristic algorithms in term of propagation range, and is four or five orders of magnitude faster than greedy algorithm, and needs lower memory compared to Influence Maximization based on Martingale (IMM) algorithm based on reverse sampling. The proposed MPRD can achieve the balance of propagation range, time cost and memory usage in solving the problem of influence maximization on large scale networks.

Key words: influence maximization, PageRank, degree centrality, heuristic algorithm, greedy algorithm

中图分类号:

TP301.6

张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用, 2020, 40(1): 96-102.

ZHANG Xianli, TANG Jianxin, CAO Laicheng. Influence maximization algorithm based on reverse PageRank[J]. Journal of Computer Applications, 2020, 40(1): 96-102.

参考文献

[1] DOMINGOS P, RICHARDSON M. Mining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2001:57-66.
[2] RICHARDSON M, DOMINGOS P. Mining knowledge-sharing sites for viral marketing[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2002:61-70.
[3] KEMPE D, KLEINBERG J, TARDOS É. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2003:137-146.
[4] LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2007:420-429.
[5] CHEN W, WANG Y, YANG S. Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2009:199-208.
[6] CHENG S, SHEN H, HUANG J, et al. StaticGreedy:solving the scalability-accuracy dilemma in influence maximization[C]//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. New York:ACM, 2013:509-518.
[7] OHSAKA N, AKIBA T, YOSHIDA Y, et al. Fast and accurate influence maximization on large networks with pruned Monte-Carlo simulations[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence. Pola Alto, CA:AAAI Press, 2014:138-144.
[8] 曹玖新,董丹,徐顺,等.一种基k-核的社会网络影响最大化算法[J].计算机学报,2015,38(2):238-248.(CAO J X, DONG D, XU S, et al. A k-core based algorithm for influence maximization in social networks[J]. Chinese Journal of Computers, 2015, 38(2):238-248.)
[9] 王双,李斌,刘学军,等.基于社区度的边界节点影响力最大化算法[J].电子技术应用,2015,41(5):145-148,151.(WANG S, LI B, LIU X J, et al. An influence maximization algorithm of boundary nodes based on degree of community[J]. Application of Electronic Technique, 2015, 41(5):145-148, 151.)
[10] 杨书新,刘成辉,鲁纪华.基于两阶段启发的社交网络影响最大化算法[J].小型微型计算机系统,2017,38(10):2268-2274.(YANG S X, LIU C H, LU J H. Two stages of heuristics based algorithm for influence maximization in social network[J]. Journal of Chinese Computer Systems, 2017, 38(10):2268-2274.)
[11] 李阅志,祝园园,钟鸣.基k-核过滤的社交网络影响最大化算法[J].计算机应用,2018,38(2):464-470.(LI Y Z, ZHU Y Y, ZHONG M. k-core filtered influence maximization algorithm in social networks[J]. Journal of Computer Applications, 2018, 38(2):464-470.)
[12] 李敏佳,许国艳,朱帅,等.基于结构洞和度折扣的影响力最大化算法[J].计算机应用,2018,38(12):3419-3424.(LI M J, XU G Y, ZHU S, et al. Influence maximization algorithm based on structure hole and degree discount[J]. Journal of Computer Applications, 2018, 38(12):3419-3424.)
[13] 孙子力,彭舰,仝博.社会网络中基于社群衰减的影响力最大化算法[J].计算机应用,2019,39(3):834-838.(SUN Z L, PENG J, TONG B. Influence maximization algorithm based on community attention in social network[J]. Journal of Computer Applications, 2019, 39(3):834-838.)
[14] KIMURA M, SAITO K. Tractable models for information diffusion in social networks[C]//Proceedings of the 2006 European Conference on Principles of Data Mining and Knowledge Discovery, LNCS 4213. Berlin:Springer, 2006:259-271.
[15] CHEN W, WANG C, WANG Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2010:1029-1038.
[16] KIM J, KIM S K, YU H. Scalable and parallelizable processing of influence maximization for large-scale social networks?[C]//Proceedings of the IEEE 29th International Conference on Data Engineering. Piscataway:IEEE, 2013:266-277.
[17] WU H, SHANG J, ZHOU S, et al. LAIM:a linear time iterative approach for efficient influence maximization in large-scale networks[J]. IEEE Access, 2018, 6:44221-44234.
[18] BORGS C, BRAUTBAR M, CHAYES J, et al. Maximizing social influence in nearly optimal time[C]//Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA:Society for Industrial and Applied Mathematics, 2014:946-957.
[19] TANG Y, XIAO X, SHI Y. Influence maximization:Near-optimal time complexity meets practical efficiency[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2014:75-86.
[20] TANG Y, SHI Y, XIAO X. Influence maximization in near-linear time:a martingale approach[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2015:1539-1554.
[21] NGUYEN H T, THAI M T, DINH T N. Stop-and-stare:optimal sampling algorithms for viral marketing in billion-scale networks[C]//Proceedings of the 2016 International Conference on Management of Data. New York:ACM, 2016:695-710.
[22] WANG X, ZHANG Y, ZHANG W, et al. Bring order into the samples:a novel scalable method for influence maximization[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 29(2):243-256.
[23] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/67):107-117.
[24] YUAN J, ZHANG R, TANG J, et al. Efficient and effective influence maximization in large-scale social networks via two frameworks[J]. Physica A:Statistical Mechanics and its Applications, 2019, 526:No.120966.

基于反向PageRank的影响力最大化算法

Influence maximization algorithm based on reverse PageRank

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张笑非, 杨阳, 黄佳进, 钟宁. 基于度中心性的认知特征选择方法[J]. 计算机应用, 2021, 41(9): 2767-2772.
[2]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[3]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[4]	李翀, 王宇宸, 杜伟静, 何晓涛, 刘学敏, 张士波, 李树仁. 基于Web of Science的PageRank人才挖掘算法[J]. 计算机应用, 2021, 41(5): 1356-1360.
[5]	张舒瑶, 李勇华, 范家佳. 基于博弈论的散货港口堆场堆位分配算法[J]. 计算机应用, 2021, 41(3): 867-874.
[6]	陈晓楠, 胡建敏, 陈茜, 张威. 基于LightGBM算法的网络战仿真与效能评估[J]. 计算机应用, 2020, 40(7): 2003-2008.
[7]	蔡豪, 袁正道. 云数据中心基于贪心模式的虚拟机选择算法[J]. 计算机应用, 2020, 40(6): 1707-1713.
[8]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[9]	隗千千, 董兴业, 王焕政. 染缸排产建模及滑动时间窗启发式调度算法[J]. 计算机应用, 2020, 40(1): 292-298.
[10]	袁培燕, 蔡云云. 移动边缘计算中一种贪心策略的内容卸载方案[J]. 计算机应用, 2019, 39(9): 2664-2668.
[11]	刘枭, 王晓国. 基于密集子图的银行电信诈骗检测方法[J]. 计算机应用, 2019, 39(4): 1214-1219.
[12]	孙子力, 彭舰, 仝博. 社会网络中基于社群衰减的影响力最大化算法[J]. 计算机应用, 2019, 39(3): 834-838.
[13]	刘开南. 云数据中心基于贪心算法的虚拟机迁移策略[J]. 计算机应用, 2019, 39(11): 3333-3338.
[14]	吴斌, 王超, 董敏. 基于混合果蝇优化算法的现场服务调度问题[J]. 计算机应用, 2018, 38(9): 2706-2711.
[15]	梁利东, 贾文友. 基于宽容分层策略的启发式排样算法[J]. 计算机应用, 2018, 38(4): 1195-1200.