Search in Power-Law Networks

Abstract

Many communication and social networks have power-law link distributions, containing a few nodes which have a very high degree and many with low degree. The high connectivity nodes play the important role of hubs in communication and networking, a fact which can be exploited when designing efficient search algorithms. We introduce a number of local search strategies which utilize high degree nodes in power-law graphs and which have costs which scale sub-linearly with the size of the graph. We also demonstrate the utility of these strategies on the Gnutella peer-to-peer network.

17 pages, 14 figures

Cited by in corpus (172)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• The spread of epidemic disease on networks
• Evolution of networks
• Mixing patterns in networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Spatial Networks
• Hyperbolic Geometry of Complex Networks
• Identity and Search in Social Networks
• Statistical physics of vaccination
• Scale-Free Networks are Ultrasmall
• Cascade control and defense in complex networks
• Large-scale topological and dynamical properties of Internet
• Random walks and diffusion on networks
• Optimal network topologies for local search with congestion
• Layered Complex Networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity
• Resilience to damage of graphs with degree correlations
• Truncation of power law behavior in "scale-free" network models due to information filtering
• The network topology of a potential energy landscape: A static scale-free network
• Random walks and search in time-varying networks
• Dynamical properties of model communication networks
• Biased random walks on complex networks: the role of local navigation rules
• Path finding strategies in scale-free networks
• Exploring complex networks by walking on them
• Scale-free network growth by ranking
• A spectrum of routing strategies for brain networks
• The Topology of Music Recommendation Networks
• Searchability of Networks
• Characterizing the network topology of the energy landscapes of atomic clusters
• How humans learn and represent networks
• Scale-free networks with an exponent less than two
• Mean-field diffusive dynamics on weighted networks
• Hide and seek on complex networks
• A dynamic model of time-dependent complex networks
• Random walk centrality for temporal networks
• Self-avoiding walks on scale-free networks
• Random walk and trapping processes on scale-free networks
• Information Horizons in Networks
• Asymptotic behavior of the Kleinberg model
• Impact of community structure on information transfer
• Perturbation: the Catastrophe Causer in Scale-Free Networks
• Computational complexity arising from degree correlations in networks
• Search in weighted complex networks
• Distance-d covering problems in scale-free networks with degree correlations
• A Tractable Complex Network Model based on the Stochastic Mean-field Model of Distance
• Extremal Properties of Random Structures
• Equilibrium statistical mechanics of network structures
• Ring structures and mean first passage time in networks
• Information Dynamics in the Networked World
• The shortest path to complex networks
• Steady state and mean recurrence time for random walks on stochastic temporal networks
• Universal fractal scaling of self-organized networks
• Large-scale structural organization of social networks
• Networking - A Statistical Physics Perspective
• The Dynamics of Internet Traffic: Self-Similarity, Self-Organization, and Complex Phenomena
• On Counteracting Byzantine Attacks in Network Coded Peer-to-Peer Networks
• The Competition for Shortest Paths on Sparse Graphs
• Random Multi-Hopper Model. Super-Fast Random Walks on Graphs
• Anti-rumor dynamics and emergence of the timing threshold on complex network
• Search in Complex Networks : a New Method of Naming
• A general centrality framework based on node navigability
• Effects of long-range hopping and interactions on quantum walk in ordered and disordered lattices
• Simulation of the COVID-19 pandemic on the social network of Slovenia: estimating the intrinsic forecast uncertainty
• Walks on weighted networks
• Walks on Apollonian networks
• Navigating Networks with Limited Information
• Navigation in a small world with local information
• Model reproduces individual, group and collective dynamics of human contact networks
• Mixing navigation on networks
• Connectivity strategies to enhance the capacity of weight-bearing networks
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Scalable Percolation Search in Power Law Networks
• Random walks on complex networks under node-dependent stochastic resetting
• Diffusive Capture Process on Complex Networks
• Growing distributed networks with arbitrary degree distributions
• What Do Your Friends Think? Efficient Polling Methods for Networks Using Friendship Paradox
• Topological phase transition in a network model with preferential attachment and node removal
• Analyzing covert social network foundation behind terrorism disaster
• Fast generation of random connected graphs with prescribed degrees
• Spectra of Random Stochastic Matrices and Relaxation in Complex Systems
• Network Discovery by Generalized Random Walks
• A comparative analysis of knowledge acquisition performance in complex networks
• Anomalous biased diffusion in networks
• Optimal random search for a single hidden target
• Cross-domain Network Representations
• Information Gathering in Networks via Active Exploration
• Preferential survival in models of complex ad hoc networks
• Network Growth with Arbitrary Initial Conditions: Analytical Results for Uniform and Preferential Attachment
• Kinetic growth walks on complex networks
• Hypercore Decomposition for Non-Fragile Hyperedges: Concepts, Algorithms, Observations, and Applications
• Random walks on networks: cumulative distribution of cover time
• Diffusive capture processes for information search
• Benefits of Bias: Towards Better Characterization of Network Sampling
• Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence
• Routes Obey Hierarchy in Complex Networks
• Two-dimensional small-world networks: navigation with local information
• Optimal transport on supply-demand networks
• Node discovery problem for a social network
• Partition of Networks into Basins of Attraction
• Smart random walkers: the cost of knowing the path
• Inter-arrival times of message propagation on directed networks
• How to search a social network
• Kinetic-growth self-avoiding walks on small-world networks
• Time walkers and spatial dynamics of ageing information
• Self-avoiding walks and connective constants in clustered scale-free networks
• AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing
• Dynamical and Topological Aspects of Consensus Formation in Complex Networks
• Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time
• On Degree-Based Decentralized Search in Complex Networks
• Online Myopic Network Covering
• An alternative approach to determining average distance in a class of scale-free modular networks
• Efficient Crowd Exploration of Large Networks: The Case of Causal Attribution
• Statistical-mechanical iterative algorithms on complex networks
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• Pathlength scaling in graphs with incomplete navigational information
• Greedy Connectivity of Geographically Embedded Graphs
• Intermittent exploration on a scale-free network
• A novel approach to study realistic navigations on networks
• StratLearner: Learning a Strategy for Misinformation Prevention in Social Networks
• Organic Design of Massively Distributed Systems: A Complex Networks Perspective
• Dependence of the average to-node distance on the node degree for random graphs and growing networks
• The Atlas for the Aspiring Network Scientist
• Temporal-varying failures of nodes in networks
• Topology-dependent density optima for efficient simultaneous network exploration
• Networks and Our Limited Information Horizon
• Distributed Random Walks
• Bayesian model selection for the latent position cluster model for Social Networks
• Star sampling with and without replacement
• Rare events statistics of random walks on networks: localization and other dynamical phase transitions
• Analytically solvable processes on networks
• Near-Optimal Random Walk Sampling in Distributed Networks
• Funnelling effect in networks
• Node discovery in a networked organization
• Study Of The Fundamental Physical Principles in Atmospheric Modeling Based On Identification Of Atmosphere - Climate Control Factors: Bromine Explosion At The Polar Arctic Sunrise
• Can Spatiality Promote Diversity?
• Query Answering via Decentralized Search
• A survey on modelling of infectious disease spread and control on social contact networks
• Little Ball of Fur: A Python Library for Graph Sampling
• Efficient network navigation with partial information
• Towards Limited Scale-free Topology with Dynamic Peer Participation
• Maximizing Entropy Yields Spatial Scaling in Social Networks
• Degree and connectivity of the Internet's scale-free topology
• Efficiency of navigation in indexed networks
• Expansion and Search in Networks
• Realistic searches on stretched exponential networks
• The Scaling laws of Spatial Structure in Social Networks
• The Multiple Instances of Node Centrality and their Implications on the Vulnerability of ISP Networks
• The Architecture of a Novel Weighted Network: Knowledge Network
• Searchability of central nodes in networks
• A Tight Lower Bound on Distributed Random Walk Computation
• Expected Message Delivery Time for Small-world Networks in the Continuum Limit
• Leveraging Peer Centrality in the Design of Socially-Informed Peer-to-Peer Systems
• On The Critical Packet Injection Rate Of A Preferential Next-Nearest Neighbor Routing Traffic Model On Barabasi-Albert Networks
• Ontological differentiation as a measure of semantic accuracy
• Orientation in Social Networks
• Universal scaling hypothesis of quantum spatial search in complex networks
• Resource location based on precomputed partial random walks in dynamic networks
• Efficient Computation of Distance Sketches in Distributed Networks
• Learning Large-scale Network Embedding from Representative Subgraph
• Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks
• Random Walks on Complex Networks
• On the Estimation and Use of Statistical Modelling in Information Retrieval
• Diffusion on dynamic contact networks with indirect transmission links
• Sampling a Network to Find Nodes of Interest
• Navigating the Small World Web by Textual Cues
• Performance of Random Walks in One-Hop Replication Networks
• Assessing the Value of Peer-Produced Information for Exploratory Search
• Graph search via star sampling with and without replacement
• Predicting relevant empty spots in social interaction