CSE 416a Roadmap

Topics and order are subject to changes as the semester evolves.

I   Networks & Graph Theory

  • complex systems and networks
  • graph representation, notation and definitions
  • degree distribution, paths, distance distribution, diameter, connectedness
  • application: social network analysis
    • triadic closure, clustering coefficient
    • strong and weak ties
    • homophily and social-affiliation networks
  • node centrality and importance
  • network robustness and resilience

II   Network Models

  • small-world phenomenon
  • random graph model (Erdös-Rényi graphs)
  • Watts-Strogatz model
  • rich-get-richer phenomenon
  • fitness model, Barabási-Albért graphs, and scale-free networks

III  Analyzing Networks: Graph Mining

  • application: community detection
    • betweenness
    • Girvan-Newman algorithm
    • graph clustering, graph partitioning
  • triangles, cliques, and paths
  • application: structure of the web & link analysis
    • web graph
    • hubs and authorities (HITs)
    • PageRank

IV  Modeling Dynamics: Information Cascades, Link Prediction, Epidemics

We can choose some topics to study in more detail (time permitting).

  • information cascades, diffusion models: how does information spread?
  • link prediction, supervised random walks: how do friendship suggestions work?
  • epidemic models: how do diseases spread?

V  (Machine) Learning with Graphs: Node and Graph Classification

We can choose some topics to study in more detail (time permitting).

  • node similarity and node classification
  • graph similarity and graph classification
  • graph and node embeddings