skip to main content
10.1145/1526709.1526804acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Social search in "Small-World" experiments

Published: 20 April 2009 Publication History

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]
J. Best, B. Krueger, and C. Smith. An assessment of the generalizability of internet surveys. Social Science Computer Review, 19:131--145, 2001.
[4]
A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. W. 2000. Graph structure in the web. Computer Networks, pages 309--320, 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]
J. Kleinberg. The small-world phenomenon: An algorithmic perspective. In 32nd ACM Symposium on Theory of Computing, 1999.
[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]
J. Leskovec and E. Horvitz. Planetary-scale views on a large instant-messaging network. In 17th International World Wide Web Conference, 2008.
[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.

Cited By

View all
  • (2021)Follow Recommendation in Social NetworksUbiquitous Networking10.1007/978-3-030-86356-2_23(280-292)Online publication date: 12-Dec-2021
  • (2019)The Structure and Evolution of an Offline Peer-to-Peer Financial Network10.1007/978-3-030-14459-3_9(113-122)Online publication date: 6-Mar-2019
  • (2018)Hybrid Approach for Predicting and Recommending Links in Social NetworksComputational Intelligence: Theories, Applications and Future Directions - Volume II10.1007/978-981-13-1135-2_9(107-119)Online publication date: 2-Sep-2018
  • Show More Cited By

Index Terms

  1. Social search in "Small-World" experiments

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WWW '09: Proceedings of the 18th international conference on World wide web
    April 2009
    1280 pages
    ISBN:9781605584874
    DOI:10.1145/1526709

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 20 April 2009

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. attrition
    2. small-world experiment
    3. social search

    Qualifiers

    • Research-article

    Conference

    WWW '09
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)4
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 22 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Follow Recommendation in Social NetworksUbiquitous Networking10.1007/978-3-030-86356-2_23(280-292)Online publication date: 12-Dec-2021
    • (2019)The Structure and Evolution of an Offline Peer-to-Peer Financial Network10.1007/978-3-030-14459-3_9(113-122)Online publication date: 6-Mar-2019
    • (2018)Hybrid Approach for Predicting and Recommending Links in Social NetworksComputational Intelligence: Theories, Applications and Future Directions - Volume II10.1007/978-981-13-1135-2_9(107-119)Online publication date: 2-Sep-2018
    • (2017)Le sens commun et les explications sociologiquesCommon sense and sociological explanationsSociologie et sociétés10.7202/1054278ar49:2(163)Online publication date: 2017
    • (2017)Personal Networks of Scientific Collaborators: A Large Scale Experimental Analysis of Their EvolutionInformation Search, Integration, and Personlization10.1007/978-3-319-68282-2_8(116-139)Online publication date: 4-Oct-2017
    • (2017)Social SearchSocial Information Seeking10.1007/978-3-319-56756-3_5(75-90)Online publication date: 29-Jun-2017
    • (2016)Similarity Index based Link Prediction Algorithms in Social Networks: A SurveyJournal of Telecommunications and Information Technology10.26636/jtit.2016.2.7252:2016(87-94)Online publication date: 30-Jun-2016
    • (2015)Search in Combined Social and Wireless Communication Networks: Delay and Success AnalysisIEEE Transactions on Wireless Communications10.1109/TWC.2015.243085714:9(4972-4980)Online publication date: Sep-2015
    • (2015)Mechanism Design for Finding Experts Using Locally Constructed Social Referral WebIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.11726:8(2316-2326)Online publication date: Aug-2015
    • (2014)Geospatial Structure of a Planetary-Scale Social NetworkIEEE Transactions on Computational Social Systems10.1109/TCSS.2014.23777891:3(156-163)Online publication date: Sep-2014
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media