CS322:
(Social and Information) Network Analysis
Autumn 2009
Course outline
Problem Sets
11/13: Competition
10/01: Problem Set 1
10/01: Problem Set 2
- Due 29/08, in class [pdf]
- The data is: dictionary and A_Tale_of_Two_Cities
- Solutions can be found here
Lectures
9/22: Introduction
- Microsoft Instant Messenger network and 6 degrees of separation [slides]
- Recommended reading: Chapters 1: Overview and 2: Graphs of Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg.
9/24: Six degrees of separation
- Milgram's experiment and basic graph models [slides]
- Recommended reading: Chapter 20: The Small-World Phenomenon
9/29: Models of the small world, Decentralized search
- Expansion, diameter of random graphs, small world model, decentralized search [slides]
- Recommended reading: Chapter 20: The Small-World Phenomenon
10/01: Small world phenomena, Search in P2P networks, Strength of weak ties
- Empirical evaluations of the Small world phenomena, Search in P2P networks [slides]
- Triadic closure, Strength of weak ties, Structural holes [slides]
- Recommended reading: Chapter 3: Strong and Weak Ties
10/06: Graph structure of the web
- Bow-tie structure of the web and power-laws [slides]
- Recommended reading: Chapter 13: Structure of the Web
10/08: Power-laws and Preferential attachment
- Power-laws and Preferential attachment model [slides]
- Recommended reading: Chapter 18: Power Laws and Rich-Get-Richer Phenomena
10/13: Models of network evolution (1)
- Models microscopic network evolution [slides]
- Recommended reading: Microscopic Evolution of Social Networks by J. Leskovec, L. Backstrom, R. Kumar, A. Tomkins, KDD 2008
10/15: Models of network evolution (2)
- Models of macroscopic network evolution [slides]
- Recommended reading: Graph Evolution: Densification and Shrinking Diameters by J. Leskovec, J. Kleinberg, C. Faloutsos, TKDD 2007
10/20: Cascading behavior in networks
- Collective models of cascading behavior [slides]
- Recommended reading: Chapter 19: Cascading Behavior in Networks Cascading Behavior in Networks
10/22: Models of network cascades
- Decision based models of cascades [slides]
- Recommended reading: Chapter 19: Cascading Behavior in Networks
10/27: Cascades in viral marketing and the blogosphere
- Cascades on the blogosphere and viral marketing [slides]
- Recommended readings:
The Dynamics of Viral Marketing by J. Leskovec, L. Adamic, B. Huberman. TWEB 1(1), 2007,
Cascading Behavior in Large Blog Graphs by J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance, M. Hurst. SDM 2007,
Group Formation in Large Social Networks: Membership, Growth, and Evolution by L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan, KDD 2006.
10/29: Influence maximization in networks
- Maximizing influence in networks [slides]
- Recommended readings:
Cost-effective Outbreak Detection in Networks by J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance, KDD 2007
Maximizing the Spread of Influence through a Social Network by D. Kempe, J. Kleinberg, E. Tardos, KDD 2003.
11/3: Detecting cascades in networks
- Detecting cascades and outbreaks in networks [slides]
- Recommended readings:
Cost-effective Outbreak Detection in Networks by J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance, KDD 2007
11/5: Guest lecture by Lars Backstrom
11/10: Finding communities and clusters in networks
- Community detection in networks [slides]
- Recommended readings:
Community detection in graphs by S. Fortunato, Arxiv 2009.
11/12: Spectral clustering and large scale community structure in networks
- Spectral clustering and large scale community structure [slides]
- Recommended readings:
Tutorial on spectral clustering by U. von Luxburg, Arxiv 2009.
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters by J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney, Arxiv 2009.
11/17: Modularity and large scale community structure in networks
- Modularity and large scale community structure [slides]
- Recommended readings:
Tutorial on spectral clustering by U. von Luxburg, Arxiv 2009.
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters by J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney, Arxiv 2009.
11/19: Kronecker graphs
- Kronecker graphs [slides]
- Recommended readings:
Kronecker Graphs: An Approach to Modeling Networks by J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, Z. Ghahramani.
12/01: Link analysis for Web search
- Hubs and Authorities, PageRank [slides]
- Recommended readings:
Chapter 14: Link Analysis and Web Search.
12/03: Networks with positive and negative edges
- Signed networks, structural balance theory, status theory [slides]
- Recommended readings:
Chapter 5: Positive and negative relationships.
Chapters are from the new book Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg.
Dates for assignments
Due dates for assignemtns and other couser work:
- Assignment 1: Out 10/1. Due 10/8
- Reaction paper/project proposal. Due 10/15
- Assignment 2: Out 10/20. Due 10/29
- Project milestone: Due 11/12.
- Project poster presentation: 12/10 3-6pm. More info.
- Final writeup: Due 12/11 (No late days). More info.
See Course information for more info on assignments, projects, late days, and collaboration policy.