skewed distributions of links that one sees in real net works, with certain nodes acting as highly connected “hubs.” ³

Another principle, also a key issue in sociology, is the notion of “triadic closure:” links are much more likely to form between two people when they have a friend in common. ³⁴ Recent work using email logs has provided some of the first concrete measurements of the effect of triadic closure in a social-communication network. ²⁴

Further principles have begun to emerge from recent studies of social and information networks over time, including “densification effects,” in which the number of links per node increases as the network grows, and “shrinking diameters,” in which the number of steps in the shortest paths between nodes can actually decrease even as the total number of nodes is increasing. ²⁷

It is also intriguing to ask whether machine-learning techniques can be effective at predicting the outcomes of social processes from observations of their early stages. Problems here include the prediction of new links, the participation of people in new activities, the effectiveness of groups at collective problem-solving, and the growth of communities over time. ^{4, 16, 17, 18, 28, 37} Recent work by Salganik, Dodds, and Watts raises the interesting possibility that the outcomes of certain types of social-feedback effects may in fact be inherently unpredictable. ³⁶ Through an online experiment in which participants were assigned to multiple, independently evolving versions of a music-download site— essentially, a set of artificially constructed “parallel universes” in which copies of the site could develop independently—Salganik et al. found that when feedback was provided to users about the popularity of the items being downloaded, early fluctuations in the popularities of different items could get locked in to produce very different long-term trajectories of popularity. Developing an expressive computational model for this phenomenon is an interesting open question.

Ultimately, across all these domains, the availability of such rich and plentiful data on human interaction has closed an important feedback loop, allowing us to develop and evaluate models of social phenomena at

large scales and to use these models in the design of new computing applications. Such questions challenge us to bridge styles of scientific inquiry—ranging from subtle small-group studies to computation on massive datasets—that traditionally have had little contact with each other. And they are compelling questions in need of answers—because at their heart, they are about the human and technological connections that link us all, and the still-mysterious rhythms of the networks we inhabit.

acknowledgments

I thank the National Science Foundation, the MacArthur Foundation, the Cornell Institute for the Social Sciences, Google, and Yahoo for their support and the anonymous reviewers of this manuscript for their comments and feedback.

 

References

1. adamic, l. and adar, e. how to search a social network.

Social Net works 27, 3 (2005), 187–203.

2. adar, e., zhang, l., adamic, l.a., and lukose, r.m. implicit structure and the dynamics of blogspace. in Proceedings of the Workshop on the Weblogging Ecosystem, 2004.

3. albert, r. and barabósi, a-l. statistical mechanics of complex networks. Reviews of Modern Physics 74 (2002), 47–97.

4. backstrom, l., huttenlocher, d., Kleinberg, J., and lan, x. Group formation in large social networks: membership, growth, and evolution. in Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006.

5. bookstein, a. informetric distributions, part ii: resilience to ambiguity. J. American Society for Information Science 41, 5 (1990), 376–386.

6. Centola, d. and macy, m. Complex contagions and the weakness of long ties. American J. of Sociology 113 (2007), 702–734.

7. de sola pool, i. and Kochen, m. Contacts and influence. Social Net works 1, 1 (1978) 5–51.

8. demers, a.J., Greene, d.h., hauser, C., irish, W., larson, J., shenker, s., sturgis, h.e., swinehart, d.C., and terry, d.b. epidemic algorithms for replicated database maintenance. in Proceedings of the 6th ACM Symposium on Principles of Distributed Computing (1987), 1–12.

9. dodds, p., muhamad, r., and Watts, d. an experimental study of search in global social networks. Science 301 (2003), 827–829.

10. dodds, p. and Watts, d. universal behavior in a generalized model of contagion. Physical Review Letters 92 (2004).

11. domingos, p. and richardson, m. mining the network value of customers. in Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2001), 57–66.

12. Garfield, e. it’s a small world after all. Current Contents 43 (1979), 5–10.

13. Granovetter, m. threshold models of collective behavior. American J. Sociology 83 (1978), 1420–1443.

14. Gruhl, d., liben-nowell, d., Guha, r.v., and tomkins, a. information diffusion through blogspace. in Proceedings of the 13th International World Wide Web Conference, 2004.

15. Guare, J. Six Degrees of Separation: A Play. vintage books, 1990.

16. hill, s., provost, f., and volinsky, C. network-based marketing: identifying likely adopters via consumer networks. Statistical Science 21, 2 (2006), 256–278.

17. hoff, p.d., raftery, a.e., and handcock, m.s. latent space approaches to social network analysis. J.

American Statistical Association 97 (2002).

18. Kearns, m., suri, s., and montfort, n. an experimental study of the coloring problem on human subject networks. Science 313 (2006), 824–827.

19. Kempe, d., Kleinberg, J., and tardos, e. maximizing the spread of influence in a social network. in Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2003), 137–146.

20. Kleinberg, J. the small-world phenomenon: an algorithmic perspective. in Proceedings of the 32nd ACM Symposium on Theory of Computing (2000), 163–170.

21. Kleinberg, J. small-world phenomena and the dynamics of information. in Proceedings of the 14th Advances in Neural Information Processing Systems (2001), 431–438.

22. Kleinberg, J. and raghavan, p. Query incentive networks. in Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (2005), 132–141.

23. Korte, C. and milgram, s. acquaintance networks between racial groups: application of the small world method. J. Personality and Social Psychology 15 (1978).

24. Kossinets, G., and Watts, d. empirical analysis of an evolving social network. Science 311 (2006), 88–90.

25. leskovec, J., adamic, l., and huberman, b. the dynamics of viral marketing. ACM Transactions on the Web 1, 1 (may 2007).

26. leskovec, J. and horvitz, e. Worldwide buzz: planetary-scale views on an instant-messaging network. in Proceedings of the 17th International World Wide Web Conference, 2008.

27. leskovec, J., Kleinberg, J.m., and faloutsos, C. Graphs over time: densification laws, shrinking diameters and possible explanations. in Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2005), 177–187.

28. liben-nowell, d. and Kleinberg, J. the link-prediction problem for social networks. J. American Society for Information Science and Technology 58, 7 (2007), 1019–1031.

29. liben-nowell, d. and Kleinberg, J. tracing information flow on a global scale using internet chain-letter data. in Proceedings of Natl. Acad. Sci. 105, 12 (mar. 2008), 4633–4638.

30. liben-nowell, d., novak, J., Kumar, r., raghavan, p., and tomkins, a. Geographic routing in social networks. in Proceedings of Natl. Acad. Sci. 102, 33 (aug. 2005), 11623–11628.

31. lua, e. K., Crowcroft, J., pias, m., sharma, r., and lim, s. a survey and comparison of peer-to-peer overlay network schemes. IEEE Commun. Surveys and Tutorials 7, 2 (2005), 72–93.

32. mossel, e. and roch, s. on the submodularity of influence in social networks. in Proceedings of the 39th ACM Symposium on Theory of Computing, 2007.

33. newman, m.e.J. the structure and function of complex networks. SIAM Review, 45 (2003), 167–256.

34. rapoport, a. spread of information through a population with socio-structural bias i: assumption of transitivity. Bulletin of Mathematical Biophysics 15, 4 (dec. 1953), 523–533.

35. rogers, e. Diffusion of Innovations, 4th Edition. free press, 1995.

36. salganik, m., dodds, p., and Watts, d. experimental study of inequality and unpredictability in an artificial cultural market. Science 311 (2006), 854–856.

37. sarkar, p. and moore, a. W. dynamic social network analysis using latent space models. in Advances in Neural Information Processing Systems, 2005.

38. travers, J. and milgram, s. an experimental study of the small world problem. Sociometry 32, 4 (1969), 425–443.

39. Watts, d.J., dodds, p.s., and newman, m.e. J. identity and search in social networks. Science 296 (may 2002), 1302–1305.

40. Watts, d.J. and strogatz, s.h. Collective dynamics of ‘small-world’ networks. Nature 393 (1998), 440–442.

 

Jon Kleinberg ( [e-mail]) is a professor of computer science at Cornell university, ithaca, ny. his work focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other online media. he is a recipient of macarthur, packard, and sloan foundation fellowships, and the nevanlinna prize from the international mathematical union.