Social search in "Small-World" experiments

ABSTRACT

The "algorithmic small-world hypothesis" states that not only are pairs of individuals in a large social network connected by short paths, but that ordinary individuals can find these paths. Although theoretically plausible, empirical evidence for the hypothesis is limited, as most chains in "small-world" experiments fail to complete, thereby biasing estimates of "true" chain lengths. Using data from two recent small-world experiments, comprising a total of 162,328 message chains, and directed at one of 30 "targets" spread across 19 countries, we model heterogeneity in chain attrition rates as a function of individual attributes. We then introduce a rigorous way of estimating true chain lengths that is provably unbiased, and can account for empirically-observed variation in attrition rates. Our findings provide mixed support for the algorithmic hypothesis. On the one hand, it appears that roughly half of all chains can be completed in 6-7 steps--thus supporting the "six degrees of separation" assertion--but on the other hand, estimates of the mean are much longer, suggesting that for at least some of the population, the world is not "small" in the algorithmic sense. We conclude that search distances in social networks are fundamentally different from topological distances, for which the mean and median of the shortest path lengths between nodes tend to be similar.

REFERENCES

• 1: L. Adamic and E. Adar. How to search a social network. Social Networks, 27:187--203, 2005.
• 2: L. Adamic, R. Lukose, A. Puniyani, and B. Huberman. Search in power-law networks. Physical Review E, 64, 2001.
• 3: Samuel J. Best , Brian Krueger , Clark Hubbard , Andrew Smith, An assessment of generalizability of Internet surveys, Social Science Computer Review, v.19 n.2, p.131-145, June 12 2001 [doi>10.1177/089443930101900201]
• 4: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 5: J. S. Coleman. Social capital in the creation of human capital. The American Journal of Sociology, 94:S95--S120, 1988.
• 6: P. Dodds, R. Muhamad, and D. J. Watts. An experimental study of search in global social networks. Science, 301:827--829, 2003.
• 7: A. Gelman and J. Hill. Data Analysis Using Regression and Multileve/Hierarchical Models. Cambridge University Press, 2007.
• 8: S. Golder, D. Wilkinson, and B. A. Huberman. Rhythms of social interaction: Messaging within a massive online network. In 3rd International Conference on Communities and Technologies, 2007.
• 9: M. Granovetter. Getting a Job: A Study of Contacts and Careers. Harvard University Press, 2nd edition, 1995.
• 10: J. Guare. Six Degrees of Separation. 1990.
• 11: J. Guiot. A modification of milgram's small world method. European Journal of Social Psychology, 6:503--507, 1976.
• 12: H. Jeong, B. Tombor, R. Albert, Z. N. Oltval, and A. L. Barabasi. The large-scale organization of metabolic networks. Nature, 407:651--654, 2000.
• 13: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 14: J. Kleinberg. Navigation in a small world. Nature, 406, 2000.
• 15: J. Kleinfeld. Could it be a big world after all? Society, 39:61--66, 2002.
• 16: B. Kogut and G. Walker. The small world of germany and the durability of national networks. American Sociological Review, 66:317--335, 2001.
• 17: C. Korte and S. Milgram. Acquaintance networks between racial groups: Application of the small world method. Journal of Personality and Social Psychology, 15:101--108, 1970.
• 18: G. Kossinets and D. Watts. Empirical analysis of an evolving social network. Science, 311:88--90, 2006.
• 19: N. H. Lee. The Search for an Abortionist. The University of Chicago Press, 1969.
• 20: Jure Leskovec , Eric Horvitz, Planetary-scale views on a large instant-messaging network, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367620]
• 21: D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. Proc. Natl. Acad. Sci. USA, 102:11623--11628, 2005.
• 22: N. Lin, P. Dayton, and P. Greenwald. The urban communication network and social stratification: A "small world experiment". In B. D. Ruben, editor, Communication Yearbook, pages 107--119. Transaction Books, 1978.
• 23: C. Lundberg. Patterns of acquaintanceship in society and complex organization: A comparative study of the small world problem. Pacific Sociological Review, 18:206--222, 1975.
• 24: J. W. Meshel. One phone call away: Secrets of a master networker, 2005. Portfolio.
• 25: S. Milgram. The small world problem. Psychology Today, 1:60--67, 1967.
• 26: A. E. Motter, T. Nishikawa, and Y. C. Lai. Large-scale structural organization of social networks|. Physical Review E, 68, 2003.
• 27: M. E. J. Newman. The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. USA, 98:404--409, 2001.
• 28: O. Pierson. The Unwritten Rules of Highly Effective Job Search. McGraw-Hill, 2006.
• 29: A. Portes. Social capital: Its origins and applications in modern sociology. Annual Review of Sociology, 24:1--24, 1998.
• 30: D. Rezac. Work the Pond! Berkley Publishing Group, 2005.
• 31: P. Sen, S. Dasgupta, A. Chatterjee, P. A. Sreeram, G. Mukherjee, and S. S. Manna. Small-world properties of the indian railway network. Physical Review E, 67, 2003.
• 32: R. Shotland. University Communication Networks: The Small World Method. Wiley, 1976.
• 33: O. Simsek and D. Jensen. Decentralized search in networks using homophily and degree disparity. In Proceedings of the Ninenteenth International Joint Conference on Artificial Intelligence, 2005.
• 34: J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry, 32:425--443, 1969.
• 35: A. Wagner and D. A. Fell. The small world inside large metabolic networks. Proceedings of the Royal Society of London Series B--Biological Sciences, 268:1803--1810, 2001.
• 36: D. J. Watts. Six Degrees: The Science of A Connected Age. W. W. Norton, 2003.
• 37: D. J. Watts, P. S. Dodds, and M. E. J. Newman. Identity and search in social networks. Science, 296:1302--1305, 2002.
• 38: D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
• 39: H. C. White. Search parameters for small world problem. Social Forces, 49:259--264, 1970.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Experimentation, Human Factors

Keywords:
attrition, small-world experiment, social search