Weitere Kapitel dieses Buchs durch Wischen aufrufen
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.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Lada A. Adamic and Eytan Adar. How to search a social network. Social Networks, 27(3): 187–203, July 2005. CrossRef
Lada A. Adamic, Rajan M. Lukose, and Bernardo A. Huberman. Local search in unstructured networks. In Handbook of Graphs and Networks. Wiley-VCH, 2002.
Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, and Bernardo A. Huberman. Search in power-law networks. Physical Review E, 64(046135), 2001.
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.
Albert-László Barabási and Eric Bonabeau. Scale-free networks. Scientific American, 288: 50–59, May 2003. CrossRef
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.
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.
Dorwin Cartwright and Alvin Zander. Group Dynamics: Research and Theory. Row, Peterson, 1953.
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.
Aaron Clauset and Cristopher Moore. How do networks become navigable? Manuscript, 2003. Available as cond-mat/0309415.
Aaron Clauset, Cosma Rohilla Shalizi, and M. E. J. Newman. Power-law distributions in empirical data. Manuscript, 2007. Available as arXiv:0706.1062.
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.
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.
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.
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.
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.
Pierre Fraigniaud, Emmanuelle Lebhar, and Zvi Lotker. A doubling dimension threshold θ(loglog n) for augmented graph navigability. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA’06), pages 376–386, September 2006.
Frank Harary and Robert Z. Norman. Graph Theory as a Mathematical Model in Social Science. University of Michigan, 1953.
P. Killworth and H. Bernard. Reverse small world experiment. Social Networks, 1:159–192, 1978. CrossRef
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.
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.
Jon Kleinberg. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems (NIPS’01), pages 431–438, December 2001.
Jon Kleinberg. Complex networks and decentralized search algorithms. In International Congress of Mathematicians (ICM’06), August 2006.
Jon M. Kleinberg. Navigation in a small world. Nature, 406:845, 24 August 2000.
Judith Kleinfeld. Could it be a big world after all? The “six degrees of separation” myth. Society, 39(61), April 2002.
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.
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.
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.
Kurt Lewin. Principles of Topological Psychology. McGraw Hill, 1936.
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
Kevin Lynch. The Image of the City. MIT Press, 1960.
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.
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.
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
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
Stanley Milgram. The small world problem. Psychology Today, 1:61–67, May 1967.
Jacob L. Moreno. Who Shall Survive? Foundations of Sociometry, Group Psychotherapy and Sociodrama. Nervous and Mental Disesase Publishing Company, 1934.
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.
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.
Roper Public Affairs and National Geographic Society. 2006 geographic literacy study, May 2006. http://www.nationalgeographic.com/roper2006.
Oskar Sandberg and Ian Clarke. The evolution of navigable small-world networks. Manuscript, 2006. Available as cs/0607025.
Georg Simmel. Conflict And The Web Of Group Affiliations. Free Press, 1908. Translated by Kurt H. Wolff and Reinhard Bendix (1955).
Ö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.
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.
Duncan J. Watts, Peter Sheridan Dodds, and M. E. J. Newman. Identity and search in social networks. Science, 296:1302–1305, 17 May 2002.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393:440–442, 1998. CrossRef
- Wayfinding in Social Networks
- Springer London
- Chapter 18
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia