Search in Power-Law Networks

By Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, Bernardo A. Huberman. Physical review. E, Statistical, nonlinear, and soft matter physics, 2001

1,267 citations recorded by the source corpus.

Many communication and social networks have power-law link distributions, containing a few nodes that 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 that can be exploited when designing efficient search algorithms. We introduce a number of local search strategies that utilize high degree nodes in power-law graphs and that have costs scaling sublinearly with the size of the graph. We also demonstrate the utility of these strategies on the GNUTELLA peer-to-peer network.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/731b0db115338ec0c4d89a785320a7e1b4a60f24

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Geographic routing in social networks (2005, background): “” As part of the recent surge of interest in networks, there has been active research exploring strategies for navigating synthetic and small-scale social networks [1–3, 18–21, 35], including routing via common membership in groups, popularity, and geographic proximity, the property upon which we fo”
A local search mechanism for peer-to-peer networks (2002, background): “In a different approach, local search strategies that take advantage of the structure of power-law networks can be employed [1].”
Routing indices for peer-to-peer systems (2002, background): “Figure 9. Simulation Parameters consider three kinds of network topologies: a tree, a tree with added cycles, and a power-law graph [ 15 ].”
Survey of research towards robust peer-to-peer networks: Search methods (2006, background): “Adamic et al. suggested that the random walk searches be directed to nodes with higher degree, that is, with larger numbers of inter-peer connections [249].”
Random walks and diffusion on networks (2016, background): “hly heterogeneous in node degree [44]. If a node that is making or passing on a query knows the degrees of its neighbors, one can enhance search eciency by sending the query to high-degree neighbors [276]. The main limitation of such an approach is that most queries are forwarded to hubs, potentiall”
Peer-to-peer architecture case study: Gnutella network (2001, background): “A number of other research projects build o n DSS’s data: [2] analyzes Gnutella user behavior whi le [6] focuses on efficient search protocols in power-law networks.”
Small-World Phenomena and the Dynamics of Information (2001, background): “Small-World Phenomena and the Dynamics of Information Jon Kleinberg Department of Computer Science Cornell University Ithaca NY 14853”
Spatial Networks (2010, methodology): “This algorithm is already very efficient for non-spatial network [2].”
Zipf's law and the Internet (2002, background): “Recent research has shown, however, that routing queries to the high degree nodes may provide a degree of congestion relief, while maintaining a short response time (Adamic 2001).”
Patterns and dynamics of users' behavior and interaction: Network analysis of an online community (2009, background): “Hubs have an inﬂuence and information-spreading capacity that is disproportionate to their number, and can easily retrieve a large amount of information by leveraging on the abundance of their communication partners (Adamic, Lukose, Puniyani, & Huberman, 2001).”
Layered complex networks. (2005, background): “The topologies of the Internet at the IP layer [1], of the World Wide Web [2] or the networks formed by Peer To Peer (P2P) applications [3] have recently drawn a lot of attention.”