Elements of Network Science: CptS 580-06/EE 582-03, Spring 2015

Schedule and Lecture Material

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.


Tues, Jan. 13Introduction motivation; course overview; course work
Thur, Jan. 15Graph Theory Refreshernodes and edges; paths; cycles; connectivity; components; distance; BFS
Tues, Jan. 20Basic Network Properties Degree distribution; pathlengths; clustering coefficients;
networks and adjacency matrices
Thur, Jan. 22Random Graphs I random graph as a concept; random variables and expectation;
graph invariants in random graphs; phase transition
Tues, Jan. 27Random Graphs II Erdos-Renyi random graphs; binomial distribution; Poisson distribution;
pathlength distribition; clustering coefficient
Thur, Jan. 29Intro 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:
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. 24Homophily 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. 17Spring Break Assignment 2 graded
Thur, Mar. 19Spring 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.