Article Source

• Title: Social and Information Network Analysis
• Authors: Jure Leskovec, Stanford University

---

Social and Information Network Analysis

Lecture notes and further reading

Introduction and the Bowtie Structure of the Web [Slides]

Reading:

• Chapter 1: Overview
• A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener. Graph structure in the Web. Computer Networks, 33, 2000.

Basic Network Properties and the Random Graph Model [Slides]

Reading:

• Chapter 2: Graphs

Optional Readings:

• P. Erdos, A. Renyi. On Random Graphs I. Publ. Math. Debrecen, 1959.
• P. Erdos, A. Renyi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Koezl., 1960.
• B. Bollobas. Random Graphs. Cambridge University Press.
• M.E.J. Newman, S. H. Strogatz and D.J. Watts. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118, 2001.
• R. Milo, N. Kashtan, S. Itzkovitz, M.E.J. Newman, U. Alon. On the uniform generation of random graphs with prescribed degree sequences. Arxiv, 2004.
• D. Ellis. The expansion of random regular graphs. Lecture notes from Algebraic methods in combinatorics, Cambridge University, 2011.
• S. Arora, S. Rao and U. Vazirani. Expander Flows, Geometric Embeddings and Graph Partitioning. In proc. STOC ‘04, 2004.

The Small World Phenomena [Slides]

Reading:

• Chapter 20: The Small-World Phenomena
• D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature 393:440-42, 1998.

Optional Readings:

• Demo: Erdos-Renyi random graph
• Demo: Watts-Strogatz small-world model
• S. Milgram. The small world problem. Psychology Today 1(1967).
• J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry 32, 1969.
• P. S. Dodds, R. Muhamad, D. J. Watts. An Experimental Study of Search in Global Social Networks. Science 301(2003), 827.
• J. Leskovec, E. Horvitz. Worldwide Buzz: Planetary-Scale Views on an Instant-Messaging Network. Proc. International WWW Conference, 2008.
• P. Killworth and H. Bernard, Reverse small world experiment. Social Networks 1, 1978.
• J. Kleinfeld. Could it be a Big World After All? The `Six Degrees of Separation’ Myth. Society, 2002.
• P. Killworth, C. McCarty, H.R. Bernard, M. House. The accuracy of small-world chains in social networks. Social Networks 28, 85-96, 2006.
• F. Menczer. Growing and Navigating the Small World Web by Local Content. Proc. Natl. Acad. Sci., 99(22): 14014-14019, 2002.
• L. Backstrom, P. Boldi, M. Rosa, J. Ugander, S. Vigna. Four Degrees of Separation. ACM Web Science Conference. 2012.
• J. Ugander, B. Karrer, L. Backstrom, C. Marlow. The Anatomy of the Facebook Social Graph. Arxiv 2012.

Decentralized search in small-world and P2P networks [Slides]

Reading:

• J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. ACM Symposium on Theory of Computing, 2000.

Optional Readings:

• M. E. J. Newman. Models of the Small World: A Review., J. Stat. Physics 2000.
• J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS), 2001.
• D. J. Watts, P. S. Dodds, M. E. J. Newman. Identity and Search in Social Networks. Science, 296, 1302-1305, 2002.
• L. A. Adamic, R. M. Lukose, A. R. Puniyani, B. A. Huberman. Search in Power-Law Networks. Phys. Rev. E, 64 46135, 2001.
• A. Clauset and C. Moore. How Do Networks Become Navigable? arXiv:cond-mat/0309415v2, 2003.
• L. A. Adamic, E. Adar. How to search a social network. Social networks, 27 3, 187-203, 2005.
• D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social networks. In Proc. Natl. Acad. Sci., 102, 2005.
• R. West, J. Leskovec. Human Wayfinding in Information Networks. In Proc. WWW, 2012.
• R. West, J. Leskovec. Automatic versus Human Navigation in Information Networks. In Proc. ICWSM, 2012.
• G. Manku, M. Naor, U. Wieder. Know thy Neighbor’s Neighbor: The Power of Lookahead in Randomized P2P Networks. Proc. STOC 2004.
• E-K Lua, J. Crowcroft, M. Pias, R. Sharma and S. Lim. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE Communications Surveys and Tutorials, 2005.
• O. Sandberg and I. Clarke. The Evolution of Navigable Small-World Networks. arxiv cs.DS/0607025, 2006.
• I. Clarke, O. Sandberg, B. Wiley, T. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System. International Workshop on Design Issues in Anonymity and Unobservability, 2000.
• I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. Proc. SIGCOMM, 2001.
• H. Zhang, A. Goel, R. Govindan. Using the small-world model to improve freenet performance. Computer Networks, 2004.

User Evaluations in Social Media [Slides]

Reading:

• J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks. In Proc. WWW, 2010.
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Effects of User Similarity in Social Media. In Proc. WSDM, 2012.

Optional Readings:

• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Discovering Value from Community Activity on Focused Question Answering Sites: A Case Study of Stack Overflow . In Proc. KDD, 2012.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Governance in Social Media: A case study of the Wikipedia promotion process. In Proc. ICWSM, 2010.
• C. Danescu-Niculescu-Mizil, G. Kossinets, J. Kleinberg, L. Lee. How opinions are received by online communities: A case study on Amazon.com helpfulness votes. In Proc. ACM WWW, 2009.
• R. Guha, R. Kumar, P. Raghavan, A. Tomkins. Propagation of trust and distrust. In Proc. WWW, 2004.
• L. A. Adamic, J. Zhang, E. Bakshy, and M. S. Ackerman. Knowledge sharing and yahoo answers: everyone knows something. In Proc. 17th International World Wide Web Conference, 2008.
• M. Burke and R. Kraut. Mopping up: Modeling wikipedia promotion decisions. In Proc. CSCW ‘08: ACM Conference on Computer-Supported Cooperative Work, 2008.
• D. Lauterbach, H. Truong, T. Shah, L. A. Adamic. Surfing a Web of Trust: Reputation and Reciprocity on CouchSurfing.com. International Symposium on Social Intelligence and Networking, 2009.
• C. Y. Teng, D. Lauterbach, L. A. Adamic. I rate you. You rate me. Should we do so publicly? In Proc. WOSN, 2010.
• L. Muchnik, S. Aral, S. J. Taylor. Social Influence Bias: A Randomized Experiment. Science, Vol. 341 no. 6146 pp. 647-651, 2013.

Networks with Signed Edges [Slides]

Reading:

• Chapter 5: Positive and negative relationships.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Signed Networks in Social Media. In Proc. CHI, 2010.

Optional Readings:

• D. Cartwright, F. Harary. Structural balance: A generalization of Heider’s theory. Psychological review, 1956.
• F. Heider. Attitudes and cognitive organization. Journal of Psychology. 21, 107-112, 1946.
• 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.
• T. Antal, P. Krapivsky, S. Redner. Dynamics of Social balance on Networks. Phys. Rev. E, 2005.
• S. Marvel, S. Strogatz, J. Kleinberg. Energy landscape of social balance. Physical Review Letters, 103, 2009.
• S. Marvel, J. Kleinberg, R. Kleinberg, S. Strogatz. Continuous-Time Model of Structural Balance. Proc. National Academy of Sciences, 2011.
• J.A. Davis. Structural balance, mechanical solidarity, and interpersonal relations. American Journal of Sociology, 68:444-62, 1963.
• P. Doreian, A. Mrvar. A partitioning approach to structural balance. Social. Networks 18, 1996.
• M. J. Brzozowski, T. Hogg, G. Szabo. Friends and foes: ideological social networking. In Proc. CHI, 2008.
• P. Doreian. Evolution of human signed networks. In Metodološki zvezki, 2004.
• C. J. Hsieh, K Chiang, and I. S. Dhillon. Low-Rank Modeling of Signed Networks. In Proc. KDD, 2012.
• K. Chiang, I. S. Dhillon, N. Natarajan, and A. Tewari. Exploiting Longer Walks for Link Prediction in Signed Network. In Proc. CIKM, 2011.
• G. Facchetti, G. Iacono, C Altafini. Computing global structural balance in large-scale signed social networks. In Proc. National Academy of Sciences, 2011.
• M. Szell, R. Lambiotte, S. Thurner. Multirelational Organization of Large-scale Social Networks in an Online World. Proc. National Academy of Sciences, 2010.
• J. Kunegis, A. Lommatzsch, C. Bauckhage. The Slashdot Zoo: Mining a social network with negative edges. In Proc. WWW, 2009.

Cascading Behavior: Decision Based Models of Cascades [Slides]

Reading:

• Chapter 19: Cascading Behavior in Networks

Optional Readings:

• S. Morris. Contagion. Review of Economic Studies 67, 57-78, 2000.
• 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.
• E. Berger. Dynamic Monopolies of Constant Size. Journal of Combinatorial Theory Series B 83, 191-200, 2001.
• 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.
• T. Schelling. Micromotives and Macrobehavior. Norton, 1978.
• D. Strang, S. Soule. Diffusion in organizations and social movements: From hybrid corn to poison pills. Annual Review of Sociology, 24:265–290, 1998.
• D. Watts. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci., vol. 99 no. 9, 5766-5771, 2002.
• H. P. Young. The Diffusion of Innovations in Social Networks. Santa Fe Institute Working Paper 02-04-018.
• P. Dodds and D. J. Watts. Universal Behavior in a Generalized Model of Contagion. Phyical Review Letters, 2004.
• E. Lieberman, C. Hauert, M. A. Nowak. Evolutionary Dynamics on Graphs. Nature 433: 312-316, 2005.
• D. Centola, M. Macy, V. Eguiluz. Cascade Dynamics of Multiplex Propagation. Physica A 374, 449-456, 2007.
• D. Centola. The Spread of Behavior in an Online Social Network Experiment. Science, 2010.
• M. Granovetter. Threshold models of collective behavior. American Journal of Sociology 83(6):1420-1443, 1978.
• A. V. Banerjee. A Simple Model of Herd Behavior. The Quarterly Journal of Economics, Vol. 107, No. 3, pp. 797-817, 1992.

Cascading Behavior: Probabilistic Models of Information Flow [Slides]

Reading:

• Chapter 21: Epidemics
• 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. WWWW, 2011.
• S. Myers, J. Leskovec. Clash of the Contagions: Cooperation and Competition in Information Diffusion. In Proc. ICDM 2012.

Optional Readings:

• S. Myers, C. Zhu, J. Leskovec. Information Diffusion and External Influence in Networks. In Proc. KDD, 2012.
• A. Goyal, F. Bonchi, L.V.S. Lakshmanan. Learning influence probabilities in social networks. In Proc. WSDM, 2010.
• D. Cosley, D. Huttenlocher, J. Kleinberg, X. Lan, S. Suri.Sequential Influence Models in Social Networks. In Proc. ICWSM, 2010.
• J. Leskovec, A. Singh, J. Kleinberg. Patterns of Influence in a Recommendation Network In Proc PAKDD, 2006.
• L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. KDD, 2006.
• E. Adar, L. Adamic. Tracking information epidemics in blogspace. In Proc. Wed intelligence, 2005.
• J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance, M. Hurst. Cascading Behavior in Large Blog Graphs. In Proc. SIAM International Conference on Data Mining, 2007.
• 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.
• M. Miller, C. Sathi, D. Wiesenthal, J. Leskovec, C. Potts. Sentiment Flow Through Hyperlink Networks. In Proc. ICWSM, 2011.
• J. Ugander, L. Backstrom, C. Marlow, J. Kleinberg. Structural Diversity in Social Contagion. In Proc. National Academy of Sciences, 2012.

Influence Maximization [Slides] [Handout]

Reading:

• D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. In Proc. KDD 2003.

Optional Readings:

• 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.
• S. Hill, F. Provost, C. Volinsky. Network-Based Marketing: Identifying Likely Adopters via Consumer Networks. Statistical Sciece, 2006.
• J. Leskovec, L. Adamic, B. Huberman. The Dynamics of Viral Marketing. TWEB, 2007.
• E. Bakshy, J. M. Hofman, W. A. Mason, and D. J. Watts, Everyone’s an influencer: quantifying influence on twitter. In Proc. WSDM, 2011.
• S. Aral, L. Muchnik, A. Sundararajan. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. In Proc. National Academy of Sciences, 2009.
• A. Goyal, W. Lu, L. S.V. Lakshmanan. SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In Proc. ICDM, 2011.
• W. Chen, Y. Wang, S. Yang. Efficient Influence Maximization in Social Networks. In Proc. KDD, 2009.
• W. Chen, Y. Yuan, L. Zhang. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In Proc. ICDM, 2010.
• C. Lerman, R. Ghosh. Information Contagion: Empirical Study of the Spread of News on Digg and Twitter Social Networks. In Proc. ICWSM, 2010.
• Y. Singer. How to win friends and influence people, truthfully: Influence maximization mechanisms for social networks. In Proc. WSDM, 2012.
• A. Gionis, E. Terzi, P. Tsaparas. Opinion maximization in social networks. In Proc. SDM, 2013.

Outbreak Detection [Slides]

Reading:

• J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance. Cost-effective Outbreak Detection in Networks. In Proc. KDD, 2007.

Optional Readings:

• E. Mossel and S. Roch. On the Submodularity of Influence in Social Networks. In Proc. STOC, 2007.
• N. Agarwal, H. Liu, L. Tang, P. Yu. Identifying the Influential Bloggers in a Community In Proc. WSDM, 2008.
• A. Krause, J. Leskovec, C. Guestrin, J. VanBriesen, C. Faloutsos. Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks. Journal of Water Resources Planning and Management, 2008.
• A. Krause, C. Guestrin, A Note on the Budgeted Maximization on Submodular Functions. Technical report, Carnegie Mellon University, no. CMU-CALD-05-103, 2005.
• A. Ostfeld et al. The Battle of the Water Sensor Networks (BWSN): A Design Challenge for Engineers and Algorithms. Journal of Water Resources Planning and Management, 2009.
• M. Cha, H. Haddadi, F. Benevenuto, K.P. Gummadi. Measuring user influence in Twitter: The million follower fallacy. In Proc. ICWSM, 2010.
• A. Goyal, W. Lu, L. V.S. Lakshmanan. Celf++: optimizing the greedy algorithm for influence maximization in social networks. In Proc. WWW, 2011.
• R. Pastor-Satorras, A. Vespignani. Immunization of complex networks. Physical Review E, 2002.
• T. Lappas, E. Terzi, D. Gunopoulos, H. Mannila. Finding Effectors in Social Networks. In Proc. KDD, 2010.

Power-laws and Preferential attachment [Slides] [Handout]

Reading:

• Chapter 18: Power Laws and Rich-Get-Richer Phenomena

Optional Readings:

• M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
• A. Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009.
• M.E.J. Newman. Power laws, Pareto distributions and Zipf’s law. Contemporary Physics 46(5), 323-351, 2005.
• M. Faloutsos, P. Faloutsos, C. Faloutsos. On Power-Law Relationships of the Internet Topology. In Proc. SIGCOMM, 1999.
• A.L Barabasi, R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
• B.A. Huberman, L. A. Adamic. Growth dynamics of the World-Wide Web. Nature, 399, 1999.
• H.A. 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.
• A.L. Barabasi, R. Albert, H. Jeong. Mean-field theory for scale-free random networks. Physica A 272 173-187, 1999.
• R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. Stochastic models for the Web graph. In Proc. FOCS 2000.
• W. Aiello, F. Chung, L. Lu. Random evolution of massive graphs. Handbook of Massive Data Sets, Kluwer, pages 97-122, 2002.
• B. Bollobas, C. Borgs, J. Chayes, O. Riordan. Directed scale-free graphs. In Proc. SODA 2003.
• R. Kleinberg, J. Kleinberg. Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs. In Proc. SODA, 2005.
• A. Fabrikant, E. Koutsoupias, C. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. In Proc. ICALP, 2002.
• N. Berger, C. Borgs, J. Chayes, R. D’Souza, R. Kleinberg. Competition-Induced Preferential Attachment. In Proc. ICALP 2004.
• M. Molloy and B. Reed. A Critical Point for Random Graphs with a Given Degree Sequence. Random Structures and Algorithms 6, 161-180, 1995.
• J. Carlson and J. Doyle. Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems. Physical Review E 60:2, 1999.
• M.E.J. Newman. The first-mover advantage in scientific publication. European Physics Letters 86, 68001, 2009.
• S. Redner. Citation statistics from 110 years of Physical Review. Physics Today 58, 49-54, 2005.
• S. Goel, A. Broder, E. Gabrilovich, B. Pang. Anatomy of the Long Tail: Ordinary People with Extraordinary Tastes. In Proc. WSDM, 2010.
• D. Pennock, G. Flake, S. Lawrence, E. Glover, C. Lee Giles. Winners don’t take all: Characterizing the competition for links on the web. PNAS 99(8), 2002.

Models of evolving networks [Slides]

Reading:

• J. Leskovec, L. Backstrom, R. Kumar, A. Tomkins. Microscopic Evolution of Social Networks. In Proc. KDD 2008.

Optional Readings:

• J. Leskovec, J. Kleinberg, C. Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM TKDD, 2007.
• R. Kumar, J. Novak, A. Tomkins. Structure and evolution of online social networks. In Proc. KDD, 2006.
• A.L. Barabasi, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, T. Vicsek. Evolution of the social network of scientific collaborations. Physica A: Statistical, 2002.
• G. Kossinets, D.J. Watts. Empirical Analysis of an Evolving Social Network. Science, 2006.
• D. Fetterly, M. Manasse, M. Najork, J.L. Wiener. A large-scale study of the evolution of web pages. In Proc. WWW, 2003.
• A. Ntoulas, J. Cho, C. Olston. What’s new on the web? The evolution of the web from a search engine perspective. In Proc. WWW, 2004.
• A.L. Barabasi. The origin of bursts and heavy tails in human dynamics. Nature 435, 207-211, 2005.
• J. Kleinberg. Bursty and Hierarchical Structure in Streams. In Proc. KDD, 2002.
• R. Kumar, J. Novak, P. Raghavan, A. Tomkins. On the bursty evolution of Blogspace. In Proc. WWW, 2003.
• M. Dubinko, R. Kumar, J. Magnani, J. Novak, P. Raghavan, A. Tomkins. Visualizing Tags over Time. In Proc. WWW, 2006.
• S. Lattanzi, D. Sivakumar. Affiliation Networks. In Proc. STOC, 2009.

Kronecker graphs [Slides]

Reading:

• J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, Z. Ghahramani. Kronecker Graphs: An approach to modeling networks. Journal of Machine Learning Research (JMLR) 11(Feb):985-1042, 2010.

Additional readings:

• J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos. Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication. European Conference on Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD), 2005.
• M. Kim, J. Leskovec.Multiplicative attribute graph model of real-world networks. Internet Mathematics, 2012.
• C. Seshadhri, A. Pinar and T. G. Kolda. An In-Depth Analysis of Stochastic Kronecker Graphs. Journal of the ACM, 2013.
• D. Chakrabarti, Y. Zhan and C. Faloutsos. R-MAT: A Recursive Model for Graph Mining. SIAM Data Mining, 2004.
• J. Leskovec, C. Faloutsos. Scalable Modeling of Real Graphs using Kronecker Multiplication. International Conference on Machine Learning (ICML), 2007.
• M. Kim, J. Leskovec.Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model. In Proc. UAI, 2011.
• M. Kim, J. Leskovec.Latent Multi-group Membership Graph Model. In Proc. ICML, 2012.
• M. Mahdian, Y. Xu. Stochastic Kronecker Graphs. 5th Workshop on Algorithms and Models for the Web Graph (WAW), 2007.
• G. Palla, L. Lovasz, T. Vicsek. Multifractal Network Generator. PNAS, 2010.
• S. Moreno, S. Kirshner, J. Neville, S.V.N. Vishwanathan. Tied Kronecker Product Graph Models to Capture Variance in Network Populations. In Proceedings of the 48th Annual Allerton Conference on Communications, Controland Computing, 2010.
• E. Bodine, B. Hassibi, A. Wierman. Distance-dependent Kronecker Graphs for Modeling Social Networks. IEEE THEMES, 2010.
• A. Pinar, C. Seshadhri and T. G. Kolda. The Similarity between Stochastic Kronecker and Chung-Lu Graph Models. In Proc. SDM, 2012.
• H. Yun, S. V. N. Vishwanathan. Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs. In Proc. AISTATS, 2012.
• M. Kim, J. Leskovec.The Network Completion Problem: Inferring Missing Nodes and Edges in Networks. In Proc. SDM, 2011.

Link Analysis: HITS and PageRank [Slides][Handout]

Reading:

• Chapter 14: Link Analysis and Web Search.

Optional Readings:

• S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998.
• J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.
• P. Berkhin. A Survey of PageRank Computing. Internet Mathematics, 2005.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Mining the link structure of the World Wide Web. IEEE Computer, August 1999.
• A. Arasu, J. Cho, H. Garcia-Molina, A. Paepcke, S. Raghavan. Searching the Web. ACM Transactions on Internet Technology 1(1): 2-43, 2001.
• A. Borodin, J. S. Rosenthal, G. O. Roberts, P. Tsaparas,Finding Authorities and Hubs From Link Structures on the World Wide Web. 10th International World Wide Web Conference, May 2001.
• D. Achlioptas, A. Fiat, A. Karlin, F. McSherry. Web Search via Hub Synthesis. 42nd IEEE Symposium on Foundations of Computer Science, p.611-618, 2001.
• D. Rafiei, A. Mendelzon. What is this Page Known for? Computing Web Page Reputations. Proc. WWW Conference, 2000.
• P. Domingos, M. Richardson. The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank. In Proc. NIPS, 2002.
• T. H. Haveliwala. Topic-Sensitive PageRank. 11th International World Wide Web Conference, 2002.
• A. Altman, M. Tennenholtz. Ranking Systems: The PageRank Axioms. In Proc. of ACM EC, 2005.
• Z. Gyongyi, H. Garcia-Molina, J. Pedersen. Combating Web Spam with TrustRank. In Proc. of VLDB, 2004.
• Z. Gyongyi, P. Berkhin, H. Garcia-Molina, J. Pedersen. Link Spam Detection Based on Mass Estimation. In Proc. of VLDB, 2006.
• A. Borodin, G. O. Roberts, J. S. Rosenthal, P Tsaparas. Link Analysis Ranking: Algorithms, Theory, and Experiments. ACM TOIT, 2005.
• A. Ntoulas, J. Cho, C. Olston. What’s New on the Web? The Evolution of the Web from a Search Engine Perspective. In Proc. WWW, 2004.
• M. A. Najork. Comparing the effectiveness of HITS and SALSA. In Proc. CIKM, 2007.
• B. Bahmani, A. Chowdhury, A. Goel. Fast Incremental and Personalized PageRank. In Proc. of VLDB, 2010.

Strength of weak ties and Community structure in networks [Slides]

Reading:

• Chapter 3: Strong and Weak Ties.

Optional Readings:

• 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
• 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. Modularity and community structure in networks., Proc. Natl. Acad. Sci., 2002.
• 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. Chapeter in Social Capital: Theory and Research, 2001.
• R. Burt. Structural Holes and Good Ideas. American Journal of Sociology, Vol. 110, No. 2 2004.
• G. Flake, S. Lawrence, C.L. Giles, F. Coetzee. Self-Organization and Identification of Web Communities. IEEE Computer, 35:3, 2002.
• G. Flake, K. Tsioutsiouliklis, R.E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Technical Report 2002-06, NEC, Princeton, NJ, 2002.
• S. Fortunato Community detection in graphs, Arxiv 2009.
• A. Clauset, M.E.J. Newman, C. Moore. Finding community structure in very large networks. Phys. Rev. E 70, 066111, 2004
• 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.
• J. Reichardt, S. Bornholdt. Statistical Mechanics of Community Detection., Phys. Rev. E 74 016110, 2006.
• S. Fortunato, S. Barthelemy. Resolution limit in community detection. Proc. Natl. Acad. Sci., 2007.
• U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, D. Wagner. On Modularity Clustering. IEEE TKDE, 2007.

Network community detection: Modularity optimization and Spectral Clustering [Slides][Handout]

Reading:

A. Rajaraman, J. Ullman, J. Leskovec. Chapter 10.4 of Mining Massive Datasets. 2013.

Additional readings:

• J. Shi, J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions On Pattern Analysis And Machine Intelligence, vol. 22, no. 8, 2000.
• R. Kannan, S. Vempala, A. Vetta. On clusterings: Good, bad and spectral. Journal of the ACM, 51(3):497-515, 2004.
• M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 1973.
• A. Pothen, H.D. Simon, K.P. Liou. Partitioning sparse matrices with egenvectors of graph. SIAM Journal of Matrix Anal. Appl., 11:430–452, 1990.
• L. Hagen, A.B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992.
• A. Ng, M. Jordan, Y. Weiss. On spectral clustering: Analysis and an algorithm. NIPS, 2001.
• U. von Luxburg. Tutorial on spectral clustering. Arxiv 2009.
• S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web. In Proc. VLDB, 2001.

Overlapping communities in networks [Slides]

Reading:

• G. Palla, I. Derenyi, I. Farkas, T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814-818, 2005.

Additional readings:

• E. Tomita, A. Tanaka, H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, Volume 363, Issue 1, 2006.
• G. Palla, A.L. Barabasi, T. Vicsek. Quantifying social group evolution. Nature 446, 664-667, 2007.
• J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Statistical Properties of Community Structure in Large Social and Information Networks. In Proc. WWW, 2008.
• J. Leskovec, K. Lang, M. Mahoney. Empirical Comparison of Algorithms for Network Community Detection. In Proc. WWW, 2010.
• J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics, 2009.
• G. Karypis, V. Kumar. Multilevel k-way Partitioning Scheme for Irregular Graphs. J. Parallel Distrib. Comput, 48(1): 96-129, 1998.
• I. Dhillon, Y. Guan, and B, Kulis. A Fast Kernel-based Multilevel Algorithm for Graph Clustering. In Proc. KDD, 2005.
• R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. In Proc. FOCS, 2006.
• T. Leighton, S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 1999.

Link Prediction and Network Inference [Slides]

Readings:

• L. Backstrom, J. Leskovec. Supervised Random Walks: Predicting and Recommending Links in Social Networks. In Proc. WSDM, 2011.

Additional readings:

• D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. CIKM, 2003.
• S. A. Myers, J. Leskovec. On the Convexity of Latent Social Network Inference. Neural Information Processing Systems (NIPS), 2010.
• M. Gomez-Rodriguez, D. Balduzzi, B. Schoelkopf. Uncovering the Temporal Dynamics of Diffusion Networks. In Proc. ICML 2011.
• A. Clauset, C. Moore, M.E.J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 2008.
• M. Kim, J. Leskovec. The Network Completion Problem: Inferring Missing Nodes and Edges in Networks. In Proc. SDM, 2010.
• F. Chierichetti, J. Kleinberg, D. Liben-Nowell. Reconstructing Patterns of Information Diffusion from Incomplete Observations. Neural Information Processing Systems (NIPS), 2011.
• B. Taskar, M.F. Wong, P. Abbeel, D. Koller. Link prediction in relational data. Neural Information Processing Systems (NIPS), 2006.
• P. D’haeseleer, S. Liang2, R. Somogyi. Genetic network inference: from co-expression clustering to reverse engineering. Bioinformatics, vol. 16, 2000.

Biological networks [Slides][Handout]

Readings:

• S.D. Ghiassian, J. Menche, A-L. Barabási. A DIseAse MOdule Detection (DIAMOnD) Algorithm Derived from a Systematic Analysis of Connectivity Patterns of Disease Proteins in the Human Interactome. PLoS Computational Biology, 2015.
• A-L. Barabási, N. Gulbahce, J. Loscalzo. Network Medicine: a Network-Based Approach to Human Disease. Nature Reviews Genetics, 2011.

Additional readings:

• S.D. Himmelstein, S.E. Baranzini. Heterogeneous Network Edge Prediction: a Data Integration Approach to Prioritize Disease-Associated Genes. PLoS Computational Biology, 2015.
• M. Costanzo, et al. The Genetic Landscape of a Cell. Science, 2010.
• A. Baryshnikova. Systematic Functional Annotation and Visualization of Biological Networks. Cell Systems, 2016.
• J.X. Hu, C.E. Thomas, S. Brunak. Network Biology Concepts in Complex Disease Comorbidities. Nature Reviews Genetics, 2016.
• J. Menche, et al. Uncovering Disease-Disease Relationships Through the Incomplete Interactome. Science, 2015.
• A.B. Jensen, et al. Temporal Disease Trajectories Condensed from Population-Wide Registry Data Covering 6.2 Million Patients. Nature Communications, 2014.
• S. Mostafavi, et al. GeneMANIA: a Real-Time Multiple Association Network Integration Algorithm for Predicting Gene Function. Genome Biology, 2008.
• M. Hofree, et al. Network-Based Stratification of Tumor Mutations. Nature Methods, 2013.
• H. Yu, et al. High-Quality Binary Protein Interaction Map of the Yeast Interactome Network. Science, 2008.
• X. Zhou, et al. Human Symptoms-Disease Network. Nature Communications, 2014.
• A. Mazza, K. Klockmeier, E. Wanker, R. Sharan. An Integer Programming Framework for Inferring Disease Complexes from Network Data. Bioinformatics, 2016.
• D.M. Leiserson, et al. Pan-Cancer Network Analysis Identifies Combinations of Rare Somatic Mutations Across Pathways and Protein Complexes. Nature Genetics, 2015.
• C.S. Greene, et al. Understanding Multicellular Function and Disease with Human Tissue-Specific Networks. Nature Genetics, 2015.
• M. Kramer, et al. Inferring Gene Ontologies from Pairwise Similarity Data. Bioinformatics, 2014.
• Y. Hulovatyy, H. Chen, T. Milenkovic. Exploring the Structure and Function of Temporal Networks with Dynamic Graphlets. Bioinformatics, 2015.
• S. Lee, S. Kong, E.P. Xing. A Network-Driven Approach for Genome-Wide Association Mapping. Bioinformatics, 2016.
• Y. Li, et al. Expansion of Biological Pathways Based on Evolutionary Inference. Cell, 2014.
• E. Guney, et al. Network-Based in Silico Drug Efficacy Screening. Nature Communications, 2016.

Networks: Two Fun Topics [Slides]

Readings:

• C. Danescu-Niculescu-Mizil, R. West, D. Jurafsky, J. Leskovec, C. Potts. No Country for Old Members: User lifecycle and linguistic change in online communities ACM International Conference on World Wide Web (WWW), 2013
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Steering User Behavior With Badges. ACM International Conference on World Wide Web (WWW), 2013.
• J. Kleinberg. The convergence of social and technological networks. CACM, 2008.

Additional readings:

• D. Lazer et al. Life in the network: the coming age of computational social science. Science, 2009.
• L.-A. Barabasi. Linked: How Everything Is Connected to Everything Else and What It Means. Plume, 2003.
• N. Christakis, J.H. Fowler. Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives. Back Bay Books, 2011.
• D.J. Watts. Six Degrees: The Science of a Connected Age. W. W. Norton & Company, 2004.

Homeworks

• Homework 0 (Due at 11:59pm Oct. 6, 2016). Submission Template for HW0 [pdf

  tex]. Solutions: [PDF][Code].

• Homework 1 (Due at 11:59pm Oct. 13, 2016). Submission Template for HW1 [pdf | tex]. Solutions: [PDF].

• Homework 2 (Due at 11:59pm Oct. 27, 2016). Submission Template for HW2 [pdf

  tex] Solutions: [PDF].

• Homework 3 (Due at 11:59pm Nov. 10, 2016). Submission Template for HW3 [pdf

  tex]. Solutions [PDF].

• Homework 4 (Due at 11:59pm Dec. 1, 2016). Submission Template for HW4 [pdf

  tex]. Solutions [PDF].

Recitations

• Introduction to SNAP.PY: Friday, 9/30, 12:30-1:20pm in Huang 18
• Probability, Linear Algebra and Proof Techniques review: Monday, 10/03, 3:00-3:50pm in Gates B03