PageRank computation for Higher-Order Networks

Célestin Coquidé (1) , Julie Queiros (1) , François Queyroi (1)

1 LS2N - Laboratoire des Sciences du Numérique de Nantes

Higher-order networks are efficient representations of sequential data. Unlike the classic first-order network approach, they capture indirect dependencies between items composing the input sequences by the use of memory-nodes. We focus in this study on the variable-order network model introduced in [12,10]. Authors suggested that randomwalk-based mining tools can be directly applied to these networks. We discuss the case of the PageRank measure. We show the existence of a bias due to the distribution of the number of representations of the items. We propose an adaptation of the PageRank model in order to correct it. Application on real-world data shows important differences in the achieved rankings.

Mots clés: Higher-order Networks; Sequential data; Random walks; PageRank

Domaines: Informatique [cs]

Célestin Coquidé, Julie Queiros, François Queyroi. PageRank computation for Higher-Order Networks. Complex Networks 2021, Nov 2021, Madrid, Spain. ⟨hal-03369197v1⟩