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. 13 Introduction motivation; course overview; course work
Thur, Jan. 15 Graph Theory Refresher nodes and edges; paths; cycles; connectivity; components; distance; BFS
Tues, Jan. 20 Basic Network Properties Degree distribution;
pathlengths; clustering coefficients;
networks and adjacency matrices
Thur, Jan. 22 Random Graphs I random graph as a concept; random variables and expectation;
graph invariants in random graphs; phase transition
Tues, Jan. 27 Random Graphs II Erdos-Renyi random graphs; binomial distribution; Poisson distribution;
pathlength distribition; clustering coefficient
Thur, Jan. 29 Intro to igraph Assignment 1 goes out
Tues, Feb. 03 Centrality I structural index; centrality around distances and neighbors
(degree centrality, eccentricity, closeness/transmission);
centrality around shortest paths (betweeness centrality)
Thur, Feb. 05 Centrality II Feedback centrality (Katz Index, Eigenvector centrality) Assignment 1 due
Tues, Feb. 10 Link analysis:
Hubs and Authorities Hub score; Authority score; HITS algorithm
Thur, Feb. 12 Link analysis:
PageRank Random surfer model; Markov chains; Perron-Frobenius theorem;
PageRank computation Assignment 1 graded
Tues, Feb. 17 Spectral Analysis Spectrum of the adjacency matrixi, the Laplacian, and the normalized Laplacian;
The second-smallest eigenvalue of the Laplacian; Spectra of subgraphs and supergraphs
Thur, Feb. 19 Similarity Cosine similarity; Pearson coefficients; Euclidean distance; Regular equivalence
Tues, Feb. 24 Homophily and assortative mixing Quantifying assortative mixing; Mechanisms underlying homophily
Thur, Feb. 26 Signed networks Structural balance: characterization and computation; Application of structural balance
Tues, Mar. 03 No class Assignment 2 is due
Thur, Mar. 05 Semester Project discussion Descrition, setup, and deliverables
Tues, Mar. 10 Cascading behavior I Modeling diffusion; cascades and clusters; heterogenous thresholds;
knowledge and collective action
Thur, Mar. 12 Cascading behaviour II cascade capacity; cascades and compatibility
Tues, Mar. 17 Spring Break Assignment 2 graded
Thur, Mar. 19 Spring Break
Tues, Mar. 24 Epidemics I The Braching process; the SIR model; SIR and Percolation; the SIS model; synchronization;
temporal edges and concurrency; Genealogy
Thur, Mar. 26 Epidemics II Analysis of the branching process; Analysis of the Coalescent process;
Broader view of percolation
Tues, Mar. 31 Influence Maximization Independent Cascade Model; Linear Threshold Model; Greedy Hill-Climbing;
Approximation Algorithms; Empirical evaluations
Thur, Apr. 02 The small-world phenomenon Six degree of separation; The Watts-Strogatz samll-world model;
Decentralized serach and its modeling
Tues, Apr. 07 Navigation in social networks Empirical analysis and generalized models for decentralized search:
geographic data on friendship; rank-based friendship; social distance;
search as an instance of decentralized search; generative/evolution models for searchability.
Thur, Apr. 09 Structure of the Web Web basics; Precursors to Web; Web as a directed graph;
Structure of the Web; Web 2.0
Tues, Apr. 14 Community structures I Local bridges and weak ties; Tie strength in real data; community identification;
Girvan-Newman community identification algorithm
Thur, Apr. 16 Communities structures II Modularity; Modularity-optimization based algorithms;
overview of other community identification methods
Tues, Apr. 21 Power Laws Zipf, Power-Laws, and Pareto distribution; Preferential attachment;
The Long Tail.
Thur, Apr. 23 EECS EC meeting
Tues, Apr. 28 Project presentation 1) Fuat Arslan and Hamzeh Zbib
2) Guanqun Wang and Kudrat Kaur
Thur, Apr. 30 Project presentation 1) Helen Catanese and Nitin Panuganti
2) Priyanka Ghosh and Sayan Ghosh Final project report due May 4, 8AM.