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

邹晓红; 许成伟; 陈晶; 宋彪; 王明月

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 大规模时序图中种子节点挖掘算法研究
- Research on seed node mining algorithm in large-scale temporal graph
- 通信学报 2022年43卷第9期页码：157-168
- 作者机构：
  
  1. 燕山大学信息科学与工程学院，河北秦皇岛 066004
  2. 河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛 066004
- 作者简介：
  
  [ "邹晓红（1967- ），女，吉林省吉林市人，博士，燕山大学教授、硕士生导师，主要研究方向为图挖掘、社会网络、复杂网络分析等" ]
  [ "许成伟（1997- ），男，黑龙江齐齐哈尔人，燕山大学硕士生，主要研究方向为社交网络" ]
  [ "陈晶（1976- ），女，河北秦皇岛人，博士，燕山大学教授、硕士生导师，主要研究方向为对等网络、社会计算、Web服务等" ]
  [ "宋彪（1996- ），男，河北张家口人，燕山大学硕士生，主要研究方向为不确定图挖掘" ]
  [ "王明月（1996- ），女，河北秦皇岛人，燕山大学硕士生，主要研究方向为社交网络" ]
- 基金信息：
  
  国家自然科学基金资助项目(62172352);国家自然科学基金资助项目(61871465);河北省自然科学基金资助项目(F2019203157);河北省高等学校科学技术研究项目(ZD2019004);河北省创新能力提升计划基金资助项目(22567626H)
- DOI：10.11959/j.issn.1000-436x.2022170
  中图分类号： TP399
- 网络出版日期：2022-09，
  
  纸质出版日期：2022-09-25
- 稿件说明：
移动端阅览
邹晓红, 许成伟, 陈晶, 等. 大规模时序图中种子节点挖掘算法研究[J]. 通信学报, 2022,43(9):157-168.

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.
邹晓红, 许成伟, 陈晶, 等. 大规模时序图中种子节点挖掘算法研究[J]. 通信学报, 2022,43(9):157-168. DOI： 10.11959/j.issn.1000-436x.2022170.

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 .

浏览量

293

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于模体结构和度信息的关键节点组识别

基于社交网络的影响力最大化算法

TSL：基于连接强度的Facebook消息流行度预测模型

基于交互行为的在线社会网络水军检测方法