Analysis of Complex Network

Back to Yung Yi, Courses

Introduction

A graduate-level course on the analysis of complex networks based on the randomized algorithm analysis techniques. Lectured by Prof. Yung Yi, KAIST, South Korea (spring13, spring16).

Textbook

Epidemics and Rumours in Complex Networks, by Moez Draief and Laurent Massoulie

images/complex_book.jpg

Note

모든 녹화 강의는 한글로 진행되었고, YouTube에 업로드 되었습니다(14.Epidemics on general graphs 제외). 본 강의에서는 고급 확률적 분석 기술 (randomized algorithm, branching process, Stein-chen method, Martingale, Azuma-Hoeffding inequality, Kurtz theorem, coupling 등등)을 이용하여 복잡계 네트워크에서 epidemics에 관한 여러 알려진 현상을 수학적으로 기술해보고, 끝까지 증명해 보는 수업이었습니다.

본 수업을 통해서 다시 한번 느꼈던 점은, 논문을 많이 읽는 것도 중요하지만, 모델링과 분석을 주요 목적으로 하는 연구의 경우, 핵심 수학적 증명을 완결성있게 끝까지 해보는 것이 연구에 얼마나 중요한지 대학원생들과 같이 느꼈습니다.

본 수업 이후 대학원생들이 재미있고 나름대로 깊이가 있는 논문을 많이 작성하였고 (Sigmetrics, Infocom, ICML, AISTATS 등등), 그 점에 대해서 보람과 감사를 느끼고 있습니다. 본 강의자료는 오랫동안 LANADA 내부에서 신입생 교육 및 학술 논문 준비 자료로 활용되어 왔습니다.

Contents	Videos	Materials
1. Introduction to Complex Network	Part 1: Intro to complex network and what this course is about. Youtube	Lecture notes Many from Moez Draief's slides.
2. Erdős–Rényi (ER) graph	Part 1: The most basic random graph. Youtube	Lecture notes
3. Galton-Watson branching process	Part 1: Definition and depth-first exploration. Youtube Part 2: Breadth-first exploration and phase transition. Youtube Part 3: One-by-one exploration. Youtube	Lecture notes
4. Chernoff bound	Part 1: Boudning the probability of rare events. Youtube	Lecture notes
5. Emergence of giant components	Part 1: Subscritical regime. Youtube Part 2: Supercritical regime. Youtube Part 3: Critical regime. Youtube	Lecture notes
6. Connectivity and Poisson approximation	Part 1: Story on the big picture. Youtube Part 2: Convergence of random variables Youtube Part 3: Poisson approximation (Stein-Chen method) Youtube Part 4: When nodes are connected in ER-graphs Youtube	Lecture notes
7. Diameter of ER graphs	Part 1: Main results, meaning, and proof steps Youtube Part 2: Proof step 1 Youtube Part 3: Proof step 2 Youtube	Lecture notes
8. Small world I: Strogatz and Watts	Part 1: Result, meaning, and proof steps Youtube Part 2: Martingale and Azuma-Hoeffding inequality Youtube Part 3: Proof Youtube	Lecture notes Martingale and Azuma Hoeffding inequality, pdf, pptx
9. Small world II: Kleinberg	Part 1: Result and meaning Youtube Part 2: Theorem statement and proof step 1 Youtube Part 3: Proof step 2 Youtube	Lecture notes
10. Background: Markov chain (MC)	Part 1: Discrete time MC Youtube Part 2: Continuous time MC, Embedded MC Youtube	Lecture note 1, Lecture note 2
11. From micro to macro dynamics	Part 1: Story, functional LLN, Kurtz theorem Youtube Part 2: Using Kurtz theorem, understanding SIS epidemics Youtube Part 3: Doob's inequality, Gronwall's lemma, Kurtz thm proof Youtube	Lecture notes Functional LLN and M/M/1 fluid model
12. Power laws via preferential attachment	Part 1: Preferential attachment (PA) algorhm Youtube Part 2: Power-law degree distribution and heavy-tail behavior Youtube Part 3: PA --> power-law degree distribution, Proof steps Youtube Part 4: Coupling technique (guest lecture by Jiin Woo) Youtube Part 5: Proof of main results Youtube	Lecture notes Coupling
13. Influence maximization	Part 1: Viral marketing and influence maximization problem Youtube Part 2: Proof step 1 Youtube Part 3: Proof step 2 Youtube Part 4: Proof step 3 Youtube	Lecture notes Influce maximization
14. Epidemics on general graphs SIS (Susceptible-Infected-Susceptible) SIR (Susceptible-Infected-Removed)		Lecture slides (pdf) Lecture slides (pptx) Made by Prof. Jungseul Ok at Postech.