• Home
• Schedule
• Information
• Project
• Resources

Course outline

• Problem Sets
• Lectures
• Dates for assignments

Problem Sets

• Competition- here
• Problem Set 2 - PS2. The solution to PS2 can be found here.
• Problem Set 1 - PS1. The solution to PS1 can be found here.
• DataSet for Problem Set 1 can be found here
• Dataset for competition - here

Lectures

09/20: Introduction

• Introduction, Course logistics and Bowtie Structure of the Web. [Slides]
• Recommended reading: Chapters 1: Overview and 2: Graphs from Kleinberg&Easley

09/22: Six degrees of separation

• Six degrees of separation, the small world experiment. [Slides]
• Additional readings:
• 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. 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. S. Dodds, R. Muhamad, D. J. Watts. An Experimental Study of Search in Global Social Networks. Science 301(2003), 827.
• 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.
• J. Leskovec, E. Horvitz. Worldwide Buzz: Planetary-Scale Views on an Instant-Messaging Network. Proc. International WWW Conference, 2008.

09/27: Models of small-world networks

• Erdos-Renyi random graph, Models of the small world. [Slides]
• Chapter 20: The Small-World Phenomenon from Kleinberg&Easley.
• Demo: Erdos-Renyi random graph
• Demo: Watts-Strogatz small-world model
• Additional readings:
• D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature 393:440-42, 1998.
• J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. ACM Symposium on Theory of Computing, 2000.
• L. A. Adamic, R. M. Lukose, A. R. Puniyani, B. A. Huberman. Search in Power-Law Networks. Phys. Rev. E, 64 46135, 2001.
• J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS), 2001.
• A. Clauset and C. Moore. How Do Networks Become Navigable? arXiv:cond-mat/0309415v2, 2003.
• M. E. J. Newman. Models of the Small World: A Review., J. Stat. Physics 2000.

09/29: Decentralized search in small-world and P2P networks

• Decentralized search in Watts-Strogatz, Kleinberg's model, P2P networks. [Slides]
• Chapter 20: The Small-World Phenomenon from Kleinberg&Easley.
• Demo: Search in Kleinberg's small-world model
• Additional readings:
• D. J. Watts, P. S. Dodds, M. E. J. Newman. Identity and Search in Social Networks. Science, 296, 1302-1305, 2002.
• L. Adamic, B. Huberman. Information dynamics in a networked world. Lecture Notes in Physics, 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. Proc. Natl. Acad. Sci., 102, 2005.
• 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/4: Guest Lecture by Lars Backstrom, Facebook

• Geography on the Web [Slides]
• Additional readings:
• L. Backstrom, J. Kleinberg, R. Kumar, J. Novak. Spatial Variation in Search Engine Queries. In Proc. WWW, 2008.
• L. Backstrom, E. Sun, C. Marlow. Find Me If You Can: Improving Geographical Prediction with Social and Spatial Proximity. In Proc. WWW, 2010.
• D. Crandall, L. Backstrom, D. Huttenlocher, J. Kleinberg. Mapping the World's Photos. In Proc. WWW 2009
• M.C. Gonzalez, C.A. Hidalgo, A.L. Barabasi. Understanding individual human mobility patterns. Nature, 2008.
• T. Sakaki, M. Okazaki, Y. Matsuo. Earthquake shakes Twitter users: real-time event detection by social sensors. In Proc. WWW, 2010.
• M. C. Gonzalez, P. G. Lind, H. J. Hermann. System of Mobile Agents to Model Social Networks. Phys. Rev. Let., 2006.
• D. Brockmann, L. Hufnage, T. Geisel. The scaling laws of human travel. Nature, 2006.
• A. Kapoor, N. Eagle, E. Horvitz. People, Quakes, and Communications: Inferences from Call Dynamics about a Seismic Event and its Influences on a Population. AAAI Spring Symposium, 2010.
• C. Song, Z. Qu, N. Blumm, A.L. Barabasi. Limits of Predictability in Human Mobility. Science, 2010.
• N. Eagle, M. Macy, R. Claxton. Network Diversity and Economic Development. Science 328(5981), pp. 1029-1031, 2010.

10/6: Network effects and information cascades

• Network effects and information cascades [Slides]
• Chapter 16: Information cascades from Kleinberg&Easley.
• Chapter 17: Network Effects from Kleinberg&Easley.
• Demo: Schelling segregation model.
• Additional readings:
• 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.
• 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.
• P. Holme, M. E. J. Newman. Nonequilibrium phase transition in the coevolution of networks and opinions. arXiv:physics/0603023v3.

10/11: Cascading behavior in networks

• Network effects and information cascades [Slides]
• Chapter 19: Cascading Behavior in Networks from Kleinberg&Easley.
• Additional 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.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Governance in Social Media: A case study of the Wikipedia promotion process. In Proc. AAAI ICWSM, 2010.
• 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.

Project ideas and datasets

• Project ideas and datasets [Slides]
• Additional information on projects.

10/14: Empirical studies of diffusion in networks

• Diffusion and cascades in viral marketing and blogosphere [Slides]
• Chapter 21: Epidemics from Kleinberg&Easley.
• Demo: Virus on a network.
• Additional readings:
• 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.
• L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. KDD, 2006.
• J. Leskovec, A. Singh, J. Kleinberg. Patterns of Influence in a Recommendation Network In Proc PAKDD, 2006.
• J. Leskovec, L. Adamic, B. Huberman. The Dynamics of Viral Marketing. TWEB, 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.
• E. Adar, L. Zhang, L. A. Adamic, R. M. Lukose. Implicit Structure and the Dynamics of Blogspace. Workshop on the Weblogging Ecosystem, at the International WWW Conference, 2004.
• D. Liben-Nowell, J. Kleinberg. Tracing Information Flow on a Global Scale Using Internet Chain-Letter Data. Proc. National Academy of Sciences, 105(12):4633-4638, 2008.
• E. Sun, I. Rosenn, C. Marlow, T. Lento. Gesundheit! Modeling Contagion through Facebook News Feed. In Proc. AAAI ICWSM, 2009.
• D. Centola. The Spread of Behavior in an Online Social Network Experiment. Science, 2010.
• M. Cha, A. Mislove, K. P. Gummadi. A measurement-driven analysis of information propagation in the flickr social network. In Proc. WWW, 2008.
• H. Kwak, C. Lee, H. Park, S. Moon. What is Twitter, a social network or a news media? In Proc. WWW, 2010.

10/18: Influence maximization in networks

• Influnece maximization, greedy hill climbing, submodular functions [Slides]
• Additional readings:
• D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. In Proc. KDD 2003.
• M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In Proc. KDD, 2002.
• E. Mossel and S. Roch. On the Submodularity of Influence in Social Networks. In Proc. STOC, 2007.
• 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.
• A. Goyal, F. Bonchi, L.V.S. Lakshmanan. Learning influence probabilities in social networks. In Proc. WSDM, 2010.
• 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.

10/20: Outbreak detection in networks

• Outbreak detection in networks, lazy submodular function evaluation [Slides]
• Additional readings:
• J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance. Cost-effective Outbreak Detection in Networks. In Proc. KDD, 2007.
• E. Adar, L. Adamic. Tracking information epidemics in blogspace. In Proc. Wed intelligence, 2005.
• N. Agarwal, H. Liu, L. Tang, P. Yu. Identifying the Influential Bloggers in a Community In Proc. WSDM, 2008.
• M. Cha, H. Haddadi, F. Benevenuto, K.P. Gummadi. Measuring user influence in Twitter: The million follower fallacy. In Proc. ICWSM, 2010.
• 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. 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.

10/25: Power-laws and Preferential attachment

• Power-laws and Preferential attachment model [slides]
• Chapter 18: Power Laws and Rich-Get-Richer Phenomena from Kleinberg&Easley.
• Additional 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.
• 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.
• 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.

10/27: Models of evolving networks

• Models network evolution [slides]
• Additional readings:
• J. Leskovec, L. Backstrom, R. Kumar, A. Tomkins. Microscopic Evolution of Social Networks. In Proc. KDD 2008.
• 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.

11/01: Strength of weak ties and Community structure in networks

• Strong weak ties, Community structure and betweenness centrality [slides]
• Chapter 3: Strong and Weak Ties from Kleinberg&Easley.
• Additional 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
• 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.

11/03: Network community detection: Modularity

• Girvan-Newman, Modularity optimization [slides]
• Additional readings:
• 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.
• M.E.J. Newman. Modularity and community structure in networks., Proc. Natl. Acad. Sci., 2002.
• A. Clauset, M.E.J. Newman, C. Moore. Finding community structure in very large networks. Phys. Rev. E 70, 066111, 2004
• 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/08: Network community detection: Spectral graph partitioning

• Trawling, Spectral graph partitioning [slides]
• Additional readings:
• R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Trawling the web for emerging cyber-communities. In Proc. WWW, 1999.
• R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules. In Proc. VLDB, 1994.
• S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web. In Proc. VLDB, 2001.
• 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.

11/10: Community structure of large networks

• Clique percolation method, Network community profile [slides]
• Additional readings:
• 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.
• 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, A. Dasgupta, M. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics, 2009.
• J. Leskovec, K. Lang, M. Mahoney. Empirical Comparison of Algorithms for Network Community Detection. In Proc. WWW, 2010.
• 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.

11/15: Kronecker graphs and the structure of large networks

• Kronecker graphs [slides]
• Additional readings:
• 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.
• J. Leskovec, C. Faloutsos. Scalable Modeling of Real Graphs using Kronecker Multiplication. International Conference on Machine Learning (ICML), 2007.
• 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. Mahdian, Y. Xu. Stochastic Kronecker Graphs. 5th Workshop on Algorithms and Models for the Web Graph (WAW), 2007.
• M. Kim, J. Leskovec. Multiplicative Attribute Graph Model of Real-World Networks. 7th Workshop on Algorithms and Models for the Web Graph (WAW), 2010.
• 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.

11/17: Networks with positive and negative links

• Signed networks, structural balance theory, status theory [slides]
• Chapter 5: Positive and negative relationships.
• Additional readings:
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Signed Networks in Social Media. In Proc. CHI, 2010.
• R. Guha, R. Kumar, P. Raghavan, A. Tomkins. Propagation of trust and distrust. In Proc. WWW, 2004.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks. In Proc. WWW, 2010.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Governance in Social Media: A case study of the Wikipedia promotion process. In Proc. ICWSM, 2010.
• 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.
• M. Szell, R. Lambiotte, S. Thurner. Multirelational Organization of Large-scale Social Networks in an Online World. PNAS, 2010.
• 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.
• T. Antal, P. Krapivsky, S. Redner. Dynamics of Social balance on Networks. Phys. Rev. E, 2005.

11/29: Random walks

• PageRank, Hubs and Authorities, Superwised Random walks [slides]
• Chapter 14: Link Analysis and Web Search.
• Additional 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.
• 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.
• R. Lempel, S. Moran. The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect. In Proc. WWW, 2000.
• S. Vigna. Spectral ranking. (and slides), 2009.

12/01: Link prediction

• Link prediction, superwised random walks [slides]
• Additional readings:
• D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. CIKM, 2003.
• A. Clauset, C. Moore, M.E.J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 2008.
• L. Backstrom, J. Leskovec. Supervised Random Walks: Predicting and Recommending Links in Social Networks. In Proc. WSDM, 2011.

Chapters are from the new book Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg.

Tentative List of Topics

• 1: Introduction
• 2: Six degrees of separation
• 3: Models of the small world, Decentralized search
• 4: Small world phenomena, Search in P2P networks, Strength of weak ties
• 5: Graph structure of the web
• 6: Power-laws and Preferential attachment
• 7: Models of network evolution (1)
• 8: Models of network evolution (2)
• 9: Cascading behavior in networks
• 10: Models of network cascades
• 11: Cascades in viral marketing and the blogosphere
• 12: Influence maximization in networks
• 13: Detecting cascades in networks
• 14: Finding communities and clusters in networks
• 15: Spectral clustering and large scale community structure in networks
• 16: Modularity and large scale community structure in networks
• 17: Kronecker graphs
• 18: Link analysis for Web search
• 19: Networks with positive and negative edges

For more info see last year's version of the class.

Dates for assignments

Due dates for assignments and other course work:

Assignment/Work	Out on	Due on
Reaction Paper	--	October 6 11:59PM
Assignment #1	September 29	October 14 11:59PM
Project Proposal	--	October 20
Assignment #2	October 21	November 4
Assignment #3 / Competition	November 5	November 12 ; Midnight
Project Milestone	--	November 18
Project Poster Presentation	--	December 7 ; 3-6PM
Project Write-up	--	December 8 ; Midnight (NO LATE DAYS)

See Course information for more info on assignments, projects, late days, and collaboration policy.