The small-world phenomenon

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The small-world phenomenon: an algorithm perspective

Full text

Pdf (767 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 163 - 170

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Jon Kleinberg

Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 40, Downloads (12 Months): 442, Citation Count: 118

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335325 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Lada A. Adamic, The Small World Web, Proceedings of the Third European Conference on Research and Advanced Technology for Digital Libraries, p.443-452, September 22-24, 1999
	2	R. Albert, H. Jeong, A.-L. Barabasi, "The diameter of the World Wide Web," Nature 401, 130 (1999).
	3	Piotr Berman, On-line Searching and Navigation, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.232-241, January 1998
	4	B. Bollob~s, Random Graphs (Academic Press, London, 1985).
	5	B. Bollobás , F. R. K. Chung, The diameter of a cycle plus a random matching, SIAM Journal on Discrete Mathematics, v.1 n.3, p.328-333, Aug. 1988 [doi>10.1137/0401033]
	6	F.R.K. Chung, M.R. Garey, "Diameter bounds for altered graphs," J. Graph Theory 8, 511 (1984).
	7	J. Guam, Six Degrees o/Separation: A Play (Vintage Books, New York, 1990).
	8	J. Hunter and R. Shotland, "Treating data collected by the small world method as a Markov process," Social Forces 52, 321 (1974).
	9	J. Kaiser, Ed., "It's a small Web after all," Science 285, 1815 (1999).
	10	P. Killworth and H. Bernard, "Reverse small world experiment," Social Networks 1,159 (1978).
	11	M. Kochen, Ed., The Small World (Ablex, Norwood, 1989).
	12	C. Korte and S. Milgram, "Acquaintance networks between racial groups: Application of the small world method," J. Personality and Social Psych., 15, 101 (1978).
	13	S. Milgram, "The small world problem," Psychology Today 1, 61 (1967).
	14	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	15	David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
	16	I. de Sola Pool and M. Kochen, "Contacts and influence,'' Social Networks 1, 5 (1978).
	17	Henry Kautz , Bart Selman , Mehul Shah, Referral Web: combining social networks and collaborative filtering, Communications of the ACM, v.40 n.3, p.63-65, March 1997 [doi>10.1145/245108.245123]
	18	J. Travers and S. Milgram, "An experimental study of the small world problem," Sociometry 32, 425 (1969).
	19	D. Watts and S. Strogatz, "Collective dynamics of small-world networks," Nature 393, 440 (1998).
	20	H. White, "Search parameters for the small world problem," Social Forces 49, 259 (1970).

CITED BY 118

	Ali Ghodsi , Seif Haridi , Hakim Weatherspoon, Exploiting the synergy between gossiping and structured overlays, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
	Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Mayank Bawa , Gurmeet Singh Manku , Prabhakar Raghavan, SETS: search enhanced by topic segmentation, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
	Mayank Bawa , Brian F. Cooper , Arturo Crespo , Neil Daswani , Prasanna Ganesan , Hector Garcia-Molina , Sepandar Kamvar , Sergio Marti , Mario Schlosser , Qi Sun , Patrick Vinograd , Beverly Yang, Peer-to-peer research at Stanford, ACM SIGMOD Record, v.32 n.3, September 2003
	Bin Yu , Munindar P. Singh, Searching social networks, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
	K. Gummadi , R. Gummadi , S. Gribble , S. Ratnasamy , S. Shenker , I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
	Hans Friedrich Witschel , Thomas Böhme, Evaluating profiling and query expansion methods for P2P information retrieval, Proceedings of the 2005 ACM workshop on Information retrieval in peer-to-peer networks, November 04-04, 2005, Bremen, Germany
	Keren Horowitz , Dahlia Malkhi, Estimating network size from local information, Information Processing Letters, v.88 n.5, p.237-243, 16 December 2003
	References, Grid resource management: state of the art and future trends, Kluwer Academic Publishers, Norwell, MA, 2004
	Gurmeet Singh Manku, Routing networks for distributed hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.133-142, July 13-16, 2003, Boston, Massachusetts
	Gurmeet Singh Manku, Balanced binary trees for ID management and load balance in distributed hash tables, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	David D. Clark , Craig Partridge , J. Christopher Ramming , John T. Wroclawski, A knowledge plane for the internet, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
	Chip Martel , Van Nguyen, Analyzing Kleinberg's (and other) small-world Models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Hai Zhuge, Retrieve images by understanding semantic links and clustering image fragments, Journal of Systems and Software, v.73 n.3, p.455-466, November-December 2004
	Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Pierre Fraigniaud , Cyril Gavoille , Christophe Paul, Eclecticism shrinks even small worlds, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
	Shudong Jin, Replication of partitioned media streams in wireless ad hoc networks, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
	S. Muthukrishnan , Gopal Pandurangan, The bin-covering technique for thresholding random geometric graph properties, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Farnoush Banaei-Kashani , Cyrus Shahabi, SWAM: a family of access methods for similarity-search in peer-to-peer data networks, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Ittai Abraham , Dahlia Malkhi, Compact routing on euclidian metrics, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Saverio Perugini , Marcos André Gonçalves , Edward A. Fox, Recommender Systems Research: A Connection-Centric Survey, Journal of Intelligent Information Systems, v.23 n.2, p.107-143, September 2004
	Shashidhar Merugu , Sridhar Srinivasan , Ellen Zegura, Adding structure to unstructured peer-to-peer networks: the use of small-world graphs, Journal of Parallel and Distributed Computing, v.65 n.2, p.142-153, February 2005
	Gaurav Sharma , Ravi Mazumdar, Hybrid sensor networks: a small world, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
	Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Van Nguyen , Chip Martel, Analyzing and characterizing small-world graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Omer Angel , Itai Benjamini , Eran Ofek , Udi Wieder, Routing complexity of faulty networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Debora Donato , Luigi Laura , Stefano Leonardi , Stefano Millozzi, Simulating the Webgraph: A Comparative Analysis of Models, Computing in Science and Engineering, v.6 n.6, p.84-89, November 2004
	Gennaro Cordasco , Luisa Gargano , Mikael Hammar , Vittorio Scarano, Brief announcement: degree: optimal deterministic routing for P2P systems, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Shengquan Wang , Dong Xuan , Wei Zhao, Analyzing and enhancing the resilience of structured peer-to-peer systems, Journal of Parallel and Distributed Computing, v.65 n.2, p.207-219, February 2005
	András Faragó, On the typical case complexity of graph optimization, Discrete Applied Mathematics, v.153 n.1, p.73-88, 1 December 2005
	Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Ivona Bezáková , Adam Kalai , Rahul Santhanam, Graph model selection using maximum likelihood, Proceedings of the 23rd international conference on Machine learning, p.105-112, June 25-29, 2006, Pittsburgh, Pennsylvania
	Emmanuelle Lebhar , Nicolas Schabanel, Close to optimal decentralized routing in long-range contact networks, Theoretical Computer Science, v.348 n.2, p.294-310, 8 December 2005
	Fred S. Annexstein , Kenneth A. Berman , Mijhalo A. Jovanović, Broadcasting in unstructured peer-to-peer overlay networks, Theoretical Computer Science, v.355 n.1, p.25-36, 6 April 2006
	Pierre Fraigniaud , Philippe Gauron, D2B: a de Bruijn based content-addressable network, Theoretical Computer Science, v.355 n.1, p.65-79, 6 April 2006
	Philippe Duchon , Nicolas Hanusse , Emmanuelle Lebhar , Nicolas Schabanel, Could any graph be turned into a small-world?, Theoretical Computer Science, v.355 n.1, p.96-103, 6 April 2006
	Enoch Peserico , Larry Rudolph, Robust network connectivity: when it's the big picture that matters, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
	Shudong Jin , Azer Bestavros, Small-world characteristics of internet topologies and implications on multicast scaling, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.5, p.648-666, 6 April 2006
	Stephen Boyd , Arpita Ghosh , Balaji Prabhakar , Devavrat Shah, Randomized gossip algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2508-2530, June 2006
	Pierre Fraigniaud , Cyril Gavoille , Christophe Paul, Eclecticism shrinks even small worlds, Distributed Computing, v.18 n.4, p.279-291, March 2006
	Bernard Wong , Ymir Vigfússon , Emin Gün Sirer, Hyperspaces for object clustering and approximate matching in peer-to-peer overlays, Proceedings of the 11th USENIX workshop on Hot topics in operating systems, p.1-6, May 07-09, 2007, San Diego, CA
	Alan Mislove , Massimiliano Marcon , Krishna P. Gummadi , Peter Druschel , Bobby Bhattacharjee, Measurement and analysis of online social networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA
	Hai Jin , Xiaomin Ning , Hanhua Chen, Efficient search for peer-to-peer information retrieval using semantic small world, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland
	Philippe Duchon , Nicolas Hanusse , Emmanuelle Lebhar , Nicolas Schabanel, Towards small world emergence, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Cyril Gavoille , Martin Nehéz, Interval routing in reliability networks, Theoretical Computer Science, v.333 n.3, p.415-432, 3 March 2005
	Matthew J. Rattigan , Marc Maier , David Jensen, Using structure indices for efficient approximation of network properties, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Jon Kleinberg, Distributed social systems, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, p.5-6, July 23-26, 2006, Denver, Colorado, USA
	Ming Zhong , Kai Shen, Random walk based node sampling in self-organizing networks, ACM SIGOPS Operating Systems Review, v.40 n.3, July 2006
	Ittai Abraham , Cyril Gavoille, Object location using path separators, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Jon Kleinberg, Social networks, incentives, and search, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, p.210-211, August 06-11, 2006, Seattle, Washington, USA
	Toan Luu , Fabius Klemm , Ivana Podnar , Martin Rajman , Karl Aberer, ALVIS peers: a scalable full-text peer-to-peer retrieval engine, Proceedings of the international workshop on Information retrieval in peer-to-peer networks, November 11-11, 2006, Arlington, Virginia, USA
	Ittai Abraham , Yair Bartal , Ofer Neiman, Local embeddings of metric spaces, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Jinyang Li , Jeremy Stribling , Robert Morris , M. Frans Kaashoek, Bandwidth-efficient management of DHT routing tables, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.99-114, May 02-04, 2005
	Gurmeet Singh Manku , Mayank Bawa , Prabhakar Raghavan, Symphony: distributed hashing in a small world, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.10-10, March 26-28, 2003, Seattle, WA
	Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Journal of Computer and System Sciences, v.73 n.3, p.245-264, May, 2007
	Haifeng Yu , Michael Kaminsky , Phillip B. Gibbons , Abraham Flaxman, SybilGuard: defending against sybil attacks via social networks, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
	Akira Ohtsubo , Shigeaki Tagashira , Satoshi Fujita, A content addressable small-world network, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: parallel and distributed computing and networks, p.209-213, February 13-15, 2007, Innsbruck, Austria
	Thorsten Schütt , Florian Schintke , Alexander Reinefeld, Range queries on structured overlay networks, Computer Communications, v.31 n.2, p.280-291, February, 2008
	Pierre Fraigniaud , Cyril Gavoille , Adrian Kosowski , Emmanuelle Lebhar , Zvi Lotker, Universal augmentation schemes for network navigability: overcoming the √n-barrier, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Ziv Bar-Yossef , Roy Friedman , Gabriel Kliot, RaWMS - Random Walk Based Lightweight Membership Service for Wireless Ad Hoc Networks, ACM Transactions on Computer Systems (TOCS), v.26 n.2, p.1-66, June 2008
	Xiaoping Sun, SCAN: a small-world structured p2p overlay for multi-dimensional queries, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Xiaoping Sun , Xue Chen, SRing: a structured non dht p2p overlay supporting string range queries, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Luca Gatani , Giuseppe Lo Re, An efficient adaptive strategy for searching in peer-to-peer networks, Multiagent and Grid Systems, v.1 n.3, p.209-224, August 2005
	Prithviraj Dasgupta, A Multi-agent Mechanism for Topology Balancing in Unstructured P2P Networks, Proceedings of the IEEE/WIC/ACM international conference on Intelligent Agent Technology, p.389-392, December 18-22, 2006
	Jeffrey Davitz , Jiye Yu , Sugato Basu , David Gutelius , Alexandra Harris, iLink: search and routing in social networks, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Prithviraj Dasgupta, Building small worlds in unstructured P2P networks using a multiagent Bayesian inference mechanism, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Gianluigi Greco , Sergio Greco , Ester Zumpano, Web Communities: Models and Algorithms, World Wide Web, v.7 n.1, p.59-82, March 2004
	Haifeng Yu , Michael Kaminsky , Phillip B. Gibbons , Abraham D. Flaxman, SybilGuard: defending against sybil attacks via social networks, IEEE/ACM Transactions on Networking (TON), v.16 n.3, p.576-589, June 2008
	Roy Friedman , Anne-Marie Kermarrec , Michel Raynal, Modularity: a first class concept to address distributed systems, ACM SIGACT News, v.39 n.2, June 2008
	Joseph S. Kong , Jesse S. A. Bridgewater , Vwani P. Roychowdhury, Resilience of structured P2P systems under churn: The reachable component method, Computer Communications, v.31 n.10, p.2109-2123, June, 2008
	Yaacov Fernandess , Dahlia Malkhi, On spreading recommendations via social gossip, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Jon Kleinberg, The convergence of social and technological networks, Communications of the ACM, v.51 n.11, November 2008
	Chih-Chiang Wang , Khaled Harfoush, Shortest-path routing in randomized DHT-based Peer-to-Peer systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.18, p.3307-3317, December, 2008
	Giancarlo Ruffo , Rossano Schifanella, A peer-to-peer recommender system based on spontaneous affinities, ACM Transactions on Internet Technology (TOIT), v.9 n.1, p.1-34, February 2009
	Yury Lifshits , Shengyu Zhang, Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.318-326, January 04-06, 2009, New York, New York
	Dominic Meier , Yvonne Anne Oswald , Stefan Schmid , Roger Wattenhofer, On the windfall of friendship: inoculation strategies on social networks, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Pierre Fraigniaud , Cyril Gavoille, Polylogarithmic network navigability using compact metrics with small stretch, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Moritz Steiner , Ernst W. Biersack, Shortcuts in a virtual world, Proceedings of the 2006 ACM CoNEXT conference, December 04-07, 2006, Lisboa, Portugal
	Qiaozhu Mei , Deng Cai , Duo Zhang , ChengXiang Zhai, Topic modeling with network regularization, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Peter Kersch , Robert Szabo , Lawrence Cheng , Kerry Jean , Alex Galis, Stochastic maintenance of overlays in structured P2P systems, Computer Communications, v.31 n.3, p.603-619, February, 2008
	Mary Helander , Rick Lawrence , Yan Liu , Claudia Perlich , Chandan Reddy , Saharon Rosset, Looking for great ideas: analyzing the innovation jam, Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis, p.66-73, August 12-12, 2007, San Jose, California
	Tao Gu , Hung Keng Pung , Daqing Zhang, Information retrieval in schema-based P2P systems using one-dimensional semantic space, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.16, p.4543-4560, November, 2007
	Moni Naor , Udi Wieder, Novel architectures for P2P applications: The continuous-discrete approach, ACM Transactions on Algorithms (TALG), v.3 n.3, p.34-es, August 2007
	Xiaomin Ning , Hai Jin , Hao Wu, RSS: A framework enabling ranked search on the semantic web, Information Processing and Management: an International Journal, v.44 n.2, p.893-909, March, 2008
	Augustin Chaintreau , Abderrahmen Mtibaa , Laurent Massoulie , Christophe Diot, The diameter of opportunistic mobile networks, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York
	George Giakkoupis , Vassos Hadzilacos, On the complexity of greedy routing in ring-based peer-to-peer networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Philippe Duchon , Nicole Eggemann , Nicolas Hanusse, Non-searchability of random scale-free graphs, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Olga Goussevskaia , Michael Kuhn , Roger Wattenhofer, Exploring music collections on mobile devices, Proceedings of the 10th international conference on Human computer interaction with mobile devices and services, September 02-05, 2008, Amsterdam, The Netherlands
	Cyrus Shahabi , Farnoush Banaei-Kashani, Modelling P2P data networks under complex system theory, International Journal of Computational Science and Engineering, v.3 n.2, p.103-111, November 2007
	Navin Goyal , Yury Lifshits , Hinrich Schütze, Disorder inequality: a combinatorial approach to nearest neighbor search, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA
	Rex K. Kincaid , Michael J. Holroyd , Christopher Gatz, Understanding the structure of power law networks, Proceedings of the 2007 spring simulation multiconference, March 25-29, 2007, Norfolk, Virginia
	Elena Meshkova , Janne Riihijärvi , Marina Petrova , Petri Mähönen, A survey on resource discovery mechanisms, peer-to-peer and service discovery frameworks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.11, p.2097-2128, August, 2008
	Vittorio Bilò , Angelo Fanelli , Michele Flammini , Luca Moscardelli, Graphical congestion games with linear latencies, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Augustin Chaintreau , Pierre Fraigniaud , Emmanuelle Lebhar, Opportunistic spatial gossip over mobile social networks, Proceedings of the first workshop on Online social networks, August 18-18, 2008, Seattle, WA, USA
	Roie Melamed , Idit Keidar, Araneola: A scalable reliable multicast system for dynamic environments, Journal of Parallel and Distributed Computing, v.68 n.12, p.1539-1560, December, 2008
	Chen Avin, Distance graphs: from random geometric graphs to Bernoulli graphs and between, Proceedings of the fifth international workshop on Foundations of mobile computing, August 18-21, 2008, Toronto, Canada
	Ralph Lange , Frank Dürr , Kurt Rothermel, Scalable processing of trajectory-based queries in space-partitioned moving objects databases, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California
	Chiara Boldrini , Marco Conti , Andrea Passarella, Fast track article: Exploiting users' social relations to forward data in opportunistic networks: The HiBOp solution, Pervasive and Mobile Computing, v.4 n.5, p.633-657, October, 2008
	Augustin Chaintreau , Pierre Fraigniaud , Emmanuelle Lebhar, Forget him and keep on moving, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Gaurav Sharma , Ravi R. Mazumdar, A case for hybrid sensor networks, IEEE/ACM Transactions on Networking (TON), v.16 n.5, p.1121-1132, October 2008
	Vincent Lacroix , Ludovic Cottret , Patricia Thébault , Marie-France Sagot, An Introduction to Metabolic Networks and Their Structural Analysis, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.4, p.594-617, October 2008
	Pierre-Évariste Dagand , Dejan Kostić , Viktor Kuncak, Opis: reliable distributed systems in OCaml, Proceedings of the 4th international workshop on Types in language design and implementation, January 24-24, 2009, Savannah, GA, USA
	Djelloul Boukhelef , Hiroyuki Kitagawa, Dynamic load balancing in RCAN content addressable network, Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication, January 15-16, 2009, Suwon, Korea
	Pierre Fraigniaud , Cyril Gavoille , Adrian Kosowski , Emmanuelle Lebhar , Zvi Lotker, Universal augmentation schemes for network navigability, Theoretical Computer Science, v.410 n.21-23, p.1970-1981, May, 2009
	Sharad Goel , Roby Muhamad , Duncan Watts, Social search in "Small-World" experiments, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain
	Omer Angel , Itai Benjamini , Eran Ofek , Udi Wieder, Routing complexity of faulty networks, Random Structures & Algorithms, v.32 n.1, p.71-87, January 2008
	Martin Dietzfelbinger , Philipp Woelfel, Tight lower bounds for greedy routing in uniform small world rings, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Silvio Lattanzi , D. Sivakumar, Affiliation networks, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Atish Das Sarma , Danupon Nanongkai , Gopal Pandurangan, Fast distributed random walks, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Charles L. Cartledge , Michael L. Nelson, Unsupervised creation of small world networks for the preservation of digital objects, Proceedings of the 9th ACM/IEEE-CS joint conference on Digital libraries, June 15-19, 2009, Austin, TX, USA
	Miguel Rebollo, Small world model for agent search, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
	Harold Thimbleby , Patrick Oladimeji, Social network analysis and interactive device design analysis, Proceedings of the 1st ACM SIGCHI symposium on Engineering interactive computing systems, July 15-17, 2009, Pittsburgh, PA, USA
	Pierre Fraigniaud , George Giakkoupis, The effect of power-law degrees on the navigability of small worlds: [extended abstract], Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Martin Dietzfelbinger , Philipp Woelfel, Brief announcement: tight lower bounds for greedy routing in uniform small world rings, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	O¨ zgu¨r Simsek , David Jensen, Decentralized search in networks using homophily and degree disparity, Proceedings of the 19th international joint conference on Artificial intelligence, p.304-310, July 30-August 05, 2005, Edinburgh, Scotland