大规模时序图中种子节点挖掘算法研究

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

通信学报 ›› 2022, Vol. 43 ›› Issue (9): 157-168.doi: 10.11959/j.issn.1000-436x.2022170

大规模时序图中种子节点挖掘算法研究

邹晓红¹^,², 许成伟¹, 陈晶¹, 宋彪¹, 王明月¹

¹ 燕山大学信息科学与工程学院，河北秦皇岛 066004
² 河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛 066004

修回日期:2022-08-29 出版日期:2022-09-25 发布日期:2022-09-01
作者简介:邹晓红（1967- ），女，吉林省吉林市人，博士，燕山大学教授、硕士生导师，主要研究方向为图挖掘、社会网络、复杂网络分析等
许成伟（1997- ），男，黑龙江齐齐哈尔人，燕山大学硕士生，主要研究方向为社交网络
陈晶（1976- ），女，河北秦皇岛人，博士，燕山大学教授、硕士生导师，主要研究方向为对等网络、社会计算、Web服务等
宋彪（1996- ），男，河北张家口人，燕山大学硕士生，主要研究方向为不确定图挖掘
王明月（1996- ），女，河北秦皇岛人，燕山大学硕士生，主要研究方向为社交网络
基金资助:
国家自然科学基金资助项目(62172352);国家自然科学基金资助项目(61871465);河北省自然科学基金资助项目(F2019203157);河北省高等学校科学技术研究资助项目(ZD2019004);河北省创新能力提升计划项目(22567626H)

Research on seed node mining algorithm in large-scale temporal graph

Xiaohong ZOU¹^,², Chengwei XU¹, Jing CHEN¹, Biao SONG¹, Mingyue WANG¹

¹ School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China
² Hebei Key Laboratory of Computer Virtual Technology and System Integration, Qinhuangdao 066004, China

Revised:2022-08-29 Online:2022-09-25 Published:2022-09-01
Supported by:
The National Natural Science Foundation of China(62172352);The National Natural Science Foundation of China(61871465);The Natural Science Foundation of Hebei Province(F2019203157);Science and Technology Research Project of Hebei Province Higher Education(ZD2019004);Innovation Capability Improvement Plan Project of Hebei Province(22567626H)

摘要/Abstract

摘要：

针对现有基于时序图的影响力最大化算法多因时间效率低或影响范围窄，不适用于大规模网络的问题，提出了一种融合启发式算法和贪心策略的种子节点挖掘算法（CHG）。首先，基于时序图中信息传播的时序性，给出了节点二阶度概念，并以此对节点影响力进行启发式评估；其次，根据影响力评估结果对节点进行初步过滤筛选，构建候选种子节点集；最后，通过计算候选种子节点的边际效应，解决节点间影响范围重叠问题，保证获取最优种子节点组合。在3个不同规模的时序网络数据集上进行了实验，实验结果表明，所提算法在相对较短的运行时间下，仍能够保证所得种子节点集具有较高的网络全局影响力，在时间效率与种子节点集影响范围2个方面取得了更好的平衡。

关键词: 时序图, 影响力最大化, 种子节点挖掘, 信息传播, 边际效应

Abstract:

Most of the existing maximizing influence algorithms based on temporal graph were not applicable for large-scale networks due to the low time efficiency or narrow influence range.Therefore, the seed node mining algorithm named CHG combining heuristic algorithm and greedy strategy was proposed.Firstly, based on the time sequence characteristics of information diffusion in temporal graph, the concept of two-order degree of nodes was given, and the influence of nodes was heuristically evaluated.Secondly, the nodes were filtered according to the influence evaluation results, and the candidate seed node set was constructed.Finally, the marginal effect of candidate seed nodes was calculated to solve the overlap of influence ranges between nodes to ensure the optimal combination of seed nodes.The experiments were carried out on three different scale data sets, and the results show that the proposed algorithm can ensure the high influence of the seed node set even though its running time is relatively shorter.And it can achieve a better trade-off between the time efficiency and the influence range of the seed node set.

Key words: temporal graph, influence maximization, seed node mining, information diffusion, marginal effect

中图分类号:

TP399

邹晓红, 许成伟, 陈晶, 宋彪, 王明月. 大规模时序图中种子节点挖掘算法研究[J]. 通信学报, 2022, 43(9): 157-168.

Xiaohong ZOU, Chengwei XU, Jing CHEN, Biao SONG, Mingyue WANG. Research on seed node mining algorithm in large-scale temporal graph[J]. Journal on Communications, 2022, 43(9): 157-168.

图/表 13

图1

图2

表1

表2

图3

图4

图5

图6

图7

图8

图9

图10

表3

参考文献 27

[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． NewYork:ACM Press, 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 Press, 2002: 61-70．
[3]	WU J , CHEN Z G , ZHAO M ． Information cache management and data transmission algorithm in opportunistic social networks［J］． Wireless Networks, 2019,25(6): 2977-2988．
[4]	HAN J D J , BERTIN N , HAO T ,et al． Evidence for dynamically organized modularity in the yeast protein-protein interaction network［J］． Nature, 2004,430(6995): 88-93．
[5]	MIRITELLO G , MORO E , LARA R ． Dynamical strength of social ties in information spreading［J］． Physical Review E,Statistical,Nonlinear,and Soft Matter Physics,2011:doi．org/10．1103/PhysRev E.83.045102．
[6]	WU H H , HUANG YU Z , CHENG J ,et al． Efficient processing of reachability and time-based path queries in a temporal graph［J］． arXiv Preprint,arXiv:1601．05909, 2016．
[7]	REDMOND U , CUNNINGHAM P ． Subgraph isomorphism in temporal networks［J］． arXiv Preprint,arXiv:1605．02174, 2016．
[8]	TAKAGUCHI T , YANO Y , YOSHIDA Y ． Coverage centralities for temporal networks［J］． The European Physical Journal B, 2016,89(2): 35．
[9]	吴安彪, 袁野, 乔百友 ,等．大规模时序图影响力最大化的算法研究［J］．计算机学报, 2019,42(12): 2647-2664．
	WU A B , YUAN Y , QIAO B Y ,et al． The influence maximization problem based on large-scale temporal graph［J］． Chinese Journal of Computers, 2019,42(12): 2647-2664．
[10]	陈晶, 祁子怡．基于时序关系的社交网络影响最大化算法研究［J］．通信学报, 2020,41(10): 211-221．
	CHEN J , QI Z Y ． Research on social network influence maximization algorithm based on time sequential relationship［J］． Journal on Communications, 2020,41(10): 211-221．
[11]	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 Press, 2003: 137-146．
[12]	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 Press, 2007: 420-429．
[13]	CHEN W , WANG Y J , YANG S Y ． Efficient influence maximization in social networks［C］// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining． New York:ACM Press, 2009: 199-208．
[14]	BAGHERI E , DASTGHAIBYFARD G , HAMZEHA ． FAIMCS:a fast and accurate influence maximization algorithm in social networks based on community structures［J］． Computational Intelligence, 2021,37(4): 1779-1802．
[15]	王帅, 刘静．一种针对网络结构破坏下鲁棒影响力最大化问题的Memetic算法［J］．计算机学报, 2021,44(6): 1153-1167．
	WANG S , LIU J ． A memetic algorithm for solving the robust influence maximization problem towards network structural perturbances［J］． Chinese Journal of Computers, 2021,44(6): 1153-1167．
[16]	TONG G M , WANG R Q , DONG Z ,et al． Time-constrained adaptive influence maximization［J］． IEEE Transactions on Computational Social Systems, 2021,8(1): 33-44．
[17]	YANG Y , YAN D , WU H H ,et al． Diversified temporal subgraph pattern mining［C］// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining． New York:ACM Press, 2016: 1965-1974．
[18]	SHENG W , SONG W B , LI D ,et al． Dynamic influence maximization via network representation learning［J］． Frontiers in Physics, 2022,9:827468．
[19]	WANG Y H , FAN Q , LI Y C ,et al． Real-time influence maximization on dynamic social streams［J］． Proceedings of the VLDB Endowment, 2017,10(7): 805-816．
[20]	ROSSI I , MUSOLESIM．TORSELLO A ,, ． On the k-anonymization of time-varying and multi-layer social graphs［C］// Proceedings of the 9th Internation AAAI Conference on Web and Social Media． Palo Alto:AAAI Press, 2015: 377-386．
[21]	王一舒, 袁野, 刘萌 ,等．大规模时序图数据的查询处理与挖掘技术综述［J］．计算机研究与发展, 2018,55(9): 1889-1902．
	WANG Y S , YUAN Y , LIU M ,et al． Survey of query processing and mining techniques over large temporal graph database［J］． Journal of Computer Research and Development, 2018,55(9): 1889-1902．
[22]	ZHANG M , DAI C N , DING C ,et al． Probabilistic solutions of influence propagation on social networks［C］// Proceedings of the 22nd ACM International Conference on Information ＆ Knowledge Management． New York:ACM Press, 2013: 429-438．
[23]	李美玲, 钱付兰, 徐涛 ,等．基于种子候选的贪心策略影响力最大化算法［J］．模式识别与人工智能, 2020,33(11): 1033-1042．
	LI M L , QIAN F L , XU T ,et al． Greedy strategy influence maximization algorithm based on seed candidates［J］． Pattern Recognition and Artificial Intelligence, 2020,33(11): 1033-1042．
[24]	WALKERS K ． Connected:the surprising power of our social networks and how they shape our lives［J］． Journal of Family Theory ＆ Review, 2011,3(3): 220-224．
[25]	BARABASIAL ALBERT R ． Emergence of scaling in random networks［J］． Science, 1999,286(5439): 509-512．
[26]	ROSSI R , AHMED N ． The network data repository with interactive graph analytics and visualization［C］// Proceedings of the 29th AAAI Conference on Artificial Intelligence． Palo Alto:AAAI Press, 2015: 4292-4293．
[27]	LESKOVEC J , KREVL A ． SNAP datasets:Stanford large network dataset collection［EB］． 2014.

节点	第1轮	第2轮	Max_Inf	Max_node
a	100 √	—	—	—
b	80	30	30	b
c	60	50	50	c√
d	40	—	—	—
e	30	—	—	—

数据集	节点数/个	边数/条	时间跨度/天
Digg	7 786	132 506	56
Mathoverflow	21 688	107 581	2 350
Superuser	101 052	356 822	2 735

算法	Digg/s	Mathoverflow/s	Superuser/s
CHG	4.1	6.9	9.2
IMIT	12.9	46.4	154.2
TIM	3.9	5.4	8.6
Degree	1.7	2.2	3.2
DegreeDiscount	2.6	3.8	5.5
Random	0.8	0.9	1.2

大规模时序图中种子节点挖掘算法研究

Research on seed node mining algorithm in large-scale temporal graph

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 27

相关文章 10

Metrics

推荐阅读 0

[1]	王璿, 张瑜, 周军锋, 陈子阳. 基于社交网络的影响力最大化算法[J]. 通信学报, 2022, 43(8): 151-163.
[2]	顾秋阳, 吴宝, 孙兆洋, 池仁勇. 基于改进灰狼优化的复杂网络重要节点识别算法[J]. 通信学报, 2021, 42(6): 72-83.
[3]	陈晶,祁子怡. 基于时序关系的社交网络影响最大化算法研究[J]. 通信学报, 2020, 41(10): 211-221.
[4]	王晓萌, 方滨兴, 张宏莉, 王星. TSL：基于连接强度的Facebook消息流行度预测模型[J]. 通信学报, 2019, 40(10): 1-9.
[5]	李凤华,王彦超,殷丽华,谢绒娜,熊金波. 面向网络空间的访问控制模型[J]. 通信学报, 2016, 37(5): 9-20.
[6]	陈侃,陈亮,朱培栋,熊岳山. 基于交互行为的在线社会网络水军检测方法[J]. 通信学报, 2015, 36(7): 120-128.
[7]	刘衍珩1,2，李飞鹏1,2，孙鑫1,2，朱建启1,2. 基于信息传播的社交网络拓扑模型[J]. 通信学报, 2013, 34(4): 1-9.
[8]	刘衍珩,李飞鹏,孙鑫,朱建启. 基于信息传播的社交网络拓扑模型[J]. 通信学报, 2013, 34(4): 1-9.
[9]	吴大鹏,张普宁,王汝言. 节点连接态势感知的低开销机会网络消息传输策略[J]. 通信学报, 2013, 34(3): 44-52.
[10]	于洪,杨显. 微博中节点影响力度量与传播路径模式研究[J]. 通信学报, 2012, 33(Z1): 96-102.