Sgt/lecture3

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ eigen value ลำดับที่ 2 กับกราฟ และบทพิสูจน์

Intuitive of Rayleight Quotient term numerator

จาก

$R(M,x)={\frac {x^{T}Mx}{x^{T}x}}$

สังเกตว่า

$x^{T}Lx=\sum \limits _{(u,v)}(x(u)-x(v))^{2}$

ถ้าเรามองว่า $x(u)$ คือการเปลี่ยนมิติ ของจุดจากกราฟมายังเส้นตรงแล้ว ราคาที่เพิ่มขึ้นจาก เส้นเชื่อมแต่ละเส้น จะเท่ากับระยะห่างของจุดปลายของเส้นเชื่อมนั้นบนเส้นตรงดังกล่าว

Terminology

สำหรับกราฟ $G=(V,E)$ และเซ็ตของปม $S\subseteq V$ เราจะนิยาม $\partial (S)=\{(u,v)\in E,u\in S,v\in V-S\}$ เป็นขนาดของคัท และ อัตราการขยายตัวของปริมาตรผ่านทางเส้นเชื่อม

Isoperimetric Inequality

Isoperimetric ratio of vertices set $\theta (S)={\frac {|\partial (S)|}{|S|}}$

Isoperimetric ratio of graph $\theta (G)=min_{S,|S|\leq n/2}\theta (S)$

ณ จุดนี้ เราจะพิจารณาขอบล่างของ $\theta (G)$ เทียบกับ $\lambda _{2}$ โดยจะพิจารณาขอบบน ซึ่งก็คือ Cheeger Inequality ใน lecture ครั้งถัดไป

"For every $S\subset V,\theta (S)\geq {\lambda }_{2}(1-s),wheres={\frac {|S|}{|V|}}$"

---

จาก Rayleight Quotient เรารู้ว่า ${\lambda }_{2}=min_{x\neq 0,x\perp {\mathbf {1}}}{\frac {x^{T}Lx}{x^{T}x}}$

แสดงว่า ถ้าเราหยิบ vector ใด ๆ ซึ่งไม่ใช่ 0 ที่ตั้งฉากกับ vector 1 มา เราสามารถนำมาบอกขอบเขตของ $\lambda _{2}$ ได้เสมอ

พิจารณา characteristic vector $x$ โดย ${\begin{aligned}x(u)=1&,u\in S\\x(u)=0&,otherwise\end{aligned}}$

สังเกตว่า ${\frac {x^{T}Lx}{x^{T}x}}=\theta (S)$ แต่ $x$ ไม่ตั้งฉากกับ vector ${\mathbf {1}}$

พิจารณา $x'=x-{\frac {|S|}{|V|}}{\mathbf {1}}=x-s{\mathbf {1}}$ สังเกตว่า $x'\perp {\mathbf {1}},x'\neq 0$

จากนั้นเราจะพิจารณาผลของ ${\frac {{x'}^{T}Lx'}{{x'}^{T}x'}}$

โดย ${x'}^{T}Lx'=|\partial {S}|$

และ

${\begin{aligned}{x'}^{T}x'&=\sum \limits _{u}(x'(u))^{2}\\&=\sum \limits _{u}(x(u)-s)^{2}\\&=\sum \limits _{u}x(u)^{2}-2x(u)s+s^{2}\\&=|S|-2s|S|+|V|s^{2}\\&=|S|-2{\frac {|S|^{2}}{|V|}}+{\frac {|S|^{2}}{|V|}}\\&=|S|-{\frac {|S|^{2}}{|V|}}\\&=|S|(1-s)\end{aligned}}$

ดังนั้น

${\begin{aligned}\lambda _{2}&\leq {\frac {{x'}^{T}Lx'}{{x'}^{T}x'}}\\\lambda _{2}(1-s)&\leq {\frac {{x'}^{T}Lx'}{|S|}}\\\lambda _{2}(1-s)&\leq \theta {S}\end{aligned}}$

---

The Adjacency Matrix

กำหนดให้ A เป็น adjacency matrix ของกราฟ $G=(V,E)$ โดยถ้าเรานำ vector x ไปคูณ ผลลัพธ์ที่ได้คือ

$(Ax)(u)=\sum \limits _{(u,v)\in E}w(u,v)x(v)$

พิจารณา regular graph G ที่มี degree d เราสามารถหาความสัมพันธ์ระหว่าง laplacian matrix กับ adjacency matrix ได้โดย

$L=D-A=Id-A$

ถ้า $\lambda$ และ $\varphi$ เป็น eigen value และ eigen vector ที่สอดคล้องกันใน L แล้ว

${\begin{aligned}L\varphi &=(Id-A)\varphi =\lambda \varphi \\A\varphi &=(Id-L)\varphi =(d-\lambda )\varphi \\\end{aligned}}$

ได้ว่า $\mu =(d-\lambda )$ และ $\varphi$ เป็น eigen value และ eigen vector ที่สอดคล้องกันใน A

สังเกตว่าถ้ากราฟเป็น regular แล้ว eigen vector ของ L กับ A จะเป็นชุดเดียวกัน แต่มี eigen value ต่างกัน

กำหนดให้ $\mu _{1}\geq \mu _{2}\geq ...\geq \mu _{n}$ เป็น eigen value ของ A

เมื่อกราฟ G เป็น regular ได้ว่า $\mu _{1}=d$