Networks are everywhere. We can easily find network structure in many complex systems around us: our cells, brains, society, etc. The inherent generality of network approach flourished wide applications of network theory across diverse fields including biology, sociology, and epidemiology. The questions that we will address in the class are following:

why do networks matter? what are the fundamental theory to understand the structure and dynamics of networks? how has it been applied to other fields? What are the frontiers of the research?

We will explore key papers ranging from the fundamental theory to the various applications of network theory. This course will focus more on the round-table discussion between students than presentation. Students will work on research projects in groups and finish a paper at the end of the class.


Key ideas and concepts

Basic information

Time & Location
Informatics West 107 (note the room change!)
Tuesday & Thursday 4:00pm–5:15pm
First meeting: Jan. 10th, 2012
Yong-Yeol Ahn (YY)
Office: Informatics East Room 316
Phone: (812) 856 2920
Office hours: Tuesday & Thursday 1pm–2:30pm, or by appointment
(you can email me or use MeetMe:
All announcements will be sent through a mailing list (a Google group).
Readings (mostly scientific papers) will be assigned.
This course is open only to graduate students. There is no formal prerequisite but basic mathematical and programming skills will be needed.


This website contains all the information in the syllabus. You can simply print this website.


1/10 Introduction and Misc.

Further reading:
Small world
1/12 Required reading: Further reading: Shantanu

Small world / clustering / weak ties
1/17 Required reading: Further reading: Ian
Communities / clustering / weak ties
1/19 Required reading: Further reading: Ali
1/24 Required reading: Further reading: Exercise #1 (one week): download American college footbal network data from here. Load the network into memory and calculate the degree distribution, clustering coefficient, and average path length. Repeat it with WWW data from here. Huizi
Scale-free networks
1/26 Required reading: Further reading: Alex
Overlapping communities
1/31 Required reading: Further reading: Abhik
2/2 Required reading: Further reading: Shenshen
2/7 Required reading: Further reading: Lilian
Overlapping communities, line graph
2/9 Required reading: Further reading: Jaehong
Epidemic spreading
2/14 Required reading: Further reading: Varsha
2/16 Required reading: Further reading: Varsha
Project proposal paper due
2/21Project proposal presentations
Guest lectures
2/23 Guest lecture: Johan Bollen
2/28 Guest lecture: David Crandall, "Reconstructing the world from social photo-sharing websites"
3/1 Guest lecture: Apu Kapadia, "Privacy in Social Networks: From Drunk Tweeting to Anonymous Counseling"
Random graphs
3/6 Required reading: Further reading: YY
3/8 Required reading: Further reading: Lilian
3/13No class (spring recess)
3/15No class (spring recess)
Random walk and communities
3/20 Required reading: Further reading: Dimitar
Project progress report due
Epidemic spreading (immunization)
3/22 Required reading: Further readings: YY
Metabolic networks
3/27 Required Readings Further reading: Shantanu
Degree correlation
3/29 Required reading Further readings Ian
Protein-Protein interaction networks
4/3 Required reading: Further reading: Jaehong
Social contagion
4/5 Required reading: Further reading: Varsha
Project progress report due
4/10 Required readings: Further readings: Abhik
4/12 Required reading: Further readings: Dimitar
Geography and social connection
4/17 Required reading: Further readings: Shenshen
4/19 Required readings: YY
Final paper due
4/24Project presentation
4/26Project presentation



Performing a publishable research project (and publish) on network science.


The deliverables are:

Project proposal (Due: 2/21)

A two to four page document that contains

Proposal presentation (Due: 2/21)

We will follow the Ignite format. You can have 20 slides and each slide will auto-advance every 15 seconds. Therefore, you should submit the slides the day before the class. The presentation should contain:

Progress report #1 (3/22) and #2 (4/10)

The progress report will be a draft of the final paper. I can always discuss about the project with you independent of the progress report.

Final paper (5/3)

6-10 pages, two column. You can use a generic CS conference format or other reasonable journal/conference formats.

Final presentation (4/24, 4/26)

Prepare 10 minute presentation about your work.


Class policies


The course structure (paper review - presentation - group discussion) is mostly based on Prof. Apu Kapadia's method.

Paper review

You need to submit a short review of the papers by the midnight before the class (e.g. by Monday night for the Tuesday's readings). The review for each paper should consists of For each of the points, just list them and add several supporting arguments for each of them.

Paper presentation

Assigned moderators will make a brief (~ 5 minutes) presentation about the premises and the results of the paper. The essential elements in the presentation are:

Academic integrity

The principles of academic honesty and ethics will be enforced. Any cases of academic misconduct (cheating, fabrication, plagiarism, etc) will be thoroughly investigated and immediately reported to the School and the Dean of Students. You should actively discuss with others, but you should write your own report and you should not read others' review. You should credit all the sources (discussion with other students, using some softwares, etc).

Grading policy



Softwares, libraries



Relavant courses