CS224W:

Social and Information Network Analysis

Autumn 2011

Handouts

Homeworks

Homework 1 (Due at 9:30am Oct. 13, 2011) [Homework 1][Solutions]
Homework 2 (Due at 9:30 Nov. 3, 2011) [Homework 2][Solutions]
Competition (Due at 9:30 Nov. 14, 2011) [Competition] [Data]

Recitations

[Recitation probability].

[Recitation algebra].

[Recitation SNAP slides] [Recitation SNAP website]

Lecture Notes & Papers

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

10/4: The Small World Phenomena [Slides]

Reading:

Chapter 20: The Small-World Phenomena

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.

10/6: Decentralized search in small-world and P2P networks [Slides]

Reading:

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.

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

J.A. Davis. Structural balance, mechanical solidarity, and interpersonal relations. American Journal of Sociology, 68:444?62, 1963.
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, 108(5) 1771-1776, 2011.
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.

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

Optional Readings:

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, pages 665鈥?74, 2008.
M. Burke and R. Kraut. Mopping up: Modeling wikipedia promotion decisions. In Proc. CSCW鈥?8: ACM Conference on Computer-Supported Cooperative Work, pages 27鈥?6, 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? WOSN 2010.

10/18: Network effects and Cascading behavior [Slides]

Reading:

Chapter 17: Network Effects

Optional Readings:

Demo: Schelling segregation model.
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/20: 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.
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.
L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. KDD, 2006.

10/25: Probabilistic Contagion in Graphs, Influence Maximization [Slides]

Reading:

Chapter 21: Epidemics

Optional Readings:

M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In Proc. KDD, 2002.
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.
E. Adar, L. Adamic. Tracking information epidemics in blogspace. In Proc. Wed intelligence, 2005.
M. Cha, H. Haddadi, F. Benevenuto, K.P. Gummadi. Measuring user influence in Twitter: The million follower fallacy. In Proc. ICWSM, 2010.
D. Romero, B. Meeder, J. Kleinberg. Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter. Proc. 20th International World Wide Web Conference, 2011.
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.
D. Centola. The Spread of Behavior in an Online Social Network Experiment. Science, 2010.

10/27: Influence Maximization and Outbreak Detection [Slides]

Reading:

D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. In Proc. KDD 2003.
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.
M. Richardson, P. Domingos. Mining the Network Value of Customers. In Proc. KDD, 2001.
N. Agarwal, H. Liu, L. Tang, P. Yu. Identifying the Influential Bloggers in a Community In Proc. WSDM, 2008.
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.
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.

11/01: Power-laws and Preferential attachment [Slides]

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.
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.

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.

11/08: Link Analysis: HITS and PageRank [Slides]

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.
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.
Alon Altman and Moshe Tennenholtz. Ranking Systems: The PageRank Axioms. In Proc. of ACM EC, 2005.

11/10: 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
C. Marlow, L. Byron, T. Lento, I. Rosenn. Maintained relationships on Facebook. 2009.
M. Girvan and M.E.J. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99, 8271-8276, 2002.
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/15: Network community detection: Modularity and Trawling [Slides]

Reading:

M.E.J. Newman. Modularity and community structure in networks., Proc. Natl. Acad. Sci., 2002.

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.
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: 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.

11/29: Kronecker graphs and the structure of large networks [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, 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.

12/01: Meme-tracking and Predicting information flows [Slides]

Reading:

J. Leskovec, L. Backstrom, J. Kleinberg Meme-tracking and the Dynamics of the News Cycle. In Proc. KDD 2009.
J. Yang, J. Leskovec. Modeling Information Diffusion in Implicit Networks. In Proc. ICDM, 2010.

Additional Readings:

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.
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.
Y. Jang, J. Leskovec. Patterns of Temporal Variation in Online Media In Proc. WSDM, 2011.
E. Sadikov, M. Medina, J. Leskovec, H. Garcia-Molina. Correcting for Missing Data in Information Cascades. In Proc. WSDM, 2011.
S. Asur, B. Huberman. Predicting the Future with Social Media. In Proc. WI-IAT, 2010.
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.
J. Ratkiewicz, M. Conover, M. Meiss, B. Gon?alves, S. Patil, A. Flammini, F. Menczer. Detecting and Tracking the Spread of Astroturf Memes in Microblog Streams. In Proc. WWW, 2010.

12/06: 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.
M. Gomez-Rodriguez, J. Leskovec, A. Krause. Inferring Networks of Diffusion and Influence. In Proc. KDD, 2010.

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/07: Networks: Review [Slides]

Readings:

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.