Delay of Social Search on Small-World Graphs

REFERENCES

• Adamic , L. A. , Lukose , R. M. , Puniyani A. R. , & Huberman , B. A. ( 2001 ). Search in power-law networks . Physical Review E , 64 , Article 046135 .
   PubMed Web of Science ®Google Scholar
• Amaral , L. A. N. , Scala , A. , Barthelemy , M. , Stanley , H. E. ( 2000 ). Classes of small-world networks . Proceedings of the National Academy of Sciences , 97 , 11149 – 11152 .
   PubMed Web of Science ®Google Scholar
• Axelrod , R. ( 1997 ). The dissemination of culture: a model with local convergence and global polarization . The Journal of Conflict Resolution , 41 , 203 – 226 .
   Web of Science ®Google Scholar
• Axtell , R. L. , Epstein , J. M. , Dean , J. S. , Gumerman , G. J. , Swedlund , A. C. , Harburger , J. , … Parker , M. ( 2002 ). Population growth and collapse in a multiagent model of the Kayenta Anasazi in Long House Valley . Proceedings of the National Academy of Sciences , 99 , 7275 – 7279 .
   PubMed Web of Science ®Google Scholar
• Barabási , A.-L. ( 2002 ). Linked: The new science of networks . Cambridge , MA : Perseus .
   Google Scholar
• Barnett , G. A. ( 1989 ). Approaches to non-Euclidean network analysis . In M. Kochen (Ed.), The small world (pp. 349 – 372 ). Norwood , NJ : Ablex .
   Google Scholar
• Bassett , D. S. , & Bullmore , E. ( 2006 ). Small-world brain networks . Neuroscientist , 12 , 512 – 523 .
   PubMed Web of Science ®Google Scholar
• Bearman , P. S. , Moody , J. , & Stovel , K. ( 2004 ). Chains of affection: The structure of adolescent romantic and social networks . American Journal of Sociology , 110 , 44 – 91 .
   Web of Science ®Google Scholar
• Bell , D. C. , Belli-McQueen , B. , & Haider , A. ( 2007 ). Partner naming and forgetting: Recall of network members . Social Networks , 29 , 279 – 299 .
   PubMed Web of Science ®Google Scholar
• Bernard , H. R. , Johnsen , E. C. , Killworth , P. D. , & Robinson , S. ( 1991 ). Estimating the size of an average personal network and of an event population: Some empirical results . Social Science Research , 20 , 109 – 121 .
   Web of Science ®Google Scholar
• Bernard , H. R. , Killworth , P. D. , Johnsen , E. C. , Shelley , G. A. , & McCarty , C. ( 2001 ). Estimating the ripple effect of a disaster . Connections , 24 , 18 – 22 .
   Google Scholar
• Bollobás , B. ( 2001 ). Random graphs . Cambridge , UK : Cambridge University Press .
   Google Scholar
• Burt , R. S. ( 1992 ). Structural holes: The social structure of competition . Cambridge, MA : Harvard University Press .
   Google Scholar
• Callaway , D. S. , Newman , M. E. J. , Strogatz , S. H. , & Watts , D. J. ( 2000 ). Network robustness and fragility: Percolation on random graphs . Physical Review Letters , 85 , 5468 – 5471 .
   PubMed Web of Science ®Google Scholar
• Centola , D. , & Macy , M. ( 2007 ). Complex contagions and the weakness of long ties . American Journal of Sociology , 113 , 702 – 734 .
   Web of Science ®Google Scholar
• Centola , D. , Willer , R. , & Macy , M. ( 2005 ). The emperor's dilemma: A computational model of self-enforcing norms . American Journal of Sociology , 110 , 1009 – 1040 .
   Web of Science ®Google Scholar
• Chaintreau , A. , Fraigniaud , P. , & Lebhar , E. (2008). Networks become navigable as nodes move and forget. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (pp.133–144). Berlin , Germany : Springer-Verlag.
   Google Scholar
• Clauset , A. , & Moore , C. ( 2003 ). How do networks become navigable? Retrieved from http://arxiv.org/abs/cond-mat/0309415
   Google Scholar
• Cohen , J. E. , Briand , F. , & Newman , C. M. ( 1990 ). Community food webs: Data and theory . Berlin , Germany : Springer .
   Google Scholar
• Cohen , L. , Frazzini , A. , & Malloy , C. ( 2008 ). The small world of investing: Board connections and mutual fund returns . Journal of Political Economy , 116 , 951 – 979 .
   Web of Science ®Google Scholar
• Coleman , J. , Katz , E. , & Menzel , H. ( 1957 ). The diffusion of an innovation among physicians . Sociometry , 20 , 253 – 270 .
   Google Scholar
• Davidson , M. L. ( 1983 ). Multidimensional scaling . New York , NY : Wiley .
   Google Scholar
• Dodds , P. S. , Muhamad , R. , & Watts , D. J. ( 2003 ). An experimental study of search in global social networks . Science , 301 , 827 – 829 .
   PubMed Web of Science ®Google Scholar
• Donovan , P. ( 2007 ). How idle is idle talk? One hundred years of rumor research . Diogenes , 54 , 59 – 83 .
   Web of Science ®Google Scholar
• Duchon , P. , Hanusse , N. , Lebhar , E. , & Schabanel , N. ( 2006 ). Could any graph be turned into a small-world? Theoretical Computer Science , 355 , 96 – 103 .
   Web of Science ®Google Scholar
• Dunbar , R. I. M. ( 1993 ). Coevolution of neocortical size, group size and language in humans . Behavioral and Brain Sciences , 16 , 681 – 735 .
   Web of Science ®Google Scholar
• Epstein , J. M. ( 1999 ). Agent-based computational models and generative social science . Complexity , 4 , 41 – 60 .
   Google Scholar
• Erickson , B. H. , & Kringas , P. ( 1975 ). Small world of politics, or seeking elites from bottom up . Canadian Research Sociology Quarterly , 12 , 585 – 593 .
   Web of Science ®Google Scholar
• Fraigniaud , P. , & Giakkoupis , G. ( 2009 ). The effect of power-law degrees on the navigability of small worlds . In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (pp. 240–249). New York , NY : ACM .
   Google Scholar
• Franceschetti , M. , & Meester , R. ( 2006 ). Navigation in small-world networks: A scale-free continuum model . Journal of Applied Probability , 43 , 1173 – 1180 .
   Web of Science ®Google Scholar
• Goel , S. , Muhamad , R. , & Watts , D. J. ( 2009 ). Social search in “small-world” experiments . In Proceedings of the 18th International World Wide Web Conference (pp. 701–710). New York , NY : ACM .
   Google Scholar
• Gowaikar , R. , & Hassibi , B. ( 2006 ). Communication over a wireless network with random connections . IEEE Transactions on Information Theory , 52 , 2857 – 2871 .
   Web of Science ®Google Scholar
• Granovetter , M. S. ( 1973 ). The strength of weak ties . American Journal of Sociology , 78 , 1360 – 1380 .
   Web of Science ®Google Scholar
• Granovetter , M. S. ( 1983 ). The strength of weak ties: A network theory revisited . Sociological Theory , 1 , 201 – 233 .
   Google Scholar
• Guiot , J. M. ( 1976 ). A modification of Milgram's small world method . European Journal of Social Psychology , 6 , 503 – 507 .
   Web of Science ®Google Scholar
• Gupta , P. , & Kumar , P. R. ( 2000 ). The capacity of wireless networks . IEEE Transactions on Information Theory , 46 , 388 – 404 .
   Web of Science ®Google Scholar
• Hekmat , R. , & Mieghem , P. V. ( 2004 ). Study of connectivity in wireless ad hoc networks with an improved radio model. In Proceedings of the 2nd Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (pp. 142–151). New York, NY: IEEE .
   Google Scholar
• Hill , R. A. , & Dunbar , R. I. M. ( 2003 ). Social network size in humans . Human Nature , 14 , 53 – 72 .
   PubMed Web of Science ®Google Scholar
• Inaltekin , H. , Chiang , M. , & Poor , H. V. ( 2010 ). Average message delivery time for small-world networks in the continuum limit . IEEE Transactions on Information Theory , 56 , 4447 – 4470 .
   Web of Science ®Google Scholar
• Killworth , P. D. , McCarty , C. , Bernard , H. R. , & House , M. ( 2006 ). Social networks: the accuracy of small world chains in sociological networks . Social Networks , 28 , 85 – 96 .
   Web of Science ®Google Scholar
• Kleinberg , J. M. (2000a). Navigation in a small world. Nature , 406, 845.
   PubMed Web of Science ®Google Scholar
• Kleinberg , J. M. ( 2000b ). The small-world phenomenon: An algorithmic perspective . In Proceedings of the 32nd ACM Symposium on Theory of Computing (pp. 163 – 170 ). New York , NY : ACM .
   Google Scholar
• Kleinfeld , J. ( 2002 ). The small world problem . Society , 39 , 61 – 66 .
   Web of Science ®Google Scholar
• Klovdahl , A. S. ( 1985 ). Social networks and the spread of infectious diseases: The AIDS example . Social Science and Medicine , 21 , 1203 – 1216 .
   PubMed Web of Science ®Google Scholar
• Kochen , M. ( 1985 ). The structure of acquaintance nets and rates of social development . Social Networks , 7 , 323 – 339 .
   Web of Science ®Google Scholar
• Korte , C. , & Milgram , S. ( 1970 ). Acquaintance linking between white and Negro populations: applications of the small world problem . Journal of Personality and Social Psychology , 15 , 101 – 118 .
   Web of Science ®Google Scholar
• Kossinets , G. , & Watts , D. J. ( 2006 ). Empirical analysis of an evolving social network . Science , 311 , 88 – 90 .
   PubMed Web of Science ®Google Scholar
• Lee , N. H. ( 1969 ). The search for an abortionist . Chicago , IL : University of Chicago Press .
   Google Scholar
• Leskovec , J. , & Horvitz , E. ( 2008 ). Planetary-scale views on a large instant-messaging network . In Proceedings of the 17th International World Wide Web Conference (pp. 915 – 924 ). New York , NY : ACM .
   Google Scholar
• Lin , N. , Dayton , P. W. , & Greenwald , P. ( 1977 ). The urban communication network and social stratification: A “small world” experiment . In B. D. Ruben (Ed.), Communication yearbook (pp. 107 – 119 ). New Brunswick , NJ : Transaction Book .
   Google Scholar
• Macy , M. W. , & Willer , R. ( 2002 ). From factors to actors: computational sociology and agent-based modeling . Annual Review of Sociology , 28 , 143 – 166 .
   Web of Science ®Google Scholar
• Malaquias , J. L. , Rosa , A. C. , & Correia , C. M. B. A. ( 2006 ). A small-world model of the human mind. In Proceedings of the 2006 ACM Symposium on Applied Computing (pp. 15–22) New York, NY: ACM .
   Google Scholar
• Manku , G. S. , Bawa , M. , & Raghavan , P. ( 2003 ). Symphony: Distributed hashing in a small world. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (pp. 127–140). Berkeley, CA: USENIX
   Google Scholar
• McCarty , C. , Killworth , P. D. , Bernard , H. R. , Johnsen , E. , & Shelley , G. A. ( 2001 ). Comparing two methods for estimating network size . Human Organization , 60 , 28 – 39 .
   Web of Science ®Google Scholar
• Milgram , S. ( 1967 ). The small world problem . Psychology Today , 1 , 61 – 67 .
   Google Scholar
• Moody , J. ( 2002 ). The importance of relationship timing for diffusion . Social Forces , 81 , 25 – 56 .
   Web of Science ®Google Scholar
• Newman , M. E. J. ( 2001 ). The structure of scientific collaboration networks . Proceedings of the National Academia of Sciences , 98 , 404 – 409 .
   PubMed Web of Science ®Google Scholar
• Newman , M. E. J. ( 2003a ). Ego-centered networks and the ripple effect . Social Networks , 25 , 83 – 95 .
   Web of Science ®Google Scholar
• Newman , M. E. J. ( 2003b ). The structure and function of complex networks . SIAM Review , 45 , 167 – 256 .
   Web of Science ®Google Scholar
• Newman , M. E. J. , Moore , C. , & Watts , D. J. ( 2000 ). Mean-field solution of the small-world network model . Physical Review Letters , 84 , 3201 – 3204 .
   PubMed Web of Science ®Google Scholar
• Nguyen , V. , & Martel , C. U. ( 2006 ). Designing low cost networks with short routes and low congestion. In Proceedings of the 25th IEEE International Conference on Computer Communications (pp. 1–12). New York, NY: IEEE .
   Google Scholar
• Nowak , M. A. , & Sigmund , K. ( 1992 ). Tit for tat in heterogenous populations . Nature , 355 , 250 – 253 .
   Web of Science ®Google Scholar
• Nowell , D. L. , Novak , J. , Kumar , R. , Raghavan , P. , & Tomkins , A. ( 2005 ). Geographic routing in social networks . Proceedings of the National Academy of Sciences , 102 , 11623 – 11628 .
   PubMed Web of Science ®Google Scholar
• Penrose , M. (2003). Random geometric graphs . New York , NY : Oxford University Press.
   Google Scholar
• Pool , I. D. S. , & Kochen , M. ( 1978 ). Contacts and influence . Social Networks , 1 , 5 – 51 .
   Web of Science ®Google Scholar
• Rapoport , A. ( 1963 ). Mathematical models of social interaction . In R. D. Luce , R. R. Bush , & E. Galanter , (Eds.), Handbook of mathematical psychology (pp. 493 – 579 ). New York , NY : John Wiley and Sons .
   Google Scholar
• Rudin , W. ( 1987 ). Real and complex analysis . New York , NY : McGraw-Hill .
   Google Scholar
• Schelling , T. C. ( 1971 ). Dynamic models of segregation . Journal of Mathematical Sociology , 1 , 143 – 186 .
   Web of Science ®Google Scholar
• Schenettler , S. ( 2009a ). A small world on feet of clay? A comparison of empirical small-world studies against best-practice criteria . Social Networks , 31 , 179 – 189 .
   Web of Science ®Google Scholar
• Schenettler , S. ( 2009b ). A structured overview of 50 years of small-world research . Social Networks , 31 , 165 – 178 .
   Web of Science ®Google Scholar
• Shotland , R. L. ( 1976 ). University communication networks: The small world method . New York , NY : Wiley .
   Google Scholar
• Stevenson , W. B. , Davidson , B. , Manev , I. , & Walsh , K. ( 1997 ). The small world of the university: a classroom exercise in the study of networks . Connections , 20 , 23 – 33 .
   Google Scholar
• Strogatz , S. H. ( 2001 ). Exploring complex networks . Nature , 410 , 268 – 276 .
   PubMed Web of Science ®Google Scholar
• Travers , J. , & Milgram , S. ( 1969 ). An experimental study of the small world problem . Sociometry , 32 , 425 – 443 .
   Google Scholar
• Watts , D. J. ( 1999 ). Small worlds: The dynamics of networks between order and randomness . Princeton, NJ : Princeton University Press .
   Google Scholar
• Watts , D. J. ( 2003 ). Six degrees: The science of a connected age . New York , NY : Norton & Company .
   Google Scholar
• Watts , D. J. ( 2004 ). The “new” science of networks . Annual Review of Sociology , 30 , 243 – 270 .
   Web of Science ®Google Scholar
• Watts , D. J. , Dodds , P. S. , & Newman , M. E. J. ( 2002 ). Identity and search in social networks . Science , 296 , 1302 – 1304 .
   PubMed Web of Science ®Google Scholar
• Watts , D. J. , & Strogatz , S. H. ( 1998 ). Collective dynamics of small-world networks . Nature , 393 , 440 – 442 .
   PubMed Web of Science ®Google Scholar
• Weimann , G. ( 1983 ). The not-so-small world—Ethnicity and acquaintance networks in Israel . Social Networks , 5 , 289 – 302 .
   Web of Science ®Google Scholar
• Williams , R. J. , & Martinez , N. D. ( 2000 ). Simple rules yield complex food webs . Nature , 404 , 180 – 183 .
   PubMed Web of Science ®Google Scholar