流模式下有向近似覆盖图算法研究

张昕; 李晓光

doi:10.7544/issn1000-1239.2019.20170680

流模式下有向近似覆盖图算法研究

张昕,
李晓光

(辽宁大学信息学院沈阳 110036) (zhangxin1979@hotmail.com)

基金项目: 国家自然科学基金项目(U1811261,61802160)；辽宁省公共舆情与网络安全大数据系统工程实验室基金项目(2016-294)

详细信息

中图分类号: TP311
计量
- 文章访问数: 898
- HTML全文浏览量: 0
- PDF下载量: 247
出版历程
- 发布日期: 2019-02-28

Spanner Algorithm for Directed Graph Stream

(College of Information, Liaoning University, Shenyang 110036)

摘要

摘要: 随着社交网络、交通网络、生物信息网等领域的分析需求快速增长,大规模图数据的处理逐渐成为信息技术领域新的挑战.近似覆盖图技术可以通过选取原图的子图,同时保证子图中任意节点间距离的增加在覆盖因子的约束范围内,从而降低大规模图存储与计算开销.当前相关工作主要研究无向图的近似覆盖图技术,针对于此,提出一种有向近似覆盖图算法,重新定义了簇集以及簇边、桥边、自由边3类关建边,并理论分析基于3类关键边的(3,2)近似覆盖图构建正确性.在此基础上,给出图数据以流模式到达时的近似覆盖图计算算法.算法通过判断边端点的类型进行边的积累聚簇及更新,进而得到全图近似覆盖结果,算法空间复杂度为O(n\+2/4).最后以基于幂率模型的人工数据集为实验对象,验证算法满足覆盖因子(3,2)的有向近似覆盖图定义,且空间与时间开销较小.
- 有向图 /
- 近似覆盖图 /
- 覆盖因子 /
- 聚簇 /
- 数据流
Abstract: With the rapid growth of analysis demand in many fields such as social network, transportation network, and bioinformatics network, the processing of large-scale graph data has become a new challenge of information technology. Graph spanner is a subgraph in which the distance between every pair of vertices falling into the given range defined by stretch factor. With the spanner, the storage and computational cost are reduced greatly for large-scale graph data processing. Most of existing research work focused on the spanner on undirected graph, and we propose an effective algorithm for directed graph spanner. Firstly, we re-define the concept of cluster set and three kinds of crucial edges including cluster edge, bridge edge and free edge, and analyze theoretically the correctness of (3,2)-spanner construction based on the crucial edges. Moreover, we propose a spanner algorithm for graph data in streaming model in which the edges is clustered and updated according to the type of end-point of edge, and then a (3,2)-spanner of full graph is constructed. Finally, we provide the theoretical analysis of space complexity O(n\+2/4), and present the experiments on the synthetic graph of power law model. Experiment results show our algorithm meet the definition of (3,2)-spanner, and has low time and space overhead.
- directed graph /
- spanner /
- stretch factor /
- cluster /
- data stream

HTML全文

参考文献(0)

施引文献(52)

期刊类型引用(20)

1.	徐宁，李静秋，王岚君，刘安安. 时序特性引导下的谣言事件检测方法评测. 南京大学学报(自然科学). 2025(01): 71-82 . 百度学术
2.	张元园，袁嘉霁. 基于社交媒体的谣言检测研究综述. 数据通信. 2024(01): 28-33 . 百度学术
3.	廖劲智，赵和伟，连小童，纪文亮，石海明，赵翔. 基于对比图学习的跨文档虚假信息检测. 计算机科学. 2024(03): 14-19 . 百度学术
4.	凤丽洲，刘馥榕，王友卫. 基于图卷积网络和注意力机制的谣言检测方法. 数据分析与知识发现. 2024(04): 125-136 . 百度学术
5.	王晰巍，孙哲，姜奕冰，李玥琪. 社交媒体网络辟谣回音室效应分析模型及实验研究. 现代情报. 2024(10): 3-17 . 百度学术
6.	朱奕，王根生，金文文，黄学坚，李胜. 基于文本语义增强和评论立场加权的网络谣言检测. 计算机科学与探索. 2024(12): 3311-3323 . 百度学术
7.	甘臣权，付祥，冯庆东，祝清意. 基于公共情感特征压缩与融合的轻量级图文情感分析模型. 计算机研究与发展. 2023(05): 1099-1110 . 本站查看
8.	聂大成，汪明达，刘世钰，杨慧，张翔，邱鸿杰. 在线社会网络虚假信息检测关键技术研究综述. 通信技术. 2023(04): 391-399 . 百度学术
9.	李卓远，李军. 基于对比学习的多模态注意力网络虚假信息检测方法. 中国科技论文. 2023(11): 1192-1197 . 百度学术
10.	强子珊，顾益军. 基于多模态异质图的社交媒体谣言检测模型. 数据分析与知识发现. 2023(11): 68-78 . 百度学术
11.	陈志毅，隋杰. 基于DeepFM和卷积神经网络的集成式多模态谣言检测方法. 计算机科学. 2022(01): 101-107 . 百度学术
12.	陆恒杨，范晨悠，吴小俊. 面向网络社交媒体的少样本新冠谣言检测. 中文信息学报. 2022(01): 135-144+172 . 百度学术
13.	唐樾，马静. 基于增强对抗网络和多模态融合的谣言检测方法. 情报科学. 2022(06): 108-114+131 . 百度学术
14.	王壮，隋杰. 基于多级融合的多模态谣言检测模型. 计算机工程与设计. 2022(06): 1756-1761 . 百度学术
15.	吴诗苑，董庆兴，宋志君，张斌. 社交媒体中错误信息的检测方法研究述评. 情报学报. 2022(06): 651-661 . 百度学术
16.	范伟，刘勇. 基于时空Transformer的社交网络信息传播预测. 计算机研究与发展. 2022(08): 1757-1769 . 本站查看
17.	姜梦函，李邵梅，吴子仪，张建朋. 多模态特征融合的中文谣言检测. 信息工程大学学报. 2022(04): 485-490 . 百度学术
18.	孟佳娜，王晓培，李婷，刘爽，赵迪. 基于对抗神经网络的跨模态谣言检测. 数据分析与知识发现. 2022(12): 32-42 . 百度学术
19.	徐铭达，张子柯，许小可. 基于模体度的社交网络虚假信息传播机制研究. 计算机研究与发展. 2021(07): 1425-1435 . 本站查看
20.	胡斗，卫玲蔚，周薇，淮晓永，韩冀中，虎嵩林. 一种基于多关系传播树的谣言检测方法. 计算机研究与发展. 2021(07): 1395-1411 . 本站查看