基于零模型的含时网络模体识别方法

doi:10.11772/j.issn.1001-9081.2022071033

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (8): 2505-2510.DOI: 10.11772/j.issn.1001-9081.2022071033

所属专题：先进计算

基于零模型的含时网络模体识别方法

胡博仁¹, 裴忠民¹(), 罗章凯¹, 丁杰²

^1.复杂电子系统仿真重点实验室（航天工程大学），北京 101416
^2.航天工程大学电子与光学工程系，北京 101416

收稿日期:2022-07-15 修回日期:2022-10-12 接受日期:2022-10-13 发布日期:2023-01-04 出版日期:2023-08-10
通讯作者: 裴忠民
作者简介:胡博仁（1999—），男，湖南宁乡人，硕士研究生，主要研究方向：网络模体
罗章凯（1989—），男，安徽滁州人，助理研究员，博士，主要研究方向：通信与信息系统、复杂网络
丁杰（1998—），女，安徽六安人，硕士研究生，主要研究方向：通信与信息系统。
基金资助:
复杂电子系统仿真重点实验室资助项目(DXZT?JC?ZZ?2020?001)

Temporal network motif discovery method based on null model

Boren HU¹, Zhongmin PEI¹(), Zhangkai LUO¹, Jie DING²

^1.Key Laboratory of Complex Electronic System Simulation （Space Engineering University），Beijing 101416，China
^2.Department of Electronics and Optical Engineering，Space Engineering University，Beijing 101416，China

Received:2022-07-15 Revised:2022-10-12 Accepted:2022-10-13 Online:2023-01-04 Published:2023-08-10
Contact: Zhongmin PEI
About author:HU Boren， born in 1999， M. S. candidate. His research interests include network motif.
LUO Zhangkai， born in 1989， Ph. D， assistant research fellow. His research interests include communications and information systems， complex network.
DING Jie， born in 1998， M. S. candidate. Her research interests include communications and information systems.
Supported by:
Science and Technology on Complex Electronic System Simulation Laboratory Project(DXZT-JC-ZZ-2020-001)

摘要/Abstract

摘要：

在带有时间属性的含时网络中，常规的基于频繁子图统计的网络模体识别方法容易受网络规模与结构差异的影响。而与实证网络具有相同规模和某些相同性质的零模型网络能为实证网络的特性挖掘提供了准确的基准，于是提出一种基于零模型的含时网络模体识别方法，用两种网络子图特征比较后的相对值来识别含时网络中的具有显著结构意义的子图。同时，为确定零模型网络何时达到稳定，采用成功置乱次数方法来改进基于时间置乱或时间随机化的含时网络零模型构造方法。在实验阶段，对包含卫星和地面站的46节点全球定位系统（GPS）星座进行仿真实验，确定了零模型网络子图特征稳定时的成功置乱次数；构造10个零模型网络与卫星网络比较，发现反映节点连接具有连续性特点的子图的出现次数仅为最高频子图的1/34，却是卫星网络中最重要的模体。实验结果表明，以零模型为参照的含时网络模体识别方法能更准确地识别出反映网络结构特性和动态变化过程的模体。

关键词: 含时网络, 模体识别, 零模型, 成功置乱次数, 卫星网络

Abstract:

In temporal networks with time attributes， conventional network motif discovery methods based on frequent subgraph statistics are easily affected by the differences in network size and structure. And an accurate benchmark for characteristic mining of empirical network can be provided by the null model network with same scale and some properties of the empirical network. Therefore， a temporal network motif discovery method based on null model was proposed to use relative values after comparing the features of the two network subgraphs to identify the subgraphs with significant structural meaning in temporal networks. At the same time， in order to determine when null model network reached stability， the method of successful scrambling times was adopted to improve the temporal network’s null model construction methods based on time scrambling or time randomization. In experiment stage， simulations were conducted on 46-node Global Positioning System （GPS） constellation containing satellites and ground stations， the number of successful scrambles times when the subgraph features of null model network reached stability was determined. Ten null model networks were constructed and compared with the satellite network. It was found that the number of occurrences of subgraph reflecting the continuity characteristics of node connection is only 1/34 of that of the subgraph with the highest frequency， but the former subgraph is the most important motif in the satellite network. Experimental results show that the temporal network’s motif discovery method with null model as reference can identify motifs that reflects network structural characteristics and dynamic change process more accurately.

Key words: temporal network, motif discovery, null model, successful scrambling times, satellite network

中图分类号:

TP393

胡博仁, 裴忠民, 罗章凯, 丁杰. 基于零模型的含时网络模体识别方法[J]. 计算机应用, 2023, 43(8): 2505-2510.

Boren HU, Zhongmin PEI, Zhangkai LUO, Jie DING. Temporal network motif discovery method based on null model[J]. Journal of Computer Applications, 2023, 43(8): 2505-2510.

图/表 10

图1 时间置乱零模型构造方法示意图

Fig. 1 Schematic diagram of time scrambling null model construction method

图2 时间随机化零模型构造方法示意图

Fig. 2 Schematic diagram of time randomized null model construction method

图3 含时网络模体识别方法流程

Fig. 3 Flow of temporal network motif discovery method

图4 受δ约束的含时网络子图

Fig. 4 Subgraphs of temporal network constrained by δ

图5 仿真加权卫星网络

Fig. 5 Simulated weighted satellite network

图6 36种二节点三边和三节点三边有向子图的示意（子图中的数字代表边的先后发生顺序）

Fig. 6 Schematic diagrams of 36 kinds of two-node three-side and three-node three-side directed subgraphs

图7 原始网络与时间置乱零模型网络的子图出现频率比值

Fig. 7 Occurrence frequency ratio of subgraph of original network to subgraph of time scrambling null model network

图8 原始网络与时间随机化零模型网络的子图出现频率比值

Fig. 8 Occurrence frequency ratio of subgraph of original network to subgraph of time randomized null model network

表1 两种零模型构造算法下结果达到稳定所需的成功置乱次数

Tab. 1 Under the two null model construction algorithms， number of successful scrambling required for results to reach stability

子图	零模型构造算法		子图	零模型构造算法
子图	时间置乱	时间随机化	子图	时间置乱	时间随机化
M_5，6	0.3L	0.5L	M_6，2	0.5L	0.9L
M_4，2	0.4L	0.7L	M_6，1	0.6L	1.1L
M_6，6	0.4L	0.8L	M_4，6	0.2L	0.3L
M_5，1	0.4L	0.9L

表2 时间置乱零模型网络子图的统计特征

Tab. 2 Statistical characteristics of subgraphs of time scrambling null model network

子图	原始网络中的出现次数	零模型网络中的平均出现次数	P	D	Z
M_5，6	1.51×N_5，6	N_5，6=9.57×10⁸	0	≤0.51	0.120
M_4，2	2.08×N_4，2	N_4，2=6.95×10⁸	0	≤1.08	0.156
M_6，6	2.22×N_6，6	N_6，6=4.12×10⁸	0	≤1.22	0.314
M_5，1	2.68×N_5，1	N_5，1=4.92×10⁷	0	≤1.68	0.431
M_6，2	2.95×N_6，2	N_6，2=2.98×10⁷	0	≤1.95	0.471
M_6，1	4.25×N_6，1	N_6，1=1.03×10⁷	0	≤3.25	0.574
M_4，6	0.22×N_4，6	N_4，6=2.82×10⁸	1	无	-0.354

参考文献 26

1	刘亮. 复杂网络基元研究方法及应用［M］. 上海：上海交通大学出版社， 2018：1-5.
	LIU L. Complex Network Building Blocks Methods and Applications［M］. Shanghai： Shanghai Jiao Tong University Press， 2018：1-5.
2	刘亮. 国家应急管理工作组合作网络的基元结构辨识［J］. 中国安全科学学报， 2016， 26（3）：133-138. 10.16265/j.cnki.issn1003-3033.2016.03.023
	LIU L. Building blocks in collaboration network of national emergency management working groups［J］. China Safety Science Journal， 2016， 26（3）：133-138. 10.16265/j.cnki.issn1003-3033.2016.03.023
3	缪莉莉，韩传峰，刘亮，等. 基于模体的科学家合作网络基元特征分析［J］. 科学学研究， 2012， 30（10）：1468-1475.
	MIAO L L， HAN C F， LIU L， et al. Using motif to characterize building block of scientific collaboration networks［J］. Studies in Science of Science， 2012， 30（10）：1468-1475.
4	BAUMES J， GOLDBERG M， KRISHNAMOORTHY M S， et al. Finding communities by clustering a graph into overlapping subgraphs［C/OL］// Proceedings of the 2005 IADIS International Conference on Applied Computing ［2022-03-22］..
5	SHERVASHIDZE N， VISHWANATHAN S V N， PETRI T H， et al. Efficient graphlet kernels for large graph comparison［C］// Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. New York： JMLR.org， 2009：488-495.
6	BATAGELJ V， ZAVERŠNIK M. An O（m） algorithm for cores decomposition of networks［EB/OL］. （2003-10-25）［2022-03-22］..
7	BELTH C， ZHENG X Y， KOUTRA D. Mining persistent activity in continually evolving networks［C］// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2020： 934-944. 10.1145/3394486.3403136
8	BOEKHOUT H D， KOSTERS W A， TAKES F W. Efficiently counting complex multilayer temporal motifs in large-scale networks［J］. Computational Social Networks， 2019， 6： No.8. 10.1186/s40649-019-0068-z
9	TU K， LI J， TOWSLEY D， et al. gl2vec： learning feature representation using graphlets for directed networks［C］// Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York： ACM， 2019：216-221. 10.1145/3341161.3342908
10	MILO R， SHEN-ORR S， ITZKOVITZ S， et al. Network motifs： simple building blocks of complex networks［J］. Science， 2002， 298（5594）：824-827. 10.1126/science.298.5594.824
11	辜姣，郭龙，江健，等. 多层网络和含时网络的相关问题研究［J］. 复杂系统与复杂性科学， 2016， 13（1）：58-63， 67. 10.13306/j.1672-3813.2016.01.004
	GU J， GUO L， JIANG J， et al. Recent progress on multiplayer and temporal networks［J］. Complex Systems and Complexity Science， 2016， 13（1）：58-63， 67. 10.13306/j.1672-3813.2016.01.004
12	HOLME P， SARAMÄKI J. Temporal networks［J］. Physics Reports， 2012， 519（3）： 97-125. 10.1016/j.physrep.2012.03.001
13	PARANJAPE A， BENSON A R， LESKOVEC J. Motifs in temporal networks［C］// Proceedings of the 10th ACM International Conference on Web Search and Data Mining. New York： ACM， 2017：601-610. 10.1145/3018661.3018731
14	LIU P H， GUARRASI V， SARIYÜCE A E. Temporal network motifs： models， limitations， evaluation［J］. IEEE Transactions on Knowledge and Data Engineering， 2023， 35（1）： 945-957.
15	SARPE I， VANDIN F. odeN： simultaneous approximation of multiple motif counts in large temporal networks［C］// Proceedings of the 30th ACM International Conference on Information and Knowledge Management. New York： ACM， 2021： 1568-1577. 10.1145/3459637.3482459
16	ZHAO Q K， TIAN Y， HE Q， et al. Communication motifs： a tool to characterize social communications［C］// Proceedings of the 19th ACM International Conference on Information and Knowledge Management. New York： ACM， 2010： 1645-1648. 10.1145/1871437.1871694
17	ZENG T C， SEMIARI O， SAAD W. Spatio-temporal motifs for optimized Vehicle-to-Vehicle （V2V） communications［C］// Proceedings of the 2018 International Conference on Computing， Networking and Communications. Piscataway： IEEE， 2018： 789-794. 10.1109/iccnc.2018.8390386
18	陈泉，杨建梅，曾进群. 零模型及其在复杂网络研究中的应用［J］. 复杂系统与复杂性科学， 2013， 10（1）：8-17. 10.3969/j.issn.1672-3813.2013.01.004
	CHEN Q， YANG J M， ZENG J Q. Null model and its application in the research of complex networks［J］. Complex Systems and Complexity Science， 2013， 10（1）：8-17. 10.3969/j.issn.1672-3813.2013.01.004
19	于咏平. 时变网络上零模型的构造算法及应用［J］. 无线互联科技， 2019， 16（5）：114-116. 10.3969/j.issn.1672-6944.2019.05.048
	YU Y P. Study on the construction algorithm and application of zero model on time-varying network［J］. Wireless Internet Technology， 2019， 16（5）：114-116. 10.3969/j.issn.1672-6944.2019.05.048
20	许小可，崔文阔，崔丽艳，等. 无权网络零模型的构造及应用［J］. 电子科技大学学报， 2019， 48（1）：122-141. 10.3969/j.issn.1001-0548.2019.01.020
	XU X K， CUI W K， CUI L Y， et al. Construction and applications of null models for unweighted networks［J］. Journal of University of Electronic Science and Technology of China， 2019， 48（1）：122-141. 10.3969/j.issn.1001-0548.2019.01.020
21	MAHADEVAN P. Mechanisms for generating realistic annotated internet topologies［D］. La Jolla， CA： University of California， San Diego， 2007：52-71.
22	尚可可，许小可. 基于置乱算法的复杂网络零模型构造及其应用［J］. 电子科技大学学报， 2014， 43（1）：7-20. 10.3969/j.issn.1001-0548.2014.01.002
	SHANG K K， XU X K. Construction and application for null models of complex networks based on randomized algorithms［J］. Journal of University of Electronic Science and Technology of China， 2014， 43（1）：7-20. 10.3969/j.issn.1001-0548.2014.01.002
23	曾进群，杨建梅，陈泉，等. 基于零模型的开源社区大众生产合作网络结构研究［J］. 华南理工大学学报（社会科学版）， 2013， 15（2）：29-34. 10.3969/j.issn.1007-7375.2013.03.018
	ZENG J Q， YANG J M， CHEN Q， et al. Research of the open source community cooperation network structure of the mass production based on null model［J］. Journal of South China University of Technology （Social Science Edition）， 2013， 15（2）：29-34. 10.3969/j.issn.1007-7375.2013.03.018
24	王鑫厅，侯亚丽，梁存柱，等. 基于不同零模型的点格局分析［J］. 生物多样性， 2012， 20（2）：151-158. 10.3724/sp.j.1003.2012.08163
	WANG X T， HOU Y L， LIANG C Z， et al. Point pattern analysis based on different null models for detecting spatial patterns［J］. Biodiversity Science， 2012， 20（2）：151-158. 10.3724/sp.j.1003.2012.08163
25	李欢，卢罡，郭俊霞. 复杂网络零模型的量化评估［J］. 计算机应用， 2015， 35（6）：1560-1563， 1572. 10.11772/j.issn.1001-9081.2015.06.1560
	LI H， LU G， GUO J X. Quantitative evaluation for null models of complex networks［J］. Journal of Computer Applications， 2015， 35（6）：1560-1563， 1572. 10.11772/j.issn.1001-9081.2015.06.1560
26	高贺. 北斗导航系统星间链路分配方法研究［D］. 长沙：湖南大学， 2018：19-22.
	GAO H. Research on inter-satellite link allocation method in Beidou Navigation Systems［D］. Changsha： Hunan University， 2018：19-22.

[1]	薛舒红, 冯彪, 于海龙, 王力, 杨云云. 多路复用网络中的模体检测算法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 752-759.
[2]	贾梦瑶, 王兴伟, 张爽, 易波, 黄敏. 基于软件定义网络的卫星网络容错路由机制[J]. 计算机应用, 2019, 39(6): 1772-1779.
[3]	王亚琼, 史国振, 谢绒娜, 李凤华, 王雅哲. 卫星网络中支持策略隐藏的多授权访问控制方案[J]. 计算机应用, 2019, 39(2): 470-475.
[4]	李欢, 卢罡, 郭俊霞. 复杂网络零模型的量化评估[J]. 计算机应用, 2015, 35(6): 1560-1563.
[5]	周星刘军董春冻张玉静. 对辅助定位按需路由协议的安全性改进[J]. 计算机应用, 2013, 33(06): 1619-1629.
[6]	潘艳辉王韬吴杨郑燕茹. 基于组密钥序列卫星网络组密钥协商协议[J]. 计算机应用, 2012, 32(04): 964-967.
[7]	潘艳辉王韬吴杨王文豪. 卫星网络基于信任的认证路由协议[J]. 计算机应用, 2011, 31(03): 781-783.
[8]	陈炳才韩亚萍郭黎利聂伯勋. 低轨卫星网络支持飞机用户的切换管理算法[J]. 计算机应用, 2009, 29(08): 2194-2197.

基于零模型的含时网络模体识别方法

Temporal network motif discovery method based on null model

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 26

相关文章 8

编辑推荐

Metrics