Dynamic Continuous Time Network Representation Learning

doi:10.3778/j.issn.1002-8331.2012-0285

Abstract

Abstract: The network would continue to evolve with changes in nodes and connections over the time. Aiming at the problem that traditional network representation learning algorithms cannot handle dynamic networks correctly, a dynamic continuous-time network representation learning algorithm based on random walks（DCTNE） is proposed. By defining a flexible node timing neighbor concept, a biased random walk process is designed. According to the time information, it can effectively explore the neighbors of different time series of nodes and model the influence of different neighbors, and learn the network representation. The experiment proves the effectiveness of DCTNE dynamic network timing information. On the link prediction task, the AUC value of DCTNE is up to 50% gain compared with other algorithms. On the node classification task, DCTNE also has significantly improved the performance. The results show that modeling the time dependence in the network is helpful for subsequent network analysis tasks.

Key words: network representation learning, random walk, temporal neighbor, continuous time, dynamic network, network evolution

摘要： 随着时间的推移，网络会随着节点和连边的变化不断发展。针对传统网络表示学习算法不能正确处理动态网络的问题，提出一种基于随机游走的动态连续时间网络表示学习算法（DCTNE）。通过定义一个灵活的节点时序邻居概念，设计一个有偏的随机游走过程。根据时间信息，有效地探索节点的不同时序邻居并建模不同邻居的影响，学习网络表示。实验证明了DCTNE动态网络时序信息的有效性。在链接预测任务上，DCTNE的AUC值与其他算法相比最高获得了50%的增益；在节点分类任务上，DCTNE相较于其他算法在效果上有明显提升。结果表明，对网络中时间依赖关系进行建模有助于后续的网络分析任务。

关键词: 网络表示学习, 随机游走, 时序邻居, 连续时间, 动态网络, 网络演化

WANG Yan, REN Hao, WANG Zhe. Dynamic Continuous Time Network Representation Learning[J]. Computer Engineering and Applications, 2022, 58(12): 163-169.

王岩, 任浩, 王喆. 动态连续时间网络表示学习[J]. 计算机工程与应用, 2022, 58(12): 163-169.

References

[1] ALBERT R，JEONG H，ALBERT-LáSZLó B.Internet：diameter of the World-Wide Web[J].Nature，1999，401（6）：130-131.
[2] BRODER A，KUMAR R，RAGHAVAN P，et al.Graph structure in the Web[J].Computer Networks，2000，33（1）：309-320.
[3] FALOUTSOS M，FALOUTSOS P，FALOUTSOS C.On power-law relationships of the Internet topology[J].Poceedings of ACM Sigcomm，1999，29（4）：251-262.
[4] McGovern A，Friedland L，Hay M，et al.Exploiting relational structure to understand publication patterns in high-energy physics[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Washington，Aug 24-Aug 27，2003.New York：ACM，2003：165-172.
[5] NEWMAN M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences，2001，98（2）：404-409.
[6] KLECZKOWSKI A，GRENFELL B T.Mean-field-type equations for spread of epidemics：the “small world” model[J].Physica A：Statistical Mechanics and Its Applications，1999，274（1/2）：355-360.
[7] MAY R M，LLOYD A L.Infection dynamics on scale-free networks[J].Physical Review E，2002，64（6 Pt 2）：066112.
[8] MOORE C，NEWMAN M E J.Epidemics and percolation in small-world networks[J].Physical Review E Statistical Physics Plasmas Fluids & Related Interdisciplinary Topics，2000，61（5 Pt B）：5678-5682.
[9] PASTOR-SATORRAS R，VESPIGNANI A.Epidemic spreading in scale-free networks[J].Physical Review Letters，2001，86（14）：3200-3203.
[10] ROSSI R，NEVILLE J.Modeling the evolution of discussion topics and communication to improve relational classification[C]//Proceedings of the 1st Workshop on Social Media Analytics，Washington，Jul 25，2010.New York：ACM，2010：89-97.
[11] 涂存超，杨成，刘知远，等.网络表示学习综述[J].中国科学：信息科学，2017，47（8）：980-996.
TU C C，YANG C，LIU Z Y，at al.Network representation learning：an overview[J].Scientia Sinica：Informations，2017，47（8）：980-996.
[12] BATTISTA G D，EADES P，TAMASSIA R，et al.Algorithms for drawing graphs：an annotated bibliography[J].Computational Geometry Theory & Applications，1994，4（5）：235-282.
[13] FRUCHTERMAN T M J，REINGOLD E M.Graph drawing by force directed placement[J].Software Practice & Experience，2010，21（11）：1129-1164.
[14] KAMADA T，KAWAI S.An algorithm for drawing general undirected graphs[J].Information Processing Letters，1989，31（1）：7-15.
[15] PEROZZI B，AL-RFOU R，SKIENA S.Deepwalk：online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，New York，Aug 24-Aug 27，2014.New York：ACM，2014：701-710.
[16] TANG J，QU M，WANG M Z，et al.LINE：large-scale information network embedding[J].arXiv：1503.03578，2015.
[17] GROVER A，LESKOVEC J.node2vec：scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，San Francisco，Aug 13-Aug 17，2016.New York：ACM，2016：855-864.
[18] CHAKRABARTI D，KUMAR R，TOMKINS A.Evolutionary clustering[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Philadelphia，Aug 20-Aug 23，2006.New York：ACM，2006：554-560.
[19] CHI Y，SONG X，ZHOU D，et al.On evolutionary spectral clustering[J].ACM Transactions on Knowledge Discovery from Data，2009，3（4）：17.
[20] KIM M S，HAN J.A particle-and-density based evolutionary clustering method for dynamic networks[J].Proceedings of the VLDB Endowment，2009，2（1）：622-633.
[21] GUPTA M，AGGARWAL C C，HAN J，et al.Evolutionary clustering and analysis of bibliographic networks[C]//International Conference on Advances in Social Networks Analysis and Mining，Jul 25-Jul 27，2011：63-70.
[22] YAO L，WANG L，PAN L，et al.Link prediction based on common-neighbors for dynamic social network[J].Procedia Computer Science，2016，83：82-89.
[23] ZHU L，GUO D，YIN J，et al.Scalable temporal latent space inference for link prediction in dynamic social networks[J].IEEE Transactions on Knowledge & Data Engineering，2016，28（10）：2765-2777.
[24] MIKOLOV T，SUTSKEVER I，CHEN K，et al.Distributed representations of words and phrases and their compositionality[J].Advances in Neural Information Processing Systems，2013，10（26）：3111-3119.
[25] MIKOLOV T，SUTSKEVER I，CHEN K，et al.Distributed representations of words and phrases and their compositionality[C]//Proceedings of the 26th International Conference on Neural Information Processing Systems.North Miami Beach，FL：Curran Associates，Dec 5 2013：3111-3119.