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.

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! |