Spectral Graph Theory: Introduction

Related lectures (51)

Introduces network data structures, models, and analysis techniques, emphasizing permutation invariance and Erdős-Rényi networks.

Explores interlacing families of polynomials and 1-sided Ramanujan graphs, focusing on their properties and construction methods.

Covers stochastic properties, network structures, models, statistics, centrality measures, and sampling methods in network data analysis.

Introduces elementary graph algorithms, focusing on Breadth-First Search and Depth-First Search.

Covers graphical models for probability distributions and factor graphs representation.

Explores Bourgain's theorem on sparsest cut in graphs, emphasizing semimetrics and cut optimization.

Explores Cheeger's inequalities for random walks on graphs and their implications.

Introduces graph theory, network flows, and flow conservation laws with practical examples and theorems.

Covers the basics of graph algorithms, focusing on modeling and representation of graphs in memory.

Covers embedding graphs into trees with a focus on minimizing distortion and Bartal Tree embeddings.

Covers the concept of graph sketching with a focus on connected components.

Explores distances on graphs, cut norms, spanning trees, blockmodels, metrics, norms, and ERGMs in network data analysis.

Focuses on open problems and the importance of reformulating problems with better tools and intuition.

Explains message passing in graphical models and the matching problem in graph theory.

Demonstrates the iterative process of applying Dijkstra's algorithm to find optimal paths.

Covers distributions, derivatives, convergence, and continuity criteria in function spaces.

Explores belief propagation on graphs, emphasizing normalization, recursive relations, and iterative computation of the partition function.

Explores Bellman-Ford algorithm for negative weight graphs and currency exchange rates.

Explores the Cartesian product operation on graphs and introduces the concept of cubes.

Explores dynamic programming for the Knapsack problem, discussing strategies, algorithms, NP-hardness, and time complexity analysis.

Page 2 of 3