CS224W:

Social and Information Network Analysis

Autumn 2016

Handouts

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

Lecture notes and further reading

Pointers to the slides will be posted here just before the start of the class.

09/27: 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.

09/29: 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.

10/04: 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.

10/06: 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.

10/11: 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.

10/13: 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.

10/18: 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.

10/20: 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 Inﬂuence 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.

10/25: 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 inﬂuencer: quantifying inﬂuence on twitter. In Proc. WSDM, 2011.
S. Aral, L. Muchnik, A. Sundararajan. Distinguishing inﬂuence-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 Efﬁcient Algorithm for Inﬂuence 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.

10/27: 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.

11/01: 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.

11/03: 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. Afﬁliation Networks. In Proc. STOC, 2009.

11/08: 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.

11/10: 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 eﬀectiveness of HITS and SALSA. In Proc. CIKM, 2007.
B. Bahmani, A. Chowdhury, A. Goel. Fast Incremental and Personalized PageRank. In Proc. of VLDB, 2010.

11/15: 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.

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

Reading:

Chapter 10.4

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.

11/29: 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.

12/01: 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.

12/06: 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.

12/08: 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.