Stanford CS224W: Machine Learning with Graphs - Stanford CS224W: Machine Learning with Graphs | 2021 | Lecture 14.2 - Erdos Renyi Random Graphs

For more information about Stanford’s Artificial Intelligence professional and graduate programs, visit: https://stanford.io/3GzPg4L Jure Leskovec Computer Science, PhD We introduce the simplest model for graph generation, Erdös-Renyi graph (E-R graphs, Gnp graphs). The Gnp random graphs are undirected graphs over n nodes, where each edge appears i.i.d. with probability p. We analyze ER graphs using the graph statistics we have introduced. Gnp graphs have binomial degree distribution. Gnp graphs have very small clustering coefficient. Graph structure of Gnp changes as p changes. To measure the path length of Gnp graphs, we introduce the nodtion of expansion, and derive that the shortest path length of Gnp graphs follows O(log n). To follow along with the course schedule and syllabus, visit: http://web.stanford.edu/class/cs224w/ 0:00 Introduction 0:33 Simplest Model of Graphs 1:50 Random Graph Model Gmp 2:19 Properties of Gmp 3:11 Degree Distribution of G 5:00 Clustering Coefficient of me Remember: C 7:03 Connected Components of G.mp . Graph structure of Gasp changes 8:29 GP Simulation Experiment 9:43 Def: Expansion 11:05 Expansion: Measures Robustness 12:42 Expansion: Random Graphs 15:01 Shortest Path of Go 15:31 Back to MSN vs. Gmp 18:38 Real Networks vs. G. #machinelearning #machinelearningcourse