Greedy routing in small-world networks with power-law degrees

DOI10.1007/S00446-014-0210-YMaRDI QIDQ2256946zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, George Giakkoupis

Publication date 23 February 2015

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01097141/file/DIST14_sw.pdf

zbMATH Keywords

power-law degreesroutingsearchsmall worldssocial networks

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network protocols (68M12) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• The effect of power-law degrees on the navigability of small worlds (extended abstract)
• Efficient routeing in Poisson small-world networks
• Tight lower bounds for greedy routing in higher-dimensional small-world grids
• Greedy routing and the algorithmic small-world phenomenon
• Optimal routing in a small-world network

Cites work

• Algorithms – ESA 2005
• Analyzing and characterizing small-world graphs
• Analyzing Kleinberg's (and other) small-world models
• Automata, Languages and Programming
• Collective dynamics of `small-world' networks
• Complex networks and decentralized search algorithms
• Could any graph be turned into a small-world?
• Distance estimation and object location via rings of neighbors
• Distributed Computing
• Eclecticism shrinks even small worlds
• Fault-tolerant routing in peer-to-peer systems
• scientific article; zbMATH DE number 2006658 (Why is no real title available?)
• scientific article; zbMATH DE number 1866312 (Why is no real title available?)
• scientific article; zbMATH DE number 2119680 (Why is no real title available?)
• Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks
• Object location using path separators
• On the complexity of greedy routing in ring-based peer-to-peer networks
• On the searchability of small-world networks with arbitrary underlying structure
• Optimal path search in small worlds, dimension matters
• Statistical mechanics of complex networks
• The Average Distance in a Random Graph with Given Expected Degrees
• The diameter of a scale-free random graph
• The effect of power-law degrees on the navigability of small worlds (extended abstract)
• The small-world phenomenon: an algorithmic perspective
• The Structure and Function of Complex Networks
• Tight bounds for blind search on the integers
• Tight lower bounds for greedy routing in uniform small world rings

Cited in

(7)

• Greedy routing and the algorithmic small-world phenomenon
• Kleinberg's grid unchained
• scientific article; zbMATH DE number 2112462 (Why is no real title available?)
• The effect of power-law degrees on the navigability of small worlds (extended abstract)
• Tight lower bounds for greedy routing in uniform small world rings
• Greedy routing and the algorithmic small-world phenomenon
• Efficient routeing in Poisson small-world networks

This page was built for publication: Greedy routing in small-world networks with power-law degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256946)