Ranking and clustering of nodes in networks with smart teleportation

Abstract

Random teleportation is a necessary evil for ranking and clustering directed networks based on random walks. Teleportation enables ergodic solutions, but the solutions must necessarily depend on the exact implementation and parametrization of the teleportation. For example, in the commonly used PageRank algorithm, the teleportation rate must trade off a heavily biased solution with a uniform solution. Here we show that teleportation to links rather than nodes enables a much smoother trade-off and effectively more robust results. We also show that, by not recording the teleportation steps of the random walker, we can further reduce the effect of teleportation with dramatic effects on clustering.

10 pages, 7 figures

References in corpus (6)

• Maps of random walks on complex networks reveal community structure
• Comparing community structure identification
• Finding Scientific Gems with Google
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Who is the best player ever? A complex network analysis of the history of professional tennis
• Flow graphs: interweaving dynamics and structure

Cited by in corpus (34)

• Multilayer Networks
• Random walks and diffusion on networks
• Memory in network flows and its effects on spreading dynamics and community detection
• Ranking in evolving complex networks
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Mapping higher-order network flows in memory and multilayer networks with Infomap
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Estimating the resolution limit of the map equation in community detection
• Interest communities and flow roles in directed networks: the Twitter network of the UK riots
• Mapping flows on hypergraphs
• Revealing cell assemblies at multiple levels of granularity
• Multiscale dynamical embeddings of complex networks
• Using higher-order Markov models to reveal flow-based communities in networks
• Random Walks on Stochastic Temporal Networks
• Hierarchical networks of scientific journals
• Random walks on complex networks under node-dependent stochastic resetting
• Map Equation Centrality: Community-aware Centrality based on the Map Equation
• A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
• Influencers identification in complex networks through reaction-diffusion dynamics
• Classical and quantum random-walk centrality measures in multilayer networks
• Mapping flows on weighted and directed networks with incomplete observations
• Flow Motifs Reveal Limitations of the Static Framework to Represent Human interactions
• Classes of random walks on temporal networks with competing timescales
• Cycle flow based module detection in directed recurrence networks
• Generalized Markov stability of network communities
• Regional economic integration via detection of circular flow in international value-added network
• Move ordering and communities in complex networks describing the game of go
• Community detection in weighted brain connectivity networks beyond the resolution limit
• Can the PageRank centrality be manipulated to obtain any desired ranking?
• Single-trajectory map equation
• Robustness of journal rankings by network flows with different amounts of memory
• Network location and clustering of genetic mutations determine chronicity in a stylized model of genetic diseases
• Flow approaches to community detection in complex network systems