在线社交网络个体影响力算法测试与性能评估

doi:10.11959/j.issn.1000-436x.2018217

通信学报 ›› 2018, Vol. 39 ›› Issue (10): 1-10.doi: 10.11959/j.issn.1000-436x.2018217

• 学术论文 • 下一篇

在线社交网络个体影响力算法测试与性能评估

全拥¹(),贾焰¹,张良¹,朱争¹,周斌¹,方滨兴²

¹ 国防科技大学计算机学院，湖南长沙 410073
² 北京邮电大学计算机学院，北京 100876

修回日期:2018-08-22 出版日期:2018-10-01 发布日期:2018-11-23
作者简介:全拥（1988-），男，湖南常德人，国防科技大学博士生，主要研究方向为在线社交网络分析、数据挖掘。|贾焰（1960-），女，四川成都人，博士，国防科技大学教授、博士生导师，主要研究方向为数据挖掘、大数据分析、信息安全等。|张良（1989-），男，江西九江人，国防科技大学博士生，主要研究方向为在线社交网络分析、数据挖掘。|朱争（1993-），男，四川攀枝花人，国防科技大学硕士生，主要研究方向为信息安全。|周斌（1971-），男，江西吉安人，博士，国防科技大学研究员、博士生导师，主要研究方向为数据挖掘、信息安全。|方滨兴（1960-），男，江西上饶人，博士，中国工程院院士，北京邮电大学教授、博士生导师，主要研究方向为计算机网络、信息安全、并行计算等。
基金资助:
国家重点研发计划基金资助项目(2017YFB0803303);国家自然科学基金资助项目(61502517);湖南省重点研发计划资助项目(2018GK2056)

Performance analysis and testing of personal influence algorithm in online social networks

Yong QUAN¹(),Yan JIA¹,Liang ZHANG¹,Zheng ZHU¹,Bin ZHOU¹,Binxing FANG²

¹ College of Computer,National University of Defense Technology,Changsha 410073,China
² College of Computer,Beijing University of Posts and Telecommunications,Beijing 100876,China

Revised:2018-08-22 Online:2018-10-01 Published:2018-11-23
Supported by:
The National Key Research and Development Program of China(2017YFB0803303);The National Natural Science Foundation of China(61502517);The Key Research and Development Project of Hunan Province(2018GK2056)

摘要/Abstract

摘要：

社交影响力是驱动信息传播的关键因素，基于在线社交网络数据，可以对社交影响力进行建模和分析。针对一种经典的个体影响力计算方法，介绍了该算法的2种并行化实现，并在真实大规模在线社交网络数据集上进行了性能测试。结果表明，借助现有的大数据处理框架，显著提高了个体影响力计算方法在海量数据集中的计算效率，同时也给该类算法的研究和优化提供了实证依据。

关键词: 性能测试, 社交影响力, 分布式计算, 在线社交网络

Abstract:

Social influence is the key factor to drive information propagation in online social networks and can be modeled and analyzed with social networking data.As a kind of classical personal influence algorithm,two parallel implementation versions of a PageRank based method were introduced.Furthermore,extensive experiments were conducted on a large-scale real dataset to test the performance of these parallel methods in a distributed environment.The results demonstrate that the computational efficiency of the personal influence algorithm can be improved significantly in massive data sets by virtue of existing big data processing framework,and provide an empirical reference for the future research and optimization of the algorithm as well.

Key words: performance testing, social influence, distributed computing, online social networks

中图分类号:

TP391

全拥,贾焰,张良,朱争,周斌,方滨兴. 在线社交网络个体影响力算法测试与性能评估[J]. 通信学报, 2018, 39(10): 1-10.

Yong QUAN,Yan JIA,Liang ZHANG,Zheng ZHU,Bin ZHOU,Binxing FANG. Performance analysis and testing of personal influence algorithm in online social networks[J]. Journal on Communications, 2018, 39(10): 1-10.

图/表 12

表1

图1

图2

表2

图3

图4

图5

图6

图7

图8

图9

图10

参考文献 22

[1]	方滨兴, 许进, 李建华 . 在线社交网络分析[M]. 北京: 电子工业出版社, 2014.
	FANG B X , XU J , LI J H . Online social network analysis[M]. Beijing: Publishing House of Electronics IndustryPress, 2014.
[2]	CIALDINI R B . Influence:science and practice[M]. Boston: Allyn and BaconPress, 2003.
[3]	吴信东, 李毅, 李磊 . 在线社交网络影响力分析[J]. 计算机学报, 2014,37(4): 735-752.
	WU X D , LI Y , LI L . Influence analysis of online social networks[J]. Chinese Journal of Computers, 2014,37(4): 735-752.
[4]	TING I H , CHANGP S , WANG S L . Understanding microblog users for social recommendation based on social networks analysis[J]. Journal of Universal Computer Science, 2012,18(4): 554-576.
[5]	LI N , GILLET D . Identifying influential scholars in academic social media platforms[C]// The 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2013: 608-614.
[6]	VEGA-OLIVEROS D A , BERTON L , LOPES A D A ,et al. Influence maximization based on the least in-fluential spreaders[C]// The 1st International Conference on Social Influence Analysis. 2015: 3-8.
[7]	DINH T N , ZHANG H , NGUYEN D T ,et al. Cost-effective viral marketing for time-critical campaigns in large-scale social networks[J]. IEEE/ACM Transactions on Networking, 2014,22(6): 2001-2011.
[8]	KATZ E , LAZARSFELD P . Personal influence:the part played by people in the flow of mass communica-tions[M]. New Jersey: Transaction PublishersPress, 1966.
[9]	CHA M , HADDADI H , BENEVENUTO F ,et al. Measuring user influence in twitter:the million follower fallacy[C]// International Conference on Weblogs and Social Media. 2010: 10-17.
[10]	DING Z , JIA Y , ZHOU B ,et al. Mining topical influencers based on the multi-relational network in microblogging sites[J]. China Communications, 2013,10(1): 93-104.
[11]	WENG J , LIM E P , JIANG J ,et al. TwitterRank:finding topic-sensitive influential twitterers[C]// The third ACM International Conference on Web Search and Data Mining. 2010: 261-270.
[12]	TANG J , SUN J , WANG C ,et al. Social influence anal-ysis in large-scale networks[C]// The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009: 807-816.
[13]	LIU X , LI M , LI S ,et al. IMGPU:GPU-accelerated influence maximization in large-scale social networks[J]. IEEE Transactions on Parallel and distributed Systems, 2014,25(1): 136-145.
[14]	平宇, 向阳, 张波 ,等. 基于MapReduce的并行PageRank算法实现[J]. 计算机工程, 2014,40(2): 31-34.
	PING Y , XIANG Y , ZHANG B ,et al. Implementation of parallel PageRank algorithm[J]. Computer Engineering Based on MapReduce, 2014,40(2): 31-34.
[15]	FREEMAN L C . Centrality in social networks conceptual clarification[J]. Social Networks, 1978,1(3): 215-239.
[16]	NEWMAN M E J . A measure of betweenness centrality based on random walks[J]. Social Networks, 2005,27(1): 39-54.
[17]	NEWMAN M E J . The structure and function of complex networks[J]. SIAM Review, 2003,45(2): 167-256.
[18]	KITSAK M , GALLOS L K , HAVLIN S ,et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010,6(11): 888-893.
[19]	PAGE L , BRIN S , MOTWANI R ,et al. The pagerank citation ranking:bringing order to the web[J]. Stanford Digital Libraries Working Paper, 1998,9(1): 1-14.
[20]	EFRON M . Information search and retrieval in microblogs[J]. Journal of the American Society for Information Science and Technology, 2011,62(6): 996-1008.
[21]	HAVELIWALA T , KAMVAR A , JEH G . An analytical comparison of approaches to personalizing pagerank[R]. Palo Alto:Stanford University, 2003.
[22]	SONG X , CHI Y , HINO K ,et al. Identifying opinion leaders in the blogosphere[C]// The 6th ACM Conference on Information and Knowledge Management. 2007: 971-974.

数据集描述	统计量
博文数	4 586 584 659
用户数	116 147 966
原创博文数	1 079 801 756
被转发原创博文数	97 351 945
转发博文数	3 506 782 903
原创博文平均被转发次数	3.25

数据集	用户数	转发关系数	稠密度
D₁	100 000	4 185 326	4.19×10^-4
D₁_A	100 000	41 862 541	4.19×10^-3
D₁_B	100 000	418 568	4.19×10^-5
D₂	1 000 000	94 091 124	9.41×10^-5
D₂_A	1 000 000	940 634 687	9.41×10^-4
D₂_B	1 000 000	9 411 885	9.41×10^-6
D₂_C	1 000 000	941 482	9.41×10^-7
D₃	10 000 000	662 538 337	6.63×10^-6
D₄	50 000 000	1 368 256 085	5.47×10^-7
D₅	115 205 577	3 504 379 868	1.19×10^-4

在线社交网络个体影响力算法测试与性能评估

Performance analysis and testing of personal influence algorithm in online social networks

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 22

相关文章 13

Metrics

推荐阅读 0

[1]	王晓萌, 方滨兴, 张宏莉, 王星. TSL：基于连接强度的Facebook消息流行度预测模型[J]. 通信学报, 2019, 40(10): 1-9.
[2]	彭舰,王屯屯,陈瑜,刘唐,徐文政. 基于跨平台的在线社交网络用户推荐研究[J]. 通信学报, 2018, 39(3): 147-158.
[3]	刘蓉,陈波,于泠,刘亚尚,陈思远. 恶意社交机器人检测技术研究[J]. 通信学报, 2017, 38(Z2): 197-210.
[4]	王超,韩笑冬,王睿,周晞,杨琳璐,刘亚萍. 支持网络互连的可重构卫星平台关键技术研究[J]. 通信学报, 2017, 38(Z1): 83-87.
[5]	丁长松,王志英,胡志刚. 分布式环境中基于市场机制的资源自适应调价策略[J]. 通信学报, 2016, 37(2): 32-38.
[6]	林荣恒，吴步丹，赵耀，杨放春. 基于K-means的云化分布式BPEL引擎放置机制[J]. 通信学报, 2014, 35(5): 7-56.
[7]	林荣恒,吴步丹,赵耀,杨放春. 基于K-means的云化分布式BPEL引擎放置机制[J]. 通信学报, 2014, 35(5): 49-56.
[8]	蒲星,刘梦晓,周瑞涛,靳军,高强,曹元大. 虚拟云环境中基于多核系统的网络I/O性能分析[J]. 通信学报, 2011, 32(9A): 139-145.
[9]	吴华锋,施朝健,高传善. CAR：一种MANET环境下的P2P资源定位与获取算法[J]. 通信学报, 2011, 32(12): 18-28.
[10]	徐小龙,程春玲,熊婧夷. 基于multi-agent的云端计算融合模型的研究[J]. 通信学报, 2010, 31(10): 203-211.
[11]	谢鲲,秦拯,文吉刚,张大方,谢高岗. 联合多维布鲁姆过滤器查询算法[J]. 通信学报, 2008, 29(1): 56-64.
[12]	陈伟江,郭朝珍. 分布式ETL中协同机制的研究与设计[J]. 通信学报, 2006, 27(11): 177-182.
[13]	姬琳,杨岳湘,王韶红. 分布式计算资源管理[J]. 通信学报, 2005, 26(1A): 259-263.