Elements of Network Science: CptS580-04 / EE 582-03

---

Resources: Papers

Here I will maintain an extended, topically-organized list of papers/references around the course material.

---

Graph Theory

• Chapter 2 of Easley and Kleinberg.
• barabasi-chapter2.pdf.

Random graphs

• Diestel, Graph Theory, Chapter 11
• barabasi-chapter3.pdf.

Spectral Analysis

• U. Brandes and T. Erlebach (Eds.), Network Analysis: Chapter 14 (Spectral Analysis).
• Dan Speilman’s class on Spectral Graph Theory (Yale), (Lectures 1 and 2).

Centrality

• U. Brandes and T. Erlebach (Eds.), Network Analysis: Chapter 3 (Centrality Indices).
• Chapters 4 and 5 are also good references.

PageRank

• David Gleich's Lecture Notes.
• David Gleich’s 2015 SIAM Review article, PageRank Beyond the Web

Hubs and Authorities

• Chapter 14 of E&K.

Similarity

• Sec 7.12 and 13 of the book Networks, An Introduction, by Newman.
• Chapter 4 of E&K.
• ICDM 2014 tutorial on similarity by Koutra, Eliassi-Rad and Faloutsos.
• Message-Passing Algorithms for Sparse Network Alignment. M. Bayati, D. Gleich, A. Saberi and Y. Wang. ACM TKDD vol 7, no 1, 2013.
• Network Similarity Decomposition (NSD): A Fast and Scalable Approach to Network Alignment.G. Kollias and A. Grama and S. Mohammadi. 2011.
• Fast parallel algorithms for graph similarity and matching.. G. Kollias, M. Sathe, O. Schenk and A. Grama. JPDC 74 (2014), 2400-2410.

Networks with positive and negative links

• Chapter 5 of E&K.
• K. Ciang, J. J. Whang, I. Dhillon. Scalable Clustering of Signed Networks Using Balance Normalized Cut. CIKM 2012.
• 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

• Chapter 19 of E&K.

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

• Chapter 20 of Easley and Kleinberg. Bibliography.
• D. Watts and S. Strogatz. Collective dynamics of ”small-world” networks. Nature, 393:440-442,1998.
• S. Milgram. The small-world problem. Psychology Today, 2:60-67, 1967.

Decentralized Search

• Sections 20.3 to 20.6 of Chapter 20 of E&K.
• J. Kleinberg. The small-world phenomenon: an algorithmic perspective. Proc 32nd ACM Symposium on Theory of Computing, pages 163-170, 2000.

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

• Chapter 13 of E&K.
• A. Broder et al. Graph structure in the Web. Computer Networks, 33, 2000.
• Mark Steyvers and Joshua B. Tenebaum. The large-scale structure of semantic networks:statistical analyses and a model of semantic growth. Cognitive Science, 29(1):41-78, 2005.
• Jakob Nielsen. The art of navigating through hypertext.. Communications of the ACM, 33(3):296-310, 1990.
• James Hendler et al. Web science: An interdisciplinary approach to understanding the Web. Communications of the ACM, 51(7):60-69, 2008.

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

• S. Fortunato. Community detection in graphs. Physics Reports 486 (2010).
• Ulrik von Luxburg. A Tutorial on Spectral Clustering. Stat Comput (2007) 17:395–416.
• R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. Trawling the Web for emerging cyber-communities. WWW 1999.
• R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. 20th Int’l Conference on Very Large Databases (VLDB), 1994.
• G. Palla, I. Derenyi, I Farkas and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814-818, 2005.

Temporal Networks

· P. Holme, J. Saramaki. Temporal Networks. Physics Reports 519 (2012), 97-125.

Power Laws

• Chapter 18 of E&K.
• A, Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009. See also the accompanying software at http://tuvalu.santafe.edu/~aaronc/powerlaws/.
• Zipf, Power-laws, and Pareto - a ranking tutorial by Lada Adamic,
  http://www.hpl.hp.com/research/idl/papers/ranking/ranking.html

Power Laws, Preferential Attachment and The Long Tail

• Sections 18.3 to 18.6 of E&K
• M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226-251, 2004.
• Chris Anderson. The long tail. Wired, October 2004.
• A.L Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
• H. Simon. On a class of skew distribution functions. Biometrika, 42:425-440, 1955.
• D. J. de S. Price. A general theory of bibliometric and other cumulative advantage processes. J. Amer. Soc. Inform. Sci. 27: 292-306, 1976.