Resources: Papers
Here I will maintain an extended, topically-organized list of papers/references around the
course material.
Graph Theory
Random graphs
Centrality
Hubs and Authorities
PageRank
Spectral Analysis
Similarity
- Sec 7.12 and 13
of the book Networks, An Introduction, by Newman.
- Chapter
4 of E&K.
Networks
with positive and negative links
- Chapter
5 of E&K.
- J.A. Davis. Structural
balance, mechanical solidarity, and interpersonal relations. American
Journal of Sociology, 68:444?62, 1963.
- J. Leskovec, D. Huttenlocher,
J. Kleinberg. Signed
Networks in Social Media. In Proc. CHI, 2010.
- J. Leskovec, D. Huttenlocher,
J. Kleinberg. Predicting
Positive and Negative Links in Online Social Networks. In Proc. WWW,
2010.
- R. Guha, R. Kumar, P. Raghavan,
A. Tomkins. Propagation
of trust and distrust. In Proc. WWW, 2004.
- J. Kunegis, A. Lommatzsch, C. Bauckhage. The
Slashdot Zoo: Mining a social network with negative edges. In Proc.
WWW, 2009.
- S. Marvel, S. Strogatz, J. Kleinberg. Energy
landscape of social balance. Physical Review Letters, 103, 2009.
Cascading behavior in networks
Cascade capacity
- Section
19.7 of Chapter 19 of E&K.
- Complex Networks
Literature
- D. Centola. The
Spread of Behavior in an Online Social Network Experiment. Science,
2010.
- A. Montanari and A. Saberi. The
spread of innovations in social networks. PNAS 2010.
- E. Lieberman, C. Hauert, M.
A. Nowak. Evolutionary
Dynamics on Graphs. Nature 433: 312-316, 2005.
- N. Immorlica, J. Kleinberg,
M. Mahdian, T. Wexler. The
Role of Compatibility in the Diffusion of Technologies Through Social
Networks. In Proc. ACM EC, 2007.
- D. Centola, M. Macy, V. Eguiluz. Cascade
Dynamics of Multiplex Propagation. Physical Review A 374, 449-456,
2007.
- D. Watts. A
simple model of global cascades on random networks. Proc. Natl. Acad.
Sci., vol. 99 no. 9, 5766-5771, 2002.
- E. Berger. Dynamic
Monopolies of Constant Size. Journal of Combinatorial Theory Series B
83, 191-200, 2001.
- P. Dodds and D. J. Watts. Universal
Behavior in a Generalized Model of Contagion. Phyical
Review Letters, 2004.
- H. P. Young. The
Diffusion of Innovations in Social Networks. Santa Fe Institute
Working Paper 02-04-018.
- Economics/Sociolgy Literature
- S. Morris. Contagion.
Review of Economic Studies 67, 57-78, 2000.
- D. Centola, M. Macy. Complex
Contagions and the Weakness of Long Ties. American Journal of
Sociology, 2007.
- M. Jackson, L. Yariv. Diffusion
of Behavior and Equilibrium Properties in Network Games. American
Economic Review , Vol
97, No. 2, 2007.
- S. Bikhchandani, D. Hirshleifer, I. Welch. A
theory of fads, fashion, custom and cultural change as information
cascades. Journal of Political Economy. Vol. 100, pp. 992-1026, 1992.
- D. Strang, S. Soule. Diffusion
in organizations and social movements: From hybrid corn to poison pills.
Annual Review of Sociology, 24:265–290, 1998.
- A. V. Banerjee. A
Simple Model of Herd Behavior. The Quarterly Journal of Economics,
Vol. 107, No. 3, pp. 797-817, 1992.
- M. Granovetter. Threshold
models of collective behavior. American Journal of Sociology 83(6):1420-1443, 1978.
- T. Schelling. Micromotives and Macrobehavior.
Norton, 1978.
Epidemics on networks
- Chapter
21 of E&K.
- D. Romero, B. Meeder, J. Kleinberg. Differences
in the Mechanics of Information Diffusion Across Topics: Idioms, Political
Hashtags, and Complex Contagion on Twitter.
In Proc. WWW, 2011.
- J. Ugander, L. Backstrom, C.
Marlow, J. Kleinberg. Structural
Diversity in Social Contagion. In Proc. National Academy of Sciences,
2012.
- D. Cosley, D. Huttenlocher, J.
Kleinberg, X. Lan, S. Suri. Sequential
Influence Models in Social Networks. In Proc. ICWSM, 2010.
- S. Myers, C.
Zhu, J. Leskovec. Information
diffusion and external influence in Networks. In Proc. KDD, 2012.
- L. Backstrom, D. Huttenlocher,
J. Kleinberg, X. Lan. Group
Formation in Large Social Networks: Membership, Growth, and Evolution.
In Proc. KDD, 2006.
- M. Miller, C. Sathi, D. Wiesenthal, J. Leskovec,
C. Potts. Sentiment
Flow Through Hyperlink Networks. In Proc. ICWSM, 2011.
- A. Ganesh , L. Massoulie , D. Towsley. The
effect of network topology on the spread of epidemics. In IEEE
INFOCOM, 2005.
- S. Myers, J. Leskovec. Clash
of the Contagions: Cooperation and Competition in Information Diffusion.
In Proc. ICDM 2012.
Diffusion in the blogosphere
- H. Kwak, C. Lee, H. Park, S. Moon. What
is Twitter, a social network or a news media? In Proc. WWW, 2010. See
also slides
in slidshare.
- M. Cha, H. Haddadi, F. Benevenuto and
K. Gummadi Measuring
User Influence in Twitter: The Million Follower
Fallacy In ICWSM 2010.
- E. Adar, L. Adamic. Tracking
information epidemics in blogspace. In Proc.
Web intelligence, 2005.
- D. Gruhl, R. Guha, D. Liben-Nowell, A. Tomkins. Information
Diffusion through Blogspace. In Proc.
International WWW Conference, 2004.
- M. Goetz, J. Leskovec, M. Mcglohon, C. Faloutsos. Modeling
blog dynamics. In AAAI Conference on Weblogs and Social Media (ICWSM),
2009.
Influence Maximization
- D. Kempe, J. Kleinberg, E. Tardos.
Maximizing
the Spread of Influence through a Social Network KDD 2003.
- Y. Singer. How
to Win Friends and Influence People, Truthfully: Influence Maximization
Mechanisms for Social Networks WSDM 2012.
- E. Bakshy, J. Hofman, W. Mason
and D. Watts. Everyone’s
an Influencer: Quantifying Influence on Twitter WSDM 2012.
- A. Goyal, W. Lu, L. S.V. Lakshmanan.
SIMPATH:
An Efficient Algorithm for Influence Maximization under the Linear
Threshold Model In Proc. ICDM, 2011.
- M. Richardson,
P. Domingos. Mining
Knowledge-Sharing Sites for Viral Marketing. In Proc. KDD, 2002.
- M. Richardson,
P. Domingos. Mining
the Network Value of Customers. In Proc. KDD, 2001.
The small-world phenomenon
Decentralized Search
Navigation in social networks: algorithms and
models
- Section 20.5 of
E&K
- D.
Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social
networks. Proc. Natl. Acad. Sci., 102, 2005.
- L.
A. Adamic, E. Adar. How to search a social
network. Social networks, 27 3, 187-203, 2005.
- L.
A. Adamic, R. M. Lukose,
A. R. Puniyani, B. A. Huberman.
Search in Power-Law Networks. Phys. Rev. E, 64 46135, 2001.
- D.
J. Watts, P. S. Dodds, M. E. J. Newman. Identity
and Search in Social Networks. Science, 296, 1302-1305, 2002.
- O’zgur Simsek and David
Jensen. Navigating networks by using homophily
and degree. Proc. Natl. Acad. Sci. USA, 105(35):12758-12762,
Sept 2008.
- A.
Clauset and C. Moore. How Do Networks Become
Navigable? arXiv:cond-mat/0309415v2,
2003.
- O.
Sandberg and I. Clarke. The Evolution of Navigable Small-World Networks.
arxiv cs.DS/0607025,
2006.
Structure of the WWW
Strong and Weak Ties, and Community structure
- Chapter
3 of E&K.
- M. Granovetter. The
strength of weak ties. American Journal of Sociology, 78(6):1360-1380, 1973.
- J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.L. Barabasi. Structure
and tie strengths in mobile communication networks. PNAS, 2007.
- C. Marlow, L.
Byron, T. Lento, I. Rosenn. Maintained
relationships on Facebook. 2009.
- B.A. Huberman, D.M. Romero, F. Wu. Social
networks that matter: Twitter under the microscope. First Monday,
14(1), 2009.
- L. Backstrom, D. Huttenlocher,
J. Kleinberg, X. Lan. Group
Formation in Large Social Networks: Membership, Growth, and Evolution.
In Proc. KDD, 2006.
- P.S. Bearman, J. Moody. Suicide
and Friendships Among American Adolescents. Am J Public Health, 94(1):
89-95, 2004.
- R. Burt. Structural
Holes versus Network Closure as Social Capital. Chapter in Social
Capital: Theory and Research, 2001.
- R. Burt. Structural
Holes and Good Ideas. American Journal of Sociology, Vol. 110, No. 2
2004.
- M. Girvan and
M.E.J. Newman. Community
structure in social and biological networks. Proc. Natl. Acad. Sci.
99, 8271-8276, 2002.
- M.E.J. Newman,
M. Girvan. Finding
and evaluating community structure in networks. Phys. Rev. E 69,
026113, 2004.
- U. Brandes. A
faster algorithm for betweenness centrality.
Journal of Mathematical Sociology, 2001.
Clustering and communities
Power Laws
Power Laws, Preferential Attachment and The Long Tail