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

Xiaohong ZOU; Chengwei XU; Jing CHEN; Biao SONG; Mingyue WANG

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

您当前的位置：

首页 >

文章列表页 >

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

Papers | 更新时间：2024-06-05

- Research on seed node mining algorithm in large-scale temporal graph
- Journal on Communications Vol. 43, Issue 9, Pages: 157-168(2022)
- 作者机构：
  
  1. 燕山大学信息科学与工程学院，河北秦皇岛 066004
  2. 河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛 066004
- 作者简介：
- 基金信息：
  
  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);The Innovation Capability Improvement Plan Project of Hebei Province(22567626H)
- DOI：10.11959/j.issn.1000-436x.2022170
  CLC： TP399
- Online First：2022-09，
  
  Published：25 September 2022
- 稿件说明：
移动端阅览
Xiaohong ZOU, Chengwei XU, Jing CHEN, et al. Research on seed node mining algorithm in large-scale temporal graph[J]. Journal on Communications, 2022, 43(9): 157-168.
DOI：

Xiaohong ZOU, Chengwei XU, Jing CHEN, et al. Research on seed node mining algorithm in large-scale temporal graph[J]. Journal on Communications, 2022, 43(9): 157-168. DOI： 10.11959/j.issn.1000-436x.2022170.

摘要

针对现有基于时序图的影响力最大化算法多因时间效率低或影响范围窄，不适用于大规模网络的问题，提出了一种融合启发式算法和贪心策略的种子节点挖掘算法（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.

关键词

Keywords

references

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 ．

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 ．

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 ．

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 ．

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 ．

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 ．

REDMOND U , CUNNINGHAM P ． Subgraph isomorphism in temporal networks ［J］． arXiv Preprint,arXiv:1605．02174 , 2016 ．

TAKAGUCHI T , YANO Y , YOSHIDA Y ． Coverage centralities for temporal networks ［J］． The European Physical Journal B , 2016 , 89 ( 2 ): 35 ．

吴安彪 , 袁野 , 乔百友 , 等．大规模时序图影响力最大化的算法研究［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 ．

陈晶 , 祁子怡．基于时序关系的社交网络影响最大化算法研究［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 ．

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 ．

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 ．

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 ．

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 ．

王帅 , 刘静．一种针对网络结构破坏下鲁棒影响力最大化问题的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 ．

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 ．

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 ．

SHENG W , SONG W B , LI D , et al ． Dynamic influence maximization via network representation learning ［J］． Frontiers in Physics , 2022 ,9:827468．

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 ．

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 ．

王一舒 , 袁野 , 刘萌 , 等．大规模时序图数据的查询处理与挖掘技术综述［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 ．

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 ．

李美玲 , 钱付兰 , 徐涛 , 等．基于种子候选的贪心策略影响力最大化算法［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 ．

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 ．

BARABASIAL ALBERT R ． Emergence of scaling in random networks ［J］． Science , 1999 , 286 ( 5439 ): 509 - 512 ．

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 ．

LESKOVEC J , KREVL A ． SNAP datasets:Stanford large network dataset collection ［EB］． 2014 .

Views

780

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Identification of key node groups based on motif structure and degree information

Influence maximization algorithm based on social network

TSL:predicting popularity of Facebook content based on tie strength

Interaction based on method for spam detection in online social networks

Related Author

Yunyun YANG

Liao ZHANG

Hailong YU

Li WANG

Xuan WANG

Yu ZHANG

Junfeng ZHOU

Ziyang CHEN

Related Institution

School of Electrical and Power Engineering, Taiyuan University of Technology

School of Computer Science and Technology, Donghua University

School of Information Management, Shanghai Lixin University of Accounting and Finance

Research Center of Computer Network and Information Security Technology,Harbin Institute of Technology

Cyberspace Institute of Advanced Technology,Guangzhou University

AI问答

⁰