CptS 591: Elements of Network Science
Course Information
Credit hours: 3
Semester Offered: Spring
Course Description
This 3 credit, graduate-level course introduces fundamental elements of the emerging science of complex networks, with emphasis on social and information networks. Students will learn about mathematical and computational methods used to analyze networks, models used to understand and predict behavior of networked systems, and theories used to reason about network dynamics. Students will also be exposed to current research in the field, and they will be given an opportunity to explore a chosen topic through a semester project.
Topics to be covered include
- Network structure, modeling and algorithms:
Graph theory essentials; Basic network properties; Random graphs; Spectral graph theory;
Centrality; PageRank; Hubs and Authorities; Graph similarity; Community detection
- Network dynamics:
Cascading behaviors; Information diffusion; Epidemic models; Influence maximization;
Time-varying networks
- Hypergraph-based methods:
Models and algorithms for analysis of multi-way relationships (using hypergraphs)
- Graph embeddings:
Graph embeddings; representation learning
Audience
The course is suitable for graduate students in computer science, engineering, epidemiology, sociology, economics, mathematics, physics, and related fields.
Prerequisites
Students are expected to have basic knowledge of algorithms (equivalent to completing an undergraduate algorithms course such as CptS 350), some programming experience (e.g. in Python, R, C, or Java), and familiarity with basic linear algebra (e.g. solution of linear systems and eigenvalue/vector computation) and basic probability and statistics.
Learning Outcomes
At the conclusion of the course, students should be able to:
- Explain basic metrics and measures used to characterize networks
- Analyze a network using the various measures and a suitable network analysis software tool
- Discuss the strengths and weaknesses of random graph models
- Understand and apply key algorithms for link analysis (ranking), community identification, and network comparison
- Understand and apply models and theories used to reason about cascading behaviors, information spread, and decentralized navigation in networks
- Understand and explain the interdisciplinary nature of the area of network science
- Critique research papers in the area
- Apply knowledge gained in the course to carry out a project and write a scientific report
Course Work
The course consists of lectures (twice a week, 75 min each) and involves a set of assignments and exercises, one exam, and a semester project.
- Assignments (30%). There will be three assignments mostly spread through the first half of the semester and a few, periodic exercises. Assignments and exercises are to be completed and submitted individually.
- Semester Project (50%). Working in teams of two or individually, students will complete a semester project. A semester project could take one of several forms: analysis of an interesting dataset using existing methods and software; comparison of existing methods and software tools in the context of a specific application; implementation of a new method; exploration of a chosen research topic.
Each project will have required submissions at three different stages—the submissions are called Reaction Paper, Project Proposal and Final Report—and will culminate with a presentation in class.
For the Reaction Paper part students will get to pick and read two closely related papers out of a list of papers the instructor provides and write a short reaction paper summarizing and critiquing the two papers and identifying opportunities for further work. Project Proposal is a short document (2 or 3 pages long) that describes the proposed project and the tentative plan to carry it out. Ideally it is an outgrowth of the Reaction Paper component, but can also deviate from it. The outcome of the project will be a final report of about 8 to 12 pages long.
Guidelines for writing the proposal and the final report will be provided at an appropriate time during the semester. A more complete project description detailing the various components will also be provided.
The 50% weight of the semester project towards final grade is further broken down into its components as follows: Reaction Paper 7%, Project Proposal 7%, Presentation 8%, Final Report 28%. - Exam (18%). There will be one mid-term exam.
- Class Participation (2%). Students are expected to actively participate in class discussions, in-class exercises and thought experiments
Expectations for Student Effort
For each hour of lecture equivalent, students should expect to have a minimum of two hours of work outside class.
Grading
Letter grades will be given according to the following ranges:
A (93–100%), A- (90–92.99%), B+ (87–89.99%), B (83–86.99%), B- (80–82.99%), C+ (77–79.99%), C (70–76.99%), C- (67–69.99%), D (60–66.99%), F (less than 60%).
Books and Course Material
There is no required textbook for the course. Lecture notes, readings and related resources will be posted at the course website or the OSBLE page of the course as the course proceeds.
The following book will be used as a frequent reference:
- D. Easley and J. Kleinberg, Networks, Crowds and Markets, Cambridge Univ. Press, 2010.
The book is available on-line at Networks, Crowds and Markets book link.
Other related references include:
- M.E. J. Newman, Networks: An Introduction, Oxford University Press, 2010.
- U. Brandes and T. Erlebach (Eds.), Network Analysis: Methodological Foundations, Springer, 2005.
- This book is available online via the doi: Network Analysis book link
- A.L. Barabasi, Network Science, Network Science book link
- Keep checking this list as I expect to add more
Software:
The graph analysis package igraph will be used as the primary software resource. The package igraph is open-source and free.
Schedule Overview
| WEEKS | TOPICS | ASSIGNMENTS |
|---|---|---|
| 01 | Introduction; Graph theory | Survey out |
| 02 | Network properties | Survey due, Assignment 1 out |
| 03 | Intro to igraph | |
| 04 | Random graphs | Assignment 1 due |
| 05 | Spectral graph theory | Assignment 1 due |
| 06 | Centrality | |
| 07 | PageRank; Hubs and Authorities | Assignment 2 due |
| 08 | Community detection, project discussion | |
| 09 | Graph similarity, signed networks | Mid-Term |
| 10 | Spring Break | |
| 11 | Hypergraphs | Reaction paper due |
| 12 | Graph embedding | Project proposal due |
| 13 | Cascading behaviors | Assignment 3 out |
| 14 | Influence maximization, Epidemic model | Assignment 3 due |
| 15 | Time-varying networks, wrap-up | |
| 16 | Project presentations | |
| May 1 | Finals Week | Final project report due |