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

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

Abstract

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

CLC Number:

TP399

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.

Figures/Tables 13

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

节点	第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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 27

Related Articles 7

Metrics

Recommended 0

[1]	Jian SHU, Jiawei SHI, Linlan LIU, Al-Kali Manar. Topology prediction for opportunistic network based on spatiotemporal convolution [J]. Journal on Communications, 2023, 44(3): 145-156.
[2]	Xuan WANG, Yu ZHANG, Junfeng ZHOU, Ziyang CHEN. Influence maximization algorithm based on social network [J]. Journal on Communications, 2022, 43(8): 151-163.
[3]	Peng WANG, Xiushe ZHANG, Long SUO, Keyi SHI. Time deterministic network routing algorithm based on stochastic temporal graph [J]. Journal on Communications, 2021, 42(9): 21-30.
[4]	Jing CHEN,Ziyi QI. Research on social network influence maximization algorithm based on time sequential relationship [J]. Journal on Communications, 2020, 41(10): 211-221.
[5]	Xiaomeng WANG, Binxing FANG, Hongli ZHANG, Xing WANG. TSL:predicting popularity of Facebook content based on tie strength [J]. Journal on Communications, 2019, 40(10): 1-9.
[6]	Kan CHEN,Liang CHEN,Pei-dong ZHU,Yue-shan XIONG. Interaction based on method for spam detection in online social networks [J]. Journal on Communications, 2015, 36(7): 120-128.
[7]	Da-peng WU,Pu-ning ZHANG,Ru-yan WANG. Connection status aware cost efficient message transmission mechanism in opportunistic networks [J]. Journal on Communications, 2013, 34(3): 44-52.