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
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
Schedule / Syllabus (Subject to Change)
- Thu Sep 1: Introduction and Overview
- Mon Sep 5: No class (Labor Day)
- Thu Sep 8 & Mon Sep 12: Descriptive Analysis
- Thu Sep 15 & Mon Sep 19: Strong and Weak Ties
- Thu Sep 22 & Mon Sep 26: Networks in their Surrounding Contexts
- Thu Sep 29 & Mon Oct 3: Positive and Negative Relationships
- Thu Oct 6 & Mon Oct 10: Link Analysis and Web Search
- 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
- 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
- Thu Nov 10 & Mon Nov 14: Cascading Behavior in Networks
- Thu Nov 17 & Mon Nov 21: Epidemics
- Thu Nov 24: No class (Thanksgiving)
- Mon Nov 28: Meme-tracking and the Dynamics of the News Cycle
- Thu Dec 1: Mapping the World's Photos
- Mon Dec 5: Privacy in Information Networks
- Thu Dec 8: Project presentations
- Mon Dec 12: Project presentations
- Tue Dec 13: Regular classes end
- Thu Dec 15: Final projects are due