On the searchability of small-world networks with arbitrary underlying structure

DOI10.1145/1806689.1806744MaRDI QIDQ2875166zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, George Giakkoupis

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1806689.1806744

zbMATH Keywords

social networkssmall worldsdecentralized search

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Recommendations

• The small-world phenomenon: an algorithmic perspective
• Analyzing Kleinberg's (and other) small-world models
• Optimal path search in small worlds, dimension matters
• Automata, Languages and Programming
• Close to optimal decentralized routing in long-range contact networks

Cited in

(19)

• Delay of social search on small-world graphs
• The Routing of Complex Contagion in Kleinberg’s Small-World Networks
• Distance-based index structures for fast similarity search
• Decentralized search on spheres using small-world Markov chains: expected hitting times and structural properties
• Depth of Field and Cautious-Greedy Routing in Social Networks
• Optimal path search in small worlds, dimension matters
• Deterministic Decentralized Search in Random Graphs
• Trading bit, message, and time complexity of distributed algorithms
• Low-distortion inference of latent similarities from a multiplex social network
• Complex networks and decentralized search algorithms
• Content search through comparisons
• Search in social networks using MCMC algorithm
• Orientation in social networks
• Kleinberg's grid unchained
• Greedy routing and the algorithmic small-world phenomenon
• Asymptotically optimal solutions for small world graphs
• The small-world phenomenon: an algorithmic perspective
• Greedy routing in small-world networks with power-law degrees
• Searching efficiency on complex networks under visual range of nodes

This page was built for publication: On the searchability of small-world networks with arbitrary underlying structure

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