I will use the online portal OSBLE (https://osble.org) for posting lecture materials, assignments, class related announcements, etc, and handling submissions. On this page, I will maintain an overview of the schedule as the course proceeds.
Here is a page where I have compiled a list of papers from the recent (and not-so-recent) literature around the topics of this course.
Schedule
Date Topic Details Comments
Tues, Jan. 12
Introduction
motivation; course overview; course work.
Slides (PPTX, PDF).
Survey out.
Thur, Jan. 14
Graph Theory Refresher
Nodes and edges; paths; cycles; connectivity; components; distance; Breadth-First Search; The small-world phenomenon; Network data sets.
Reading: Chapter 2 of Easley & Kleinberg.
Lecture slides and reading posted on OSBLE.
Tues, Jan. 19
Basic Network Properties
Degree distribution; path lengths and distributions; Clustering coefficient
Lecture talking-points summary and lecture slides posted on OSBLE.
Thur, Jan. 21
Random Graphs I
Random graph as a concept; Random variables and Expectation; Graph invariants in random graphs; Phase transition
Lecture slides posted. Suggested (optional) reading: Chapter 11 of Diestel. Survey due.
Tues, Jan. 26
Random Graphs II
Random graphs vs Real-world networks (wrt degree distribution; average path length; clustering coefficient)
Typed lecture notes posted.
Thur, Jan. 28
Intro to igraph
Tutorial given by Helen Catanese.
Tutorial slides posted on osble.
Tues, Feb. 02
Spectral Analysis I
We reviewed basic linear algebra needed for spectral analysis/spectral graph theory
Typed lecture notes posted. Assignment 1 went out. The second tutorial on igraph will take place Wed, Feb 3 from 3:00 to 4:30pm in Sloan 163.
Thur, Feb. 04
Special lecture:
Sparse Matrices for High Performance Graph Analytics
We will attend John Gilbert's lecture at the Distinguuished Speaker Series in Data Science. Lecture title: "Sparse Matrices for High Performance Graph Analytics". Event takes place in ETRL 101 from 12:00pm to 1:00pm.
Slides of the talk.
Tues, Feb. 09
Class cancelled.
Assignment 1 due.
Thur, Feb. 11
Spectral Analysis II
Spectrum of three different matrices associated with a graph:
the adjacency matrix, the Laplacian and the normalized laplacian;
the second-smallest eigenvalue of the Laplacian and its significance; isoperimetry;
spectra of subgraphs and supergraphs.
Typed lectures note posted.
Tues, Feb. 16
Centrality I
Motivating example illustrating the need for different centrality measures;
elementary common denominator formalization for centrality measures;
centrality around distances and neighbors.
Typed notes posted.
Thur, Feb. 18
Centrality II
Centrality around shortest paths; Feedback centrality (Katz Index).
Typed notes posted.
Tues, Feb. 23
Link Analysis: PageRank
"Random surfer" derivation of PageRank; Markov chain; Solving the PageRank vector system.
Typed lecture notes posted. Further reading: David Gleich's 2015 SIAM Review article titled "PageRank Beyond the Web" (also posted).
Thur, Feb. 25
Link Analysis: Hubs and Authorities
Hub score; Authority score; HITS algorithm.
Lecture material: Chapter 14 of Easley-Kleinberg.
Assignment 2 went out. New due date and time: Sat. March 5, noon.
Tues, Mar. 01
Similarity
Structural equivalence -- Cosine similarity; Pearson Coefficients; Regular equivalence -- "Katz Similarity".
Lecture slides posted. Copy of Sec 7.12 of Newmman handed in class.
Thurs, Mar. 03
Graph Similarity
Graph similarity with known node correspondence; Graph similarity with unknown node correspondence.
We went through material from the ICDM14 tutorail
given by Koutra, Elliassi-Rad and Faloutsos.
Assignment 2 is due by Sat March 05 noon.
Tues, Mar. 08
Semester Project discussion
Description, setup, and deliverables
Thur, Mar. 10
Signed networks
Structural balance;
Characterizing the structure of balanced networks;
Applications of structural balance;
Weakly balanced netwroks and their characterization.
Lecture slides posted. Chapter 5 of Easley-Kleinberg posted as reading material.
Assignment 3 went out on 3/12
Tues, Mar. 15
Spring Break
Thur, Mar. 17
Spring Break
Tues, Mar. 22
Cascading behaviors I
Following the crowd; Diffusion in networks; Modeling diffusion through a network; Cascades and clusters; Diffusion, Thresholds, and the Role of weak ties; Heterogenous thresholds; Collective action and pluralistic ignorance.
Lecture slides posted. Chapter 19 of Easley-Kleinberg posted as reading material. Assignment 3 due.
Thur, Mar. 24
Cascading behaviors II
Cascade capacity; Cascades and compatibility.
Lecture slides posted. Reaction Paper due March 25.
Tues, Mar. 29
The small-world phenomenon
Milgram's experiment; Watts-Strogatz model; Decentralized search
White-board based lecture. Chapter 20 of Easley-Kleinberg, and Watts-Strogatz'98 and Milgram'67 papers posted as reading material.
Thur, Mar. 31
Navigation in social networks
Kleinberg's decentralized search model; Searchability and navigation; Applications. We also discussed the Reaction Paper submissions and project ideas and teams.
Lecture slides posted. Reading material connsisting of several papers also posted. Project proposal due Apr 4, Noon.
Tues, Apr. 05
Epidemics
Branching processes; The SIR epidemic model; The SIS epidemic model; Synchronization; Transient contacts and dangers of concurrency; Genetic inherritance.
Lecture slides posted. Chapter 21 of Easley-Kleinberg posted as reading material.
Thur, Apr. 07
Epidemics II
Analysis of branching and coalescent processes. Percolation and applications.
Lecture slides posted.
Tues, Apr. 12
Influence maximization
Motivation: viral marketing; Diffusion models: Independent Cascade Model (ICM) and Linear Treshhold Model (LTM);
Maximizing spread of influence under ICM and LTM; Hill-climbing algorithm; Nemhauser-Wolsey-Fisher Theorem; Submodularity; Experimental results.
Lecture slides posted. The Kempe-Kleinberg-Tardos KDD03 paper posted as a reading material.
Thur, Apr. 14
Community identification (clustering)
Had an overview type lecture on why communities exist in networks and methods for discovering them. This was a truly panoramic overview lecture, and
details were left for those interested to read on their own.
Lecture slide with pointers to many resources posted. Chapter 3 of Easley-Kleinberg posted as a reading material.
Tues, Apr. 19
Review and Wrap Up.
We looked back at the topics we covered in the semester and reflected.
We also discussed the project presentations schedule and final report expectations.
Slides
Thur, Apr. 21
Project presentations
1. Zhila Esna Ashari and Mukti Sharma
Signed networks: critical survey and analysis
2. Abu Sayed Chowdhury and Md. Kamruzzaman
Spotting contagion nodes in a large network
3. Md. Touhiduzzaman and Viresh Duvvuri
Cascading failure and cyber-security analysis of a US power grid
Tues, Apr. 26
Project presentations
1. Vladyslav Oles, Sai Vignesh and Jesse Waite
Centrality analysis of communication networks using the Enron email dataset
2. Ramyar Saeedi and Seyed-Ali Rokni-Dezfooli
Network similarity-based transfer learning for human activity recognition systems
3. Rajveer Singh and Ramyya Hari
Structural analysis of power grids
Thur, Apr. 28
Project presentations
1. Joel Helkey and Anand Raguraman
Achieving cycle-free fast-failover paths in a software define network
2. Ramin Fallahazadeh and Parastoo Alinia
Classifier-based network similarity: An application to transfer learning
3. Shashvath PV, Yuhui Wang and Siddhanth Srivastava
Diffusion in social networks
Wed, May 4
Final project report due
by 11:59am.
Thanks for a fantastic semester and
best wishes in your future endeavors!