Fall 2011 -- 01:198:442 -- Introduction to Network Science

Semester: Fall 2011

Course number: 01:198:442

Course title: Introduction to Network Science: Theory, Algorithms, and Applications

Credits: 4

Instructor: Tina Eliassi-Rad

Course website: here and in Sakai

Lecture: Mondays, Thursdays 12-1:20 in Hill 254

Recitation: Mondays 1:30-2:25 in Hill 250

Office hours: Mondays 2:30-3:30 in CBIM 08

Description

Recent advances in information technology have led to the emergence of a new interdisciplinary field, called network science, where the goal is to understand behavior in network representations of social, biological, physical, and technological phenomena. Such network representations are ubiquitous. For instance, the Internet is a global system of interconnected computer networks. The World Wide Web is an information network with Web pages linking to each other. Social networks like friendship networks are abound in social networking sites such as Facebook and LinkedIn. Last but not least, there are biological networks like protein-protein interaction networks or the food web, which represents predator-prey relationships between species within an ecosystem.

This course will cover basic concepts in complex network such as filling structural holes in social networks (or "how to get access to novel information, power, and freedom"), diffusing information in networks (or "how should we organize a revolt?"), and distinguishing between homophily and social influence (or "how to promote a idea: targeted outreach vs. viral marketing?"). Network theory, algorithms, and applications will be discussed. On the application-side, students will learn to apply concepts to a variety of real-world networks by using software tools.

Textbooks

(Required) David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
(Recommended) Mark Newman. Networks: An Introduction. Oxford University Press, 2010.

Prerequisite: 01:198:112, 01:198:205, and 01:198:206, or permission of instructor. Knowledge of Java, C, or Python.

The class requires an ability to deal with "abstract mathematical concepts." You need an introductory-level background in algorithms, probability, and linear algebra. You also need to know programming to perform data analysis. The specific programming language is mostly your choice.

Grading scheme

Class project (45%) -- involving an exploratory data analysis of a novel data set, or creation of a novel model for constructing a network, or design of a novel algorithm.
Three homework assignments (45%)
Class participation (10%)

Resources

Software, tools, and data

Schedule / Syllabus (Subject to Change)

Thu Sep 1: Introduction and Overview

Chapter 1 of Eric Kolaczyk: Statistical Analysis of Network Data. Springer, 2009.
Chapter 1 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.

Mon Sep 5: No class (Labor Day)

Thu Sep 8 & Mon Sep 12: Descriptive Analysis

C. T. Butts: Revisiting the Foundations of Network Analysis. Science, 325, 2009:414-416.
Chapter 2 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.
Chapter 2 of Matthew Jackson: Social and Economic Networks. Princeton University Press, 2008.

Thu Sep 15 & Mon Sep 19: Strong and Weak Ties

Chapter 3 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.

Thu Sep 22 & Mon Sep 26: Networks in their Surrounding Contexts

Chapter 4 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.

Thu Sep 29 & Mon Oct 3: Positive and Negative Relationships

Chapter 5 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.
Jure Leskovec, Daniel P. Huttenlocher, Jon M. Kleinberg: Predicting Positive and Negative Links in Online Social Networks. WWW 2010:641-650.

Thu Oct 6 & Mon Oct 10: Link Analysis and Web Search

Chapter 14 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.
H. Tong, C. Faloutsos, and J.-Y. Pan: Fast Random Walk with Restart and Its Applications. ICDM 2006:613-622.

Thu Oct 13 & Mon Oct 17: Network Classification

B. Gallagher, T. Eliassi-Rad: Leveraging Label-Independent Features for Classification in Sparsely Labeled Networks: An Empirical Study. Lecture Notes in Computer Science: Advances in Social Network Mining and Analysis, Springer, 2010 (extended version of a SNAKDD 2008 paper).
B. Gallagher, H. Tong, T. Eliassi-Rad, C. Faloutsos: Using Ghost Edges for Classification in Sparsely Labeled Networks. KDD 2008:256-264.
P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, T. Eliassi-Rad: Collective Classification in Network Data. AI Magazine, 29(3), 2008:93-106.

Thu Oct 20: User-Interest Classification in Social Networks (Guest Lecturer: Matt Muscari)

Mon Oct 24: Role Discovery

K. Henderson, B. Gallagher, L. Li, L. Akoglu, T. Eliassi-Rad, H. Tong, C. Faloutsos: It's Who You Know: Graph Mining Using Recursive Structural Features. KDD 2011.
K. Henderson, et al: Role Discovery. Technical Report, October 2011. (Visit the Sakai Resources Folder for the report.)

Thu Oct 27 & Mon Oct 31: Community Discovery

A. Clauset, M. E. J. Newman, C. Moore: Finding Community Structure in Very Large Networks. Phys. Rev. E 70, 066111, 2004.
D. Chakrabarti, S. Papadimitriou, D. Modha, C. Faloutsos: Fully Automatic Cross-Associations. KDD 2004.
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.
J. Leskovec, K. Lang, M. Mahoney: Empirical Comparison of Algorithms for Network Community Detection. WWW 2010:631-640.
Optional reading: S. Fortunato: Community Detection in Graphs, arXiv:0906.0612, 2009. (A dense survey of different approaches)

Thu Nov 3 & Mon Nov 7: Information Cascades & Network Effects

Chapter 16 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.
Chapter 17 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.

Thu Nov 10 & Mon Nov 14: Cascading Behavior in Networks

Chapter 19 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.

Thu Nov 17 & Mon Nov 21: Epidemics

Chapter 21 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.

Thu Nov 24: No class (Thanksgiving)

Mon Nov 28: Meme-tracking and the Dynamics of the News Cycle

Jure Leskovec, Lars Backstrom, Jon M. Kleinberg: Meme-tracking and the Dynamics of the News Cycle. KDD 2009: 497-506.

Thu Dec 1: Mapping the World's Photos

David J. Crandall, Lars Backstrom, Daniel P. Huttenlocher, Jon M. Kleinberg: Mapping the World's Photos. WWW 2009: 761-770.

Mon Dec 5: Privacy in Information Networks

Michael Hay, Kun Liu, Gerome Miklau, Jian Pei, and Evimaria Terzi: Privacy-aware Data Management in Information Networks. SIGMOD 2011 Tutorial.

Thu Dec 8: Project presentations

Mon Dec 12: Project presentations

Tue Dec 13: Regular classes end

Thu Dec 15: Final projects are due