INFO/SOCI 485
Computational Methods for Complex Networks
Cornell University, Spring 2008
Lectures: 206 Hollister Hall
Tuesday & Thursday, 10:10-11:25
Instructor: Gueorgi Kossinets, 368 Uris Hall, gk67 -at- you.know.where.
Teaching Assistant: Douglas Forster, dpf8 -at- you.know.where.
Office hours: Thursday 3-4:30pm, 368/365A Uris Hall or by appointment
Description: this is a survey of research methods and
techniques used in the study of complex networks. Interdisciplinary in
nature, the course is intended for anyone interested in computational
techniques of network analysis e.g. students in Information Science,
Communication, Sociology, Economics, and Bioinformatics. You may think
of it as a practicum sequel for ECON204/ SOC209/ CS285/ INFO 204 and
preparation for CS 685 and similar graduate courses. The course covers
a range of modern methods and explores a variety of real-life
datasets, from social to technological to biological networks. We will
learn appropriate tools as we go (making use of the Python NetworkX toolkit).
Syllabus is available as PDF but
most up-to-date information will be on this page.
Programming: see introduction to Python by Doug
Forster (we'll add more information as necessary).
Lecture topics
| Jan 22 |
Lecture 1. Introduction. Network concepts and data. Survey of network datasets. |
| Jan 24 |
Lecture 2. Basic graph theory. Node, edge, graph properties. |
| Jan 29 |
Lecture 3. Some ideas for final projects. Introduction to Python and NetworkX.
Wikipedia usertalk network example: wiki-example.py
Wikipedia dataset wiki-usertalk-data.zip (unzip before using or modify the code to use zipfile.ZipFile).
See tutorial by Doug Forster and lecture notes by Prof. Muller at Caltech |
Jan 31 |
Lecture 4. Intro to Python continues. Log of in-class interactive session.
Homework 1 (due February 7)
|
Feb 5 | Lecture 5. Centrality. Network
sampling. Clustering coefficients. Network visualization.
|
Feb 7 | Lecture 6. Milgram's small world experiment. The
Watts & Strogatz small world model. Extensions.
|
Feb 12 | Lecture 7. Random variables and probability
review. Random graphs. Heavy tailed distributions. "Scale free"
networks.
|
Feb 14 | Lecture 7 (overflow). Preferential attachment
(Yule, Merton, Simon, de Solla-Price). The Barabasi-Albert model.
Bayesian model comparison.
|
Feb 19 | Non-lecture 8. Analysis of Homework 1: what
went wrong, pythonisms, best practices.
|
| To be continued...
|
Final projects
The project may be along either of these lines:
(a) An analysis of an empirical network
(b) An analysis of a generative or evolutionary network model
(c) A simulation of a process on network
(d) An implementation of an exsting algorithm as a NetworkX module
You may work individually or in groups (up to 4 people).
Some examples of student
projects at University of Michigan (note those are by MS and PhD
students and we don't have to be that advanced -- but the idea is the
important thing).
Important dates
| February 28 |
Project proposals due (1 page abstract, possibly 5-10 minutes class briefing) |
| March 28 |
Project status reports due (preliminary results summary, plan of remaining work) |
| April 29 |
In class presentations |
| May 15 |
Final project reports due (5-6 pages in the
ACM proceedings format ) |
Network datasets
Course topics
(Depending on the students' background and
interests, we may substitute or add topics)
I. Network concepts and data
- basic graph-theoretical concepts (nodes, edges, paths,
components)
- survey of datasets (social, economic, transportation, computer,
biological networks)
- network types and representations (directed, weighted,
bipartite)
- implications of missing data
II. Exploratory analysis
- network statistics and summary measures
- visualizing networks
- structural similarity; assortative mixing; homophily
- understanding community structure
- enumerating network motifs
- measuring and describing networks over time
III. Modeling network structure
- random graphs; networks with arbitrary degree
distribution
- small world networks; scale-free networks
- network growth; densification; preferential attachment
- network identification (which generative model fits
better)
IV. Measuring and simulating dynamic processes on networks
- information flows; social influence and
diffusion
- disease epidemics and intervention strategies
- resource location and strategic search
- signaling in metabolic and neuronal networks
- games on networks; cooperation and coordination; selfish
routers
- network segregation; opinion dynamics
- predicting with networks; regression and classification using
network data
References
- Ulrik Brandes and Thomas Erlebach (Eds). Network Analysis:
Methodological Foundations. Springer, 2005. The book is accessible
online.
- Jon Kleinberg and Eva Tardos. Algorithm Design.
Addison-Wesley, 2005.
- S. Bornholdt and H. G. Schuster (Eds). Handbook of Graphs and
Networks. Wiley, 2003.
- J. Zelle. Python Programming: An Introduction to Computer
Science. Franklin Beedle, 2003.
|