Toward random walk-based clustering of variable-order networks

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

Cluster analysis · Context (archaeology · Data mining · Focus (optics · Machine learning · Markov chain · Order (exchange · Random walk · Representation (politics · Spectral clustering · Variable (mathematics · Complex Network Analysis Techniques · Computer Science · Data Management and Algorithms · Human Mobility and Location-Based Analysis · Mathematics · Artificial Intelligence · Theoretical Computer Science

• Benchmark graphs for testing community detection algorithms

  Open Access•Andrea Lancichinetti, Santo Fortunato et al.•Physical Review E•2008

  Add to list

• Computing Communities in Large Networks Using Random Walks

  Open Access•Pascal Pons, Matthieu Latapy•Journal of Graph Algorithms and…•2006

  Add to list

• The anatomy of a large-scale hypertextual Web search engine

  Open Access•Sergey Brin, Lawrence Page et al.•Computer Networks and ISDN Systems•1998

  Add to list