{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T05:07:34Z","timestamp":1781672854909,"version":"3.54.5"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T00:00:00Z","timestamp":1584489600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T00:00:00Z","timestamp":1584489600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2017- 05680"],"award-info":[{"award-number":["2017- 05680"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Large-scale network mining and analysis is key to revealing the underlying dynamics of networks, not easily observable before. Lately, there is a fast-growing interest in learning low-dimensional continuous representations of networks that can be utilized to perform highly accurate and scalable graph mining tasks. A family of these methods is based on performing random walks on a network to learn its structural features and providing the sequence of random walks as input to a deep learning architecture to learn a network embedding. While these methods perform well, they can only operate on static networks. However, in real-world, networks are evolving, as nodes and edges are continuously added or deleted. As a result, any previously obtained network representation will now be outdated having an adverse effect on the accuracy of the network mining task at stake. The naive approach to address this problem is to re-apply the embedding method of choice every time there is an update to the network. But this approach has serious drawbacks. First, it is inefficient, because the embedding method itself is computationally expensive. Then, the network mining task outcome obtained by the subsequent network representations are not directly comparable to each other, due to the randomness involved in the new set of random walks involved each time. In this paper, we propose <jats:sc>EvoNRL<\/jats:sc>, a random-walk based method for learning representations of evolving networks. The key idea of our approach is to first obtain a set of random walks on the current state of network. Then, while changes occur in the evolving network\u2019s topology, to dynamically update the random walks in reserve, so they do not introduce any bias. That way we are in position of utilizing the updated set of random walks to continuously learn accurate mappings from the evolving network to a low-dimension network representation. Moreover, we present an analytical method for determining the right time to obtain a new representation of the evolving network that balances accuracy and time performance. A thorough experimental evaluation is performed that demonstrates the effectiveness of our method against sensible baselines and varying conditions.<\/jats:p>","DOI":"10.1007\/s41109-020-00257-3","type":"journal-article","created":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T14:13:10Z","timestamp":1584540790000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Evolving network representation learning based on random walks"],"prefix":"10.1007","volume":"5","author":[{"given":"Farzaneh","family":"Heidari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manos","family":"Papagelis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,3,18]]},"reference":[{"key":"257_CR1","unstructured":"Computer science bibliography."},{"key":"257_CR2","doi-asserted-by":"publisher","unstructured":"Ahmed, A, Shervashidze N, Narayanamurthy S, Josifovski V, Smola AJ (2013) Distributed large-scale natural graph factorization In: Proceedings of the 22nd international conference on World Wide Web - WWW \u201913.. ACM Press. https:\/\/doi.org\/10.1145\/2488388.2488393.","DOI":"10.1145\/2488388.2488393"},{"key":"257_CR3","unstructured":"Ahmed, NK, Rossi R, Lee JB, Kong X, Willke TL, Zhou R, Eldardiry H (2018) Learning role-based graph embeddings. arXiv preprint arXiv:1802.02896."},{"key":"257_CR4","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1162\/tacl_a_00008","volume":"6","author":"M Antoniak","year":"2018","unstructured":"Antoniak, M, Mimno D (2018) Evaluating the stability of embedding-based word similarities. TACL 6:107\u2013119.","journal-title":"TACL"},{"key":"257_CR5","volume-title":"Outliers in statistical data; 3rd ed. Wiley series in probability and mathematical statistics","author":"V Barnett","year":"1974","unstructured":"Barnett, V, Lewis T (1974) Outliers in statistical data; 3rd ed. Wiley series in probability and mathematical statistics. Wiley, Chichester."},{"issue":"8","key":"257_CR6","doi-asserted-by":"publisher","first-page":"1798","DOI":"10.1109\/TPAMI.2013.50","volume":"35","author":"Y Bengio","year":"2013","unstructured":"Bengio, Y, Courville A, Vincent P (2013) Representation learning: A review and new perspectives. IEEE TPAMI 35(8):1798\u20131828.","journal-title":"IEEE TPAMI"},{"issue":"suppl_1","key":"257_CR7","doi-asserted-by":"publisher","first-page":"D637","DOI":"10.1093\/nar\/gkm1001","volume":"36","author":"B-J Breitkreutz","year":"2007","unstructured":"Breitkreutz, B-J, Stark C, Reguly T, Boucher L, Breitkreutz A, Livstone M, Oughtred R, Lackner DH, B\u00e4hler J, Wood V, et al. (2007) The biogrid interaction database: 2008 update. Nucleic Acids Res 36(suppl_1):D637\u2013D640.","journal-title":"Nucleic Acids Res"},{"issue":"9","key":"257_CR8","doi-asserted-by":"publisher","first-page":"1616","DOI":"10.1109\/tkde.2018.2807452","volume":"30","author":"H Cai","year":"2018","unstructured":"Cai, H, Zheng VW, Chang K (2018) A comprehensive survey of graph embedding: Problems, techniques and applications. IEEE TKDE 30(9):1616\u20131637. https:\/\/doi.org\/10.1109\/tkde.2018.2807452.","journal-title":"IEEE TKDE"},{"key":"257_CR9","first-page":"891","volume-title":"Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, CIKM \u201915","author":"S Cao","year":"2015","unstructured":"Cao, S, Lu W, Xu Q (2015) Grarep: Learning graph representations with global structural information In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, CIKM \u201915, 891\u2013900.. ACM, New York."},{"key":"257_CR10","unstructured":"Chamberlain, BP, Clough J, Deisenroth MP (2017) Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359."},{"key":"257_CR11","unstructured":"Chen, H, Perozzi B, Hu Y, Skiena S (2017) Harp: Hierarchical representation learning for networks. arXiv preprint arXiv:1706.07845."},{"key":"257_CR12","doi-asserted-by":"publisher","unstructured":"Craswell, N, Szummer M (2007) Random walks on the click graph In: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR \u201907.. ACM Press. https:\/\/doi.org\/10.1145\/1277741.1277784.","DOI":"10.1145\/1277741.1277784"},{"key":"257_CR13","doi-asserted-by":"publisher","unstructured":"Du, L, Wang Y, Song G, Lu Z, Wang J (2018) Dynamic network embedding: an extended approach for skip-gram based network embedding In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence.. International Joint Conferences on Artificial Intelligence Organization. https:\/\/doi.org\/10.24963\/ijcai.2018\/288.","DOI":"10.24963\/ijcai.2018\/288"},{"key":"257_CR14","unstructured":"Goyal, P, Kamra N, He X, Liu Y2018. Dyngem: Deep embedding method for dynamic graphs."},{"key":"257_CR15","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1145\/2939672.2939754","volume-title":"Proceedings of the 22nd ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining, KDD \u201916","author":"A Grover","year":"2016","unstructured":"Grover, A, Leskovec J (2016) node2vec: Scalable feature learning for networks In: Proceedings of the 22nd ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining, KDD \u201916, 855\u2013864.. Association for Computing Machinery, New York."},{"key":"257_CR16","doi-asserted-by":"publisher","first-page":"1489","DOI":"10.18653\/v1\/P16-1141","volume-title":"Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)","author":"WL Hamilton","year":"2016","unstructured":"Hamilton, WL, Leskovec J, Jurafsky D (2016) Diachronic word embeddings reveal statistical laws of semantic change In: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 1489\u20131501.. Association for Computational Linguistics, Berlin."},{"key":"257_CR17","unstructured":"Hamilton, WL, Ying R, Leskovec J (2017) Representation learning on graphs: Methods and applications. IEEE Data Eng Bull."},{"key":"257_CR18","doi-asserted-by":"publisher","unstructured":"Heidari, F, Papagelis M (2018) Evonrl: Evolving network representation learning based on random walks In: Proceedings of the 7th International Conference on Complex Networks and Their Applications, 457\u2013469.. Springer International Publishing. https:\/\/doi.org\/10.1007\/978-3-030-05411-3_37.","DOI":"10.1007\/978-3-030-05411-3_37"},{"key":"257_CR19","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-1-4612-4380-9_14","volume-title":"Breakthroughs in statistics","author":"H Hotelling","year":"1992","unstructured":"Hotelling, H (1992) Relations between two sets of variates In: Breakthroughs in statistics, 162\u2013190.. Springer, New York."},{"issue":"9","key":"257_CR20","doi-asserted-by":"publisher","first-page":"937","DOI":"10.14778\/3099622.3099625","volume":"10","author":"M Jiang","year":"2017","unstructured":"Jiang, M, Fu AW-C, Wong RC-W (2017) Reads: A random walk approach for efficient and accurate dynamic simrank. Proc VLDB Endow 10(9):937\u2013948.","journal-title":"Proc VLDB Endow"},{"key":"257_CR21","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01016796","volume":"9","author":"VM Kenkre","year":"1973","unstructured":"Kenkre, VM, Montroll EW, Shlesinger MF (1973) Generalized master equations for continuous-time random walks. J Stat Phys 9:45\u201350.","journal-title":"J Stat Phys"},{"key":"257_CR22","doi-asserted-by":"publisher","unstructured":"Kim, Y, Chiu Y, Hanaki K, Hegde D, Petrov S (2014) Temporal analysis of language through neural language models In: Proceedings of the ACL 2014 Workshop on Language Technologies and Computational Social Science.. Association for Computational Linguistics. https:\/\/doi.org\/10.3115\/v1\/w14-2517.","DOI":"10.3115\/v1\/w14-2517"},{"key":"257_CR23","unstructured":"Kornblith, S, Norouzi M, Lee H, Hinton G (2019) Similarity of neural network representations revisited. In: Chaudhuri K Salakhutdinov R (eds)Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, 3519\u20133529, Long Beach."},{"key":"257_CR24","unstructured":"Leskovec, J, Krevl A (2014) SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data. Accessed 1 June 2019."},{"key":"257_CR25","doi-asserted-by":"publisher","unstructured":"Li, J, Dani H, Hu X, Tang J, Chang Y, Liu H2017. Attributed network embedding for learning in a dynamic environment. ACM Press. https:\/\/doi.org\/10.1145\/3132847.3132919.","DOI":"10.1145\/3132847.3132919"},{"issue":"1-46","key":"257_CR26","first-page":"4","volume":"2","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L (1993) Random walks on graphs. Comb Paul erdos is eighty 2(1-46):4.","journal-title":"Comb Paul erdos is eighty"},{"key":"257_CR27","unstructured":"Mikolov, T, Chen K, Corrado G, Dean J (2013a) Efficient estimation of word representations in vector space. In: Bengio Y LeCun Y (eds)1st International Conference on Learning Representations, ICLR 2013.. Workshop Track Proceedings, Scottsdale."},{"key":"257_CR28","unstructured":"Mikolov, T, Sutskever I, Chen K, Corrado GS, Dean J (2013b) Distributed representations of words and phrases and their compositionality In: Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2, NIPS\u201913, 3111\u20133119.. Curran Associates Inc., Red Hook."},{"key":"257_CR29","first-page":"5727","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS\u201918","author":"A Morcos","year":"2018","unstructured":"Morcos, A, Raghu M, Bengio S (2018) Insights on representational similarity in neural networks with canonical correlation In: Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS\u201918, 5727\u20135736.. Curran Associates Inc., Red Hook."},{"issue":"2","key":"257_CR30","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"ME Newman","year":"2003","unstructured":"Newman, ME (2003) The structure and function of complex networks. SIAM Rev 45(2):167\u2013256.","journal-title":"SIAM Rev"},{"key":"257_CR31","doi-asserted-by":"publisher","unstructured":"Nguyen, GH, Lee JB, Rossi RA, Ahmed NK, Koh E, Kim S (2018) Continuous-time dynamic network embeddings In: Companion of the The Web Conference 2018 on The Web Conference 2018 - WWW \u201918.. ACM Press. https:\/\/doi.org\/10.1145\/3184558.3191526.","DOI":"10.1145\/3184558.3191526"},{"key":"257_CR32","doi-asserted-by":"publisher","unstructured":"Ou, M, Cui P, Pei J, Zhang Z, Zhu W (2016) Asymmetric transitivity preserving graph embedding In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD \u201916, 1105\u20131114.. ACM Press. https:\/\/doi.org\/10.1145\/2939672.2939751.","DOI":"10.1145\/2939672.2939751"},{"key":"257_CR33","unstructured":"Page, L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab."},{"key":"257_CR34","volume-title":"Stochastic Processes: From Physics to Finance","author":"W Paul","year":"2010","unstructured":"Paul, W, Baschnagel J (2010) Stochastic Processes: From Physics to Finance. Springer, Berlin Heidelberg."},{"issue":"1867","key":"257_CR35","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1038\/072342a0","volume":"72","author":"K Pearson","year":"1905","unstructured":"Pearson, K (1905) The problem of the random walk. Nature 72(1867):342.","journal-title":"Nature"},{"key":"257_CR36","doi-asserted-by":"crossref","unstructured":"Perozzi, B, Al-Rfou R, Skiena S2014. Deepwalk: Online learning of social representations. Association for Computing Machinery, New York.","DOI":"10.1145\/2623330.2623732"},{"key":"257_CR37","first-page":"258","volume-title":"Proceedings of the 2017 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, ASONAM \u201917","author":"B Perozzi","year":"2016","unstructured":"Perozzi, B, Kulkarni V, Chen H, Skiena S (2016) Don\u2019t walk, skip! online learning of multi-scale network embeddings In: Proceedings of the 2017 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, ASONAM \u201917, 258\u2013265.. Association for Computing Machinery, New York."},{"key":"257_CR38","first-page":"6076","volume-title":"Advances in Neural Information Processing Systems 30","author":"M Raghu","year":"2017","unstructured":"Raghu, M, Gilmer J, Yosinski J, Sohl-Dickstein J (2017) Svcca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. In: Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R (eds)Advances in Neural Information Processing Systems 30, 6076\u20136085.. Curran Associates, Inc., Red Hook."},{"issue":"3","key":"257_CR39","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/BF02306029","volume":"49","author":"J J. Ramsay","year":"1984","unstructured":"J. Ramsay, J, Berge Jt, Styan G (1984) Matrix correlation. Psychometrika 49(3):403\u2013423.","journal-title":"Psychometrika"},{"key":"257_CR40","unstructured":"Reza, Z, Huan LSocial computing data repository."},{"key":"257_CR41","doi-asserted-by":"publisher","unstructured":"Rudolph, M, Blei D (2018) Dynamic embeddings for language evolution In: Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW \u201918.. ACM Press. https:\/\/doi.org\/10.1145\/3178876.3185999.","DOI":"10.1145\/3178876.3185999"},{"key":"257_CR42","doi-asserted-by":"crossref","unstructured":"Tang, J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015) LINE: large-scale information network embedding In: Proceedings of the 24th International Conference on World Wide Web, WWW \u201915, 1067\u20131077. Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee.","DOI":"10.1145\/2736277.2741093"},{"key":"257_CR43","first-page":"3462","volume":"70","author":"R Trivedi","year":"2017","unstructured":"Trivedi, R, Dai H, Wang Y, Song L (2017) Know-evolve: Deep temporal reasoning for dynamic knowledge graphs. ICML 70:3462\u20133471.","journal-title":"ICML"},{"key":"257_CR44","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1145\/2939672.2939753","volume-title":"Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201916","author":"D Wang","year":"2016","unstructured":"Wang, D, Cui P, Zhu W (2016) Structural deep network embedding In: Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201916, 1225\u20131234.. ACM, New York."},{"key":"257_CR45","unstructured":"Yang, C, Liu Z, Zhao D, Sun M, Chang EY (2015) Network representation learning with rich text information In: Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI\u201915, 2111\u20132117.. AAAI Press."},{"issue":"1","key":"257_CR46","first-page":"181","volume":"42","author":"J Yang","year":"2015","unstructured":"Yang, J, Leskovec J (2015) Defining and evaluating network communities based on ground-truth. KAIS 42(1):181\u2013213.","journal-title":"KAIS"},{"key":"257_CR47","doi-asserted-by":"publisher","first-page":"2672","DOI":"10.1145\/3219819.3220024","volume-title":"Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining KDD \u201918","author":"W Yu","year":"2018","unstructured":"Yu, W, Cheng W, Aggarwal CC, Zhang K, Chen H, Wang W (2018) Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining KDD \u201918, 2672\u20132681.. ACM, New York."},{"key":"257_CR48","doi-asserted-by":"publisher","unstructured":"Zhang, D, Yin J, Zhu X, Zhang C (2018) Network representation learning: A survey. IEEE Transac Big Data:1. https:\/\/doi.org\/10.1109\/tbdata.2018.2850013.","DOI":"10.1109\/tbdata.2018.2850013"},{"key":"257_CR49","doi-asserted-by":"publisher","unstructured":"Zuo, Y, Liu G, Lin H, Guo J, Hu X, Wu J (2018) Embedding temporal network via neighborhood formation In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.. ACM. https:\/\/doi.org\/10.1145\/3219819.3220054.","DOI":"10.1145\/3219819.3220054"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-020-00257-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41109-020-00257-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-020-00257-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,18]],"date-time":"2021-03-18T00:11:59Z","timestamp":1616026319000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-020-00257-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,18]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["257"],"URL":"https:\/\/doi.org\/10.1007\/s41109-020-00257-3","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,18]]},"assertion":[{"value":"29 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"18"}}