基于PageRank的社交网络影响最大化传播模型与算法研究

计算机科学 ›› 2013, Vol. 40 ›› Issue (Z6): 136-140.

基于PageRank的社交网络影响最大化传播模型与算法研究

宫秀文,张佩云

安徽师范大学数学计算机科学学院芜湖214003;安徽师范大学数学计算机科学学院芜湖214003

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(61201252),安徽省自然科学基金项目(1308085MF100),安徽省高校省级自然科学研究重点项目(KJ2011A128),安徽省科技厅软科学计划项目(11020503009)资助

Research on Propagation Model and Algorithm for Influence Maximization in Social Network Based on PageRank

GONG Xiu-wen and ZHANG Pei-yun

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 社交网络中影响最大化问题是指找出最具有影响力的k个节点,使得最终社交网络中被影响的节点最多,信息传播范围最大。针对影响最大化问题,目前已存在一些基本传播模型,但是这些模型没有考虑网络中节点的相关性和重要性,而网络中节点的相关性和重要性是衡量其影响力的一个重要指标,因此,提出了一种基于网页排名算法的信息传播模型(PageRank-based Propagation Model,PRP),然后利用贪心算法来近似求解影响最大化问题。实验结果表明,基于PageRank的传播模型解决影响最大化问题的效果比传统的线性阈值模型、加权级联模型和独立级联模型的效果更好,影响力范围更大。

关键词: 社交网络,影响最大化,PageRank,信息传播模型与算法

Abstract: The influence maximization problem in social network is to find top-k influential nodes in graph that maximize the number of influenced nodes．Some basic propagation models have been proposed to solve the influence maximization problem．But those models do not consider the relativity and importance of the node which we consider as an important measurement of influence．Thus,we propose a new PageRank-based propagation model,and employ the Greedy Algorithm to solve the influence maximization problem．The experimental results show that our proposed model is more effective than traditional Linear Threshold Model,Weighted Cascade Model and Independent Cascade Model in solving the influence maximization problem．

Key words: Social network,Influence maximization,PageRank,Information propagation models and algorithm

宫秀文,张佩云. 基于PageRank的社交网络影响最大化传播模型与算法研究[J]. 计算机科学, 2013, 40(Z6): 136-140. https://doi.org/

GONG Xiu-wen and ZHANG Pei-yun. Research on Propagation Model and Algorithm for Influence Maximization in Social Network Based on PageRank[J]. Computer Science, 2013, 40(Z6): 136-140. https://doi.org/

参考文献

[1] Easley D A,Kleinberg J M.Networks,Crowds,and Markets-Reasoning About a Highly Connected World[M]．Cambridge:Cambridge University Press,2010
[2] Domingos P,Richardson M．Mining the network value of cus-tomers[C]∥Seventh International Conference on Knowledge scovery and Data Mining(KDD)．2001:57-66
[3] Mathioudakis M,Bonchi F,Castillo C,et al．Sparsification of Influence Networks[C]∥Proceedings of KDD．2011:529-537
[4] Kimura M,Saito K,Akano R．Extracting Influential Nodes on a Social Network for Information Diffusion[M]．Data Mining and Knowledge Discovery,2010:70-97
[5] Kempe D,Kleinberg J M,Tardos E．Maximizing the spread ofinfluence through a social network[C]∥The Ninth InternationalConference on Knowledge discovery and Data Mining(KDD)．2003:137-146
[6] Ma H,Yang H,Lyu M R．Mining Social Networks Using Heat Diffusion Processes for Marketing Candidates Selection[C]∥Proceedings of CIKM．2011:233-242
[7] 金迪,马衍民.PageRank算法的分析及实现[J].计算机应用,2009,8(1001):118-118
[8] 田家堂,王轶彤,冯小军.一种新型的社会网络影响最大化算法[J].计算机学报,2011,4(10):1956-1965
[9] Leskovec J,Backstrom L,Kleinberg J M．Meme-tracking and the dynamics of the news cycle[C]∥KDD．2009:497-506

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed