Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Design for Optimizability: Traffic Management of a Future Internet Read chapter Read first chapter

2010 | OriginalPaper | Chapter

18. Wayfinding in Social Networks

Author : David Liben-Nowell

Published in: Algorithms for Next Generation Networks

Publisher: Springer London

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

With the recent explosion of popularity of commercial social-networking sites like Facebook and MySpace, the size of social networks that can be studied scientifically has passed from the scale traditionally studied by sociologists and anthropologists to the scale of networks more typically studied by computer scientists. In this chapter, I will highlight a recent line of computational research into the modeling and analysis of the small-world phenomenon – the observation that typical pairs of people in a social network are connected by very short chains of intermediate friends – and the ability of members of a large social network to collectively find efficient routes to reach individuals in the network. I will survey several recent mathematical models of social networks that account for these phenomena, with an emphasis on both the provable properties of these social-network models and the empirical validation of the models against real large-scale social-network data.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter At the Intersection of Networks and Highly Interactive Online Games
Literature
1.
Lada A. Adamic and Eytan Adar. How to search a social network. Social Networks, 27(3): 187–203, July 2005.CrossRef
2.
Lada A. Adamic, Rajan M. Lukose, and Bernardo A. Huberman. Local search in unstructured networks. In Handbook of Graphs and Networks. Wiley-VCH, 2002.
3.
Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, and Bernardo A. Huberman. Search in power-law networks. Physical Review E, 64(046135), 2001.
4.
Lars Backstrom, Jon Kleinberg, Ravi Kumar, and Jasmine Novak. Spatial variation in search engine queries. In Proceedings of the 17th International World Wide Web Conference (WWW’08), pages 357–366, April 2008.
5.
Albert-László Barabási and Eric Bonabeau. Scale-free networks. Scientific American, 288: 50–59, May 2003.CrossRef
6.
David Barbella, George Kachergis, David Liben-Nowell, Anna Sallstrom, and Ben Sowell. Depth of field and cautious-greedy routing in social networks. In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC’07), pages 574–586, December 2007.
7.
Lali Barrière, Pierre Fraigniaud, Evangelos Kranakis, and Danny Krizanc. Efficient routing in networks with long range contacts. In Proceedings of the 15th International Symposium on Distributed Computing (DISC’01), pages 270–284, October 2001.
8.
Béla Bollobás, Oliver Riordan, Joel Spencer, and Gábor Tusnády. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 18(3):279–290, May 2001.MathSciNetMATHCrossRef
9.
Dorwin Cartwright and Alvin Zander. Group Dynamics: Research and Theory. Row, Peterson, 1953.
10.
Augustin Chaintreau, Pierre Fraigniaud, and Emmanuelle Lebhar. Networks become navigable as nodes move and forget. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP’08), pages 133–144, July 2008.
11.
12.
Aaron Clauset, Cosma Rohilla Shalizi, and M. E. J. Newman. Power-law distributions in empirical data. Manuscript, 2007. Available as arXiv:0706.1062.
13.
Peter Sheridan Dodds, Roby Muhamad, and Duncan J. Watts. An experimental study of search in global social networks. Science, 301:827–829, 8 August 2003.
14.
Philippe Duchon, Nicolas Hanusse, Emmanuelle Lebhar, and Nicolas Schabanel. Could any graph be turned into a small world? Theoretical Computer Science, 355(1):96–103, 2006.MathSciNetMATHCrossRef
15.
Philippe Duchon, Nicolas Hanusse, Emmanuelle Lebhar, and Nicolas Schabanel. Towards small world emergence. In Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’06), pages 225–232, August 2006.
16.
Pierre Fraigniaud. Greedy routing in tree-decomposed graphs. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA’05), pages 791–802, October 2005.
17.
Pierre Fraigniaud. Small worlds as navigable augmented networks: Model, analysis, and validation. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA’07), pages 2–11, October 2007.
18.
Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclecticism shrinks even small worlds. In Proceedings of the 23rd Symposium on Principles of Distributed Computing (PODC’04), pages 169–178, July 2004.
19.
Pierre Fraigniaud, Emmanuelle Lebhar, and Zvi Lotker. A doubling dimension threshold θ(loglogn) for augmented graph navigability. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA’06), pages 376–386, September 2006.
20.
Frank Harary and Robert Z. Norman. Graph Theory as a Mathematical Model in Social Science. University of Michigan, 1953.
21.
P. Killworth and H. Bernard. Reverse small world experiment. Social Networks, 1:159–192, 1978.CrossRef
22.
B. J. Kim, C. N. Yoon, S. K. Han, and H. Jeong. Path finding strategies in scale-free networks. Physical Review E, 65(027103), 2002.
23.
Jon Kleinberg. The small-world phenomenon: An algorithmic perspective. In Proceedings of the 32nd Annual Symposium on the Theory of Computation (STOC’00), pages 163–170, May 2000.
24.
Jon Kleinberg. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems (NIPS’01), pages 431–438, December 2001.
25.
Jon Kleinberg. Complex networks and decentralized search algorithms. In International Congress of Mathematicians (ICM’06), August 2006.
26.
Jon M. Kleinberg. Navigation in a small world. Nature, 406:845, 24 August 2000.
27.
Judith Kleinfeld. Could it be a big world after all? The “six degrees of separation” myth. Society, 39(61), April 2002.
28.
Ravi Kumar, David Liben-Nowell, and Andrew Tomkins. Navigating low-dimensional and hierarchical population networks. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA’06), pages 480–491, September 2006.
29.
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, and Eli Upfal. Stochastic models for the web graph. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS’00), pages 57–65, November 2000.
30.
Emmanuelle Lebhar and Nicolas Schabanel. Close to optimal decentralized routing in long-range contact networks. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP’04), pages 894–905, July 2004.
31.
Kurt Lewin. Principles of Topological Psychology. McGraw Hill, 1936.
32.
David Liben-Nowell, Jasmine Novak, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins. Geographic routing in social networks. Proceedings of the National Academy of Sciences, 102(33):11623–11628, August 2005.CrossRef
33.
Kevin Lynch. The Image of the City. MIT Press, 1960.
34.
Gurmeet Singh Manku, Moni Naor, and Udi Wieder. Know thy neighbor’s neighbor: the power of lookahead in randomized P2P networks. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC’04), pages 54–63, June 2004.
35.
Chip Martel and Van Nguyen. Analyzing Kleinberg’s (and other) small-world models. In Proceedings of the 23rd Symposium on Principles of Distributed Computing (PODC’04), pages 179–188, July 2004.
36.
Miller McPherson, Lynn Smith-Lovin, and James M. Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27:415–444, August 2001.CrossRef
37.
Filippo Menczer. Growing and navigating the small world web by local content. Proceedings of the National Academy of Sciences, 99(22):14014–14019, October 2002.CrossRef
38.
Stanley Milgram. The small world problem. Psychology Today, 1:61–67, May 1967.
39.
40.
Jacob L. Moreno. Who Shall Survive? Foundations of Sociometry, Group Psychotherapy and Sociodrama. Nervous and Mental Disesase Publishing Company, 1934.
41.
Van Nguyen and Chip Martel. Analyzing and characterizing small-world graphs. In Proceedings of the 16th ACM–SIAM Symposium on Discrete Algorithms (SODA’05), pages 311–320, January 2005.
42.
Van Nguyen and Chip Martel. Augmented graph models for small-world analysis with geographical factors. In Proceedings of the 4th Workshop on Analytic Algorithms and Combinatorics (ANALCO’08), January 2008.
43.
44.
Oskar Sandberg and Ian Clarke. The evolution of navigable small-world networks. Manuscript, 2006. Available as cs/​0607025.
45.
Georg Simmel. Conflict And The Web Of Group Affiliations. Free Press, 1908. Translated by Kurt H. Wolff and Reinhard Bendix (1955).
46.
Özgür Şimşek and David Jensen. Decentralized search in networks using homophily and degree disparity. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI’05), pages 304–310, August 2005.
47.
Aleksandrs Slivkins. Distance estimation and object location via rings of neighbors. In Proceedings of the 24th Symposium on Principles of Distributed Computing (PODC’05), pages 41–50, July 2005.
48.
Duncan J. Watts, Peter Sheridan Dodds, and M. E. J. Newman. Identity and search in social networks. Science, 296:1302–1305, 17 May 2002.
49.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393:440–442, 1998.CrossRef
Metadata
Title
Wayfinding in Social Networks
Author
David Liben-Nowell
Copyright Year
2010
Publisher
Springer London
Book
Algorithms for Next Generation Networks

Print ISBN: 978-1-84882-764-6

Electronic ISBN: 978-1-84882-765-3

Copyright Year: 2010

DOI
https://doi.org/10.1007/978-1-84882-765-3_18

Premium Partner

    Image Credits