CSE 416a Calendar (FL19)

This is an inactive course webpage.

 

If you are wondering where we are going: here is the intended Roadmap!

(*)indicates more advanced reading for the interested student

_______

Topic

Materials

27 Aug Course OverviewSyllabus
29 Aug Introduction

  • complex systems
  • networks
  • network analysis

Motivation: Seven Bridges

Part I: Networked Data & Graphs

slides

3 Sept
  1. Definitions and Notation
  2. Types of Graphs
5 Sept
  1. Data Structures for Graphs
  2. Paths and Connectivity
  • [NCM] Chapter 2.2
  • [CNA] Ch11 – Connected Components
10 Sept

12 Sept

  1. Distances
    • Dijkstra (single source SP)
    • Floyd-Warshall (all pairs SP)
  2. Case Study: Small World
    • Global Social Network
    • Six-Degrees of Separation
    • CNA Measures
    • Social Interpretations
    • Beyond SNs
17 Sept
  1. Node Importance
    • Degree Centrality
    • Closeness Centrality
    • Harmonic Centrality
    • Betweenness Centrality
    • Eigenvector Centrality
  2. Case-Study: Robustness of the Internet
19 Sept
  1. Network Structure (Microscopic)
    • Clustering Coefficient
    • Triadic Closure
    • Strength of Weak Ties
    • Neighborhood Overlap
24 Sept
  1. Network Structure and Context (Macroscopic)
    • Assortativity
    • Surrounding Context & Homophily
  • [CNA] Ch8 – Measuring Networks
    • Estimate Network Uniformity Through Assortativity
  • Lecture notes by Aaron Clauset
  • [NCM] Ch4-4.2

Part II: Network Models

slides [Raj], slides [MN]

1 Oct

 

  1. Random Graph Model
    • Definition
    • Degree Distribution
    • Clustering Coefficient
    • Avg. Path Length
    • Giant Component
    • Evolution & Phase Transition
    • Discussion
  • [SMM] Ch4.2
  • [CNA] 
    • Ch6 – Appreciate Synthetic Networks
    • Ch7 – Generate Synthetic Networks
  • [demo] Complex Networks
3 Oct
  1. Small World Model
    • Definition
    • Avg. Path Length
    • Clustering Coefficient
    • Discussion
8 Oct
  1. Scale-Free Networks
    • Power-Law Distribution
    • Detection
    • Exponent Estimation
10 Oct
  1. Preferential Attachment
    • Model
    • Rich-get-richer
    • Power-law Degree Distribution
    • Clustering coefficient
    • Avg. path length
15 Oct  FALL BREAK – no class

Part III: Graph Mining

slides

17 Oct
  1. Motifs & Graphlets
  2. Communities
  3. Betweenness-based Clustering
    • Girvan-Newman Algorithm
    • Modularity
22 Oct

24 Oct

 

  1.  Modularity Maximization
    • Mathematical Derivation
    • Algorithm
29 Oct
  1.  Spectral Clustering
    • Laplacian Matrix
    • Algorithm
31 Oct
  1. Overlapping Communities
    • Clique Percolation Method
    • Finding Cliques
5 Nov
  1. Node Similarity
    • Structural & Regular Equivalence
    • (Markov) Random Walks
    • SimRank
    • Application: Link Prediction
7 Nov
  1. Node Classification
    • Problem Introduction
    • Label Propagation
12 Nov Exam Review
  • summary slides for all slides linked above
14 Nov In-Class EXAM

Part VI: (More) Applications

slides

19 Nov

21 Nov

  1. Spreading Processes
  2. Disease Spread and Epidemics
  3. Cascading Behavior
  4. Graph Classification
26 Nov Networks in AI

  • Natural Language Processing
  • Social and Commonsense Reasoning
  • Adversarial Learning / Security
28 Nov  THANKSGIVING – no class

Semester Summary

slides

3 Dec FINAL PROJECT presentations
  • project presentations schedule and slide submission instructions: here
5 Dec FINAL PROJECT presentrations
  • project presentations schedule and slide submission instructions: here
13 Dec FINAL PROJECT 

  • report due at 8pm
  • no extension