skewed distributions of links that one
sees in real net works, with certain nodes
acting as highly connected “hubs.” 3
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. 34 Recent
work using email logs has provided
some of the first concrete measurements of the effect of triadic closure in
a social-communication network. 24
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. 27
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. 36 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.
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
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
3. albert, r. and barabósi, a-l. statistical mechanics
of complex networks. Reviews of Modern Physics 74
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
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
9. dodds, p., muhamad, r., and Watts, d. an experimental
study of search in global social networks. Science 301
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
15. Guare, J. Six Degrees of Separation: A Play. vintage
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),
20. Kleinberg, J. the small-world phenomenon: an
algorithmic perspective. in Proceedings of the 32nd
ACM Symposium on Theory of Computing (2000),
21. Kleinberg, J. small-world phenomena and the
dynamics of information. in Proceedings of the 14th
Advances in Neural Information Processing Systems
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
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
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),
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),
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),
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
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),
39. Watts, d.J., dodds, p.s., and newman, m.e. J. identity
and search in social networks. Science 296 (may 2002),
40. Watts, d.J. and strogatz, s.h. Collective dynamics of
‘small-world’ networks. Nature 393 (1998), 440–442.
Jon Kleinberg ( firstname.lastname@example.org) 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.