Toward random walk-based clustering of variable-order networks
- 1 December 2022
- journal article
- research article
- Published by Cambridge University Press (CUP) in Network Science
- Vol. 10 (4) , 381-399
Abstract
Higher-order networks aim at improving the classical network representation of trajectories data as memory-less order 1 Markov models. To do so, locations are associated with different representations or "memory nodes" representing indirect dependencies between visited places as direct relations. One promising area of investigation in this context is variable-order network models as it was suggested by Xu et al. that random walk-based mining tools can be directly applied on such networks. In this paper, we focus on clustering algorithms and show that doing so leads to biases due to the number of nodes representing each location. To address them, we introduce a representation aggregation algorithm that produces smaller yet still accurate network models of the input sequences. We empirically compare the clustering found with multiple network representations of real-world mobility datasets. As our model is limited to a maximum order of 2, we discuss further generalizations of our method to higher orders.Keywords
This publication has 19 references indexed in Scilit:
- When is a Network a Network?2017
- Representing higher-order dependencies in networksScience Advances, 2016
- Memory in network flows and its effects on spreading dynamics and community detectionNature Communications, 2014
- Sparse Markov Chains for Sequence DataScandinavian Journal of Statistics, 2013
- Overlapping community detection in networksACM Computing Surveys, 2013
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Computing Communities in Large Networks Using Random WalksJournal of Graph Algorithms and Applications, 2006
- Higher‐order Markov chain models for categorical data sequences*Naval Research Logistics (NRL), 2004
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Learning probabilistic automata with variable memory length1994