Temporal network motif discovery method based on null model

doi:10.11772/j.issn.1001-9081.2022071033

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (8): 2505-2510.DOI: 10.11772/j.issn.1001-9081.2022071033

Special Issue: 先进计算

• Advanced computing • Previous Articles Next Articles

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)

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

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

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

通讯作者: 裴忠民
作者简介:胡博仁（1999—），男，湖南宁乡人，硕士研究生，主要研究方向：网络模体
罗章凯（1989—），男，安徽滁州人，助理研究员，博士，主要研究方向：通信与信息系统、复杂网络
丁杰（1998—），女，安徽六安人，硕士研究生，主要研究方向：通信与信息系统。
基金资助:
复杂电子系统仿真重点实验室资助项目(DXZT?JC?ZZ?2020?001)

Abstract

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

摘要：

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

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

CLC Number:

TP393

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.

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

Figures/Tables 10

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

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

Fig. 3 Flow of temporal network motif discovery method

Fig. 4 Subgraphs of temporal network constrained by δ

Fig. 5 Simulated weighted satellite network

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

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

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

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

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

References 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]	Zhiyuan XI, Chao TANG, Anyang TONG, Wenjian WANG. Driver behavior recognition based on dual-path spatiotemporal network [J]. Journal of Computer Applications, 2024, 44(5): 1511-1519.
[2]	Shuhong XUE, Biao FENG, Hailong YU, Li WANG, Yunyun YANG. Motif detection algorithm in multiplex networks [J]. Journal of Computer Applications, 2024, 44(3): 752-759.
[3]	Guoshuai MA, Yuhua QIAN, Yayu ZHANG, Junxia LI, Guoqing LIU. Scientific collaboration potential prediction based on dynamic heterogeneous information fusion [J]. Journal of Computer Applications, 2023, 43(9): 2775-2783.
[4]	ZHENG Liping, WANG Jianqiang, ZHANG Yuzhao, DONG Zuofan. Vehicle number optimization approach of autonomous vehicle fleet driven by multi-spatio-temporal distribution task [J]. Journal of Computer Applications, 2021, 41(5): 1406-1411.
[5]	GAO Shile, WANG Ying, LI Hailin, WAN Xiaoji. Prediction method on financial time series data based on matrix profile [J]. Journal of Computer Applications, 2021, 41(1): 199-207.
[6]	JIA Mengyao, WANG Xingwei, ZHANG Shuang, YI Bo, HUANG Min. Software defined network based fault tolerant routing mechanism for satellite networks [J]. Journal of Computer Applications, 2019, 39(6): 1772-1779.
[7]	ZHU Yuelong, ZHU Xiaoxiao, WANG Jimin. Time series motif discovery algorithm based on subsequence full join and maximum clique [J]. Journal of Computer Applications, 2019, 39(2): 414-420.
[8]	WANG Yaqiong, SHI Guozhen, XIE Rongna, LI Fenghua, WANG Yazhe. Multi-authority access control scheme with policy hiding of satellite network [J]. Journal of Computer Applications, 2019, 39(2): 470-475.
[9]	LI Huan, LU Gang, GUO Junxia. Quantitative evaluation for null models of complex networks [J]. Journal of Computer Applications, 2015, 35(6): 1560-1563.
[10]	ZHOU Xing LIU Jun DONG Chundong ZHANG Yujing. Security improvement on LAOR routing protocol [J]. Journal of Computer Applications, 2013, 33(06): 1619-1629.
[11]	PAN Yan-hui WANG Tao WU Yang ZHENG Yan-ru. Group key agreement and rekeying scheme in satellite network based on group key sequence [J]. Journal of Computer Applications, 2012, 32(04): 964-967.
[12]	PAN Yan-hui WANG Tao WU Yang WANG Wen-hao. Trust-based authentication routing protocol for satellite network [J]. Journal of Computer Applications, 2011, 31(03): 781-783.
[13]	. Handover management algorithm for satellite supporting aeronautical users [J]. Journal of Computer Applications, 2009, 29(08): 2194-2197.

Temporal network motif discovery method based on null model

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 26

Related Articles 13

Recommended Articles

Metrics