מטריצת לפלסיאן

בתורת הגרפים, מטריצת לפלסיאן (לעיתים מטריצת קירכהוף) היא מטריצת המתארת גרף. למטריצת הלפלסיאן שימושים רבים והיא מאפשרת למצוא תכונות שונות של גרפים. בין היתר באמצעות משפט קירכהוף ניתן לחשב את מספר העצים הפורשים בגרף. שימוש חשוב נוסף של מטריצת הלפלסיאן הוא בהקשר של גרפים מרחיבים, שבהם אי שוויון צ'יגר קושר בין הערך העצמי השני של מטריצת הלפלסיאן לחתך המינימלי בגרף.

הגדרות

מטריצת הלפלסיאן עבור גרף $G$, שבו $n$ קודקודים היא מטריצה בגודל $n\times n$ המוגדרת כך:

$L=D-A,$

כאשר:

• $D$ היא מטריצת הדרגות - מטריצת אלכסונית אשר הערכים על האלכסון הם ערכי הדרגות של כל קודקוד
• $A$ היא מטריצת שכנות - מטריצה שבה עבור כל שני קודקודים $i,j$ יופיע 1 בתא ה-$i,j$ אם שני הקודקודים שכנים, ו-0 אחרת.

כאשר עוסקים בגרף מכוון לעיתים נעשה שימוש בדרגת הקשתות הנכנסות ולעיתים נעשה שימוש בדרגת הקשתות היוצאות כתלות בשימוש.

התאים במטריצת $L$ נתונים על ידי:

$$L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}\end{cases}}$$

כאשר $deg(v_{i})$ היא הדרגה של הקודקוד ה-$i$.

שתי מטריצות הנגזרות ממטריצת הלפלסיאן, מטריצת הלפלסיאן הסימטרית המנורמלת ומטריצת הלפלסיאן המנורמלת של מהלך אקראי, הן גרסאות מנורמלות של המטריצה, ולהן שימושים בהקשרים שונים.

מטריצת לפלסיאן סימטרית מנורמלת (symmetric normalized Laplacian matrix) מוגדרת כך:

$$L^{\text{sym}}:=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$$

,

התאים ב-$L^{\text{sym}}$ נתונים על ידי:

$$L_{i,j}^{\text{sym}}:={\begin{cases}1&{\mbox{if}}\ i=j\ {\mbox{and}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}$$

מטריצת לפלסיאן מנורמלת של מהלך אקראי (random-walk normalized Laplacian matrix) מוגדרת כך:

$$L^{\text{rw}}:=D^{-1}L=I-D^{-1}A$$

האיברים של $L^{\text{rw}}$ נתונים על ידי:

$$L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if}}\ i=j\ {\mbox{and}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}$$

דוגמה

להלן דוגמה לגרף ולמטריצת הלפלסיאן שלו:

גרף	מטריצת דרגות	מטריצת שכנויות	מטריצת לפלסיאן
	$\left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)$	$\left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)$	$\left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)$

תכונות

עבור גרף לא מכוון $G$, שמטריצת הלפלסיאן שלו היא $L$ עם ערכים עצמיים $\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}$:

• $L$ היא מטריצה סימטרית
• $L$ היא מטריצת חיובית למחצה (כלומר לכל $i$ מתקיים $\lambda _{i}\geq 0$)
• הסכום של כל שורה ושל כל עמודה הוא 0, שכן הדרגה נסכמת עם 1- לכל שכן.
• בהתאם $\lambda _{0}=0$ כיוון שהווקטור $\mathbf {v} _{0}=(1,1,\dots ,1)$ מקיים $L\mathbf {v} _{0}=\mathbf {0} .$
• מספר הפעמים ש-0 מופיע כערך עצמי במטריצה הוא כמספר רכיבי הקשירות בגרף.
• הערך העצמי הקטן ביותר של $L$ שאינו 0 נקרא הפער הספקטרלי.
• הערך העצמי השני הכי קטן הוא הקשירות האלגברית (או ערך פידלר) של $G$.
• כאשר $G$ הוא k-רגולרי הלפלסיאן המנורמל הוא ${\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A$, כאשר $A$ היא מטריצת השכנות ו-$I$ היא מטריצת היחידה.
• מטריצת לפלסיאן היא מטריצה סינגולרית

מטריצת החילה

עבור גרף $G=(V,E)$, שבו $V$ הם קבוצת הקודקודים ו-$E$ היא קבוצת הקשתות, מטריצת החילה (Incidence matrix)‏ $M$ היא מטריצה בגודל $|E|\times |V|$ שהתא ה-$M_{ev}$ עבור $e=(i,j)\in E$ ו-$v\in V$ נתון על ידי:

$M_{ev}=\left\{{\begin{array}{rl}1,&{\text{if}}\,v=i\\-1,&{\text{if}}\,v=j\\0,&{\text{otherwise}}.\end{array}}\right.$

ניתן לחשב את מטריצת הלפלסיאן ממטריצת החילה באופן הבא:

$L=M^{\text{T}}M$

כאשר $M^{\text{T}}$ הוא שחלוף השורות והעמודות של $M$.

הפירוק לווקטורים עצמיים של מטריצת הלפלסיאן $L$, עם וקטורים עצמיים עם גודל יחידה $\mathbf {v} _{i}$ וערכים עצמיים $\lambda _{i}$:

${\begin{aligned}\lambda _{i}&=\mathbf {v} _{i}^{T}L\mathbf {v} _{i}\\&=\mathbf {v} _{i}^{T}M^{T}M\mathbf {v} _{i}\\&=(M\mathbf {v} _{i})^{T}(M\mathbf {v} _{i}).\\\end{aligned}}$

מאחר ש-$\lambda _{i}$ יכול להיכתב כמכפלה פנימית של הווקטור $M\mathbf {v} _{i}$ עם עצמו, זה מראה כי $\lambda _{i}\geq 0$ ולכן כל הערכים העצמיים של $L$ הם לא שליליים.

מטריצת לפלסיאן סימטרית מנורמלת

מטריצת לפלסיאן (סימטרית) מנורמלת מוגדרת כך:

$L^{\text{sym}}:=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$

כאשר $L$ היא מטריצת לפלסיאן, $A$ היא מטריצת שכנות ו-$D$ היא מטריצת הדרגות. מאחר שמטריצת הדרגות $D$ היא אלכסונית וחיובית, השורש ההופכי שלה $D^{-1/2}$ הוא מטריצה אלכסונית שבה הערכים לאורך האלכסון הם ההפכים של השורשים של הערכים על האלכסון של $D$.

ניתן לחשב אותה כך: $L^{\text{sym}}=SS^{*}$, כאשר $S$ היא מטריצה שבה השורות מאונדקסות על יד הקודקודים והעמודות על פי הקשתות של הגרף כך שבעמודה המתאימה לקשת $e=(u,v)$, התא בשורה $u$ הוא הוא בעל ערך ${\frac {1}{{\sqrt {d}}_{u}}}$, ובשורה המתאימה ל-$v$ הוא בעל ערך $-{\frac {1}{{\sqrt {d}}_{v}}}$, ו-0 ביתר התאים. (הערה: $S^{*}$ מייצג את השחלוף של $S$).

כל הערכים העצמיים של מטריצת הלפלסיאן המנורמלת ממשים ואי שליליים. אפשר להראות זאת כך: מאחר ש-$L^{\text{sym}}$ היא סימטרית, הערכים העצמיים בה ממשיים. בנוסף הם אי שליליים: עבור הווקטור העצמי $g$ של $L^{\text{sym}}$ עם הערך העצמי המתאים $\lambda$ ונניח כי $g=D^{1/2}f$. (אפשר לחשוב על $g$ ו-$f$ כפונקציות ממשיות על הקודקודים $v$.) אז:

$\lambda \ {}=\ {}{\frac {\langle g,L^{\text{sym}}g\rangle }{\langle g,g\rangle }}\ {}=\ {}{\frac {\langle g,D^{-1/2}LD^{-1/2}g\rangle }{\langle g,g\rangle }}\ {}=\ {}{\frac {\langle f,Lf\rangle }{\langle D^{1/2}f,D^{1/2}f\rangle }}\ {}=\ {}{\frac {\sum _{u\sim v}(f(u)-f(v))^{2}}{\sum _{v}f(v)^{2}d_{v}}}\ >\ 0$

כאשר משתמשים במכפלה הפנימית $\langle f,g\rangle =\sum _{v}f(v)g(v)$, סכום כל הקודקודים $v$, ו-$\sum _{u\sim v}$ מסמן סכום על כל הזוגות הלא סדורים של קודקודים סמוכים $\{u,v\}$. הסכום $\sum _{u,v}(f(u)-f(v))^{2}$ נקרא סכום דיריכלה של $f$ כאשר הביטוי ${\frac {\langle g,L^{\text{sym}}g\rangle }{\langle g,g\rangle }}$ נקרא מנת רייליג (Rayleigh quotient) של $g$.

תהא 1 פונקציה המניחה את הערך 1 עבור כל קודקוד. אז $D^{1/2}1$ הוא פונקציה עצמית של$L^{\text{sym}}$ עם ערך עצמי 0.

הערכים העצמיים של מטריצת הלפלסיאן הסימטרית המנורמלת מקיימים $0=\mu _{0}\leq ...\leq \mu _{n-1}\leq 2$. ערכים עצמיים אלו ידועים כספקטרום של מטריצת הלפלסיאן המנורמלת.

מטריצת לפלסיאן מנורמלת של מהלך אקראי

מטריצת לפלסיאן מנורמלת של מהלך אקראי, מוגדרת כך:

$L^{\text{rw}}:=D^{-1}L$

כאשר $D$ היא מטריצת דרגות. מאחר שמטריצת הדרגות $D$ היא אלכסונית, המטריצה ההופכית שלה $D^{-1}$ היא מטריצה אלכסונית גם כן, שהערכים על האלכסון שלה הם ההופכיים של האיברים המתאימים להם ב-$D$. עבור קודקודים מבודדים (בעלי דרגה 0), נהוג להגדיר את האיבר המתאים $L_{i,i}^{\text{rw}}$ ל-0. התוצאה של הגדרה כזו היא תכונה יפה שמספר הערכים העצמיים שערכם הוא 0 שווה למספר רכיבי הקשירות בגרף. איברי המטריצה $L^{\text{rw}}$ נתונים על ידי:

$L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if}}\ i=j\ {\mbox{and}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}$

השם מטריצת לפלסיאן מנורמלת של מהלך אקראי בא מהעובדה כי מטריצה זו היא פשוט מטריצת המעברים של מהלך מקרי בגרף. לדוגמה $e_{i}$ וקטור הבסיס הסטנדרטי ה-i, אז $x=e_{i}L^{\text{rw}}$ הוא וקטור הסתברות המתאר את ההתפלגות של מיקום מהלך אקראי לאחר צעד אחד מהקודקוד $i$, כלומר $x_{j}=\mathbb {P} (v_{i}\to v_{j})$. באופן כללי יותר אם $x$ הוא התפלגות של מיקום מהלך אקראי בקודקודי הגרף אז $x'=x(L^{\text{rw}})^{t}$ היא ההתפלגות של מיקום מהלך אקראי לאחר $t$ צעדים.

ניתן לראות כי:

$L^{\text{rw}}=D^{-{\frac {1}{2}}}\left(I-L^{\text{sym}}\right)D^{\frac {1}{2}}$,

$L^{\text{rw}}$ דומה למטריצת הלפלסיאן המנורמלת (הסימטרית) $L^{\text{sym}}$. מסיבה זו, אפילו אם $L^{\text{rw}}$ אינה הרמיטית באופן כללי, יש לה ערכים עצמיים ממשיים.

לעיתים מתייחסים למטריצה $I-D^{-1}A$ גם כן כמטריצת לפלסיאן של הילוך מקרי מאחר שהתכונות שלה דומות לאלו של מטריצת לפלסיאן דיסקרטית סטנדרטית מתחום האנליזה הנומרית.

שימושים

למטריצת הלפלסיאן שימושים רבים בתורת הגרפים ובאלגוריתמים.

עצים פורשים בגרף

ערך מורחב – משפט קירכהוף

יהא $G$ גרף קשיר בעל $n$ קודקודים, ויהיו $\displaystyle \lambda _{1},\lambda _{2},...,\lambda _{n-1}$ ערכים עצמיים שונים מאפס של הלפלסיאן $L$ של $G$. אזי $\displaystyle t(G)$, מספר העצים הפורשים של $G$, הוא:

$t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}$

במילים אחרות, מספר העצים הפורשים שווה למינור של $L$.

אי שוויון צ'יגר

קבוע צ'יגר (Cheeger) הוא מדד מספרי האם גרף מכיל "צוואר בקבוק". הקבוע מוגדר על ידי $h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}}$ (מהי קבוצת הקודקודים בגודל של עד חצי ממספר הקודקודים, שעבורה מספר הקשתות שיצאו ממנה ביחס לגודל שלה יהיה מינימלי).

הערך העצמי הקטן ביותר של מטריצת לפלסיאן $L$ שאינו 0 נקרא הפער הספקטרלי. עבור גרף $G$ שהוא $d$ רגולרי קיים קשר בין הפער הספקטרלי לקבוע זה, שהוכח על ידי טנר, ובאופן בלתי תלוי על ידי נוגה אלון וויטלי מילמן:

${\tfrac {1}{2}}(\lambda _{2})\leq h(G)\leq {\sqrt {2(\lambda _{2})}}$.

אשכול ספקטרלי

בתחום של ניתוח אשכולות (Clustering), מתעניינים בבעיה שבהינתן דוגמאות $x_{1},...,x_{m}$ (כאשר $x_{i}\in \mathbb {R} ^{n}:i\in [1,m]$), מספר $k$ ופונקציית דמיון רוצים למצוא חלוקה הדוגמאות ל-$k$ קבוצות כך שהדוגמאות בכל קבוצה יהיו דומות זו לזו.

אחת ממשפחות האלגוריתמים הנפוצה לפתרון בעיות מסוג זה היא אלגוריתמים של אשכול ספקטרלי (Spectral clustering). אלגוריתמים אלו מבוססים על בניית גרף דמיון, גרף שבו כל דוגמה היא קודקוד, וכל קשת מחברת בין דוגמאות דומות (בחירה אפשרית לכך היא חיבור קודקודים שעבורם פונקציית הדמיון החזירה ערך קטן מערך מסוים). על פי הגרף מחשבים מטריצת לפלסיאן (קיימות גרסאות שונות של אשכול ספקטרלי העושות שימוש במטריצת לפלסיאן מנורמלת), ותוך שימוש בווקטורים העצמיים שלה מחפשים חלוקה לקבוצות באמצעות אלגוריתם k-מרכזים (k-means).

קישורים חיצוניים

• גדי אלכסנדרוביץ', משפט המטריצה-עץ של קירכהוף, באתר "לא מדויק", 13 בספטמבר 2011
• מטריצת לפלסיאן, באתר MathWorld (באנגלית)   

• Daniel A. Spielman, Algorithms, Graph Theory, and Linear Equa-tions in Laplacian Matrices, Proceedings of the International Congress of Mathematicians. Hyderabad, India, 2010

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

30050115מטריצת לפלסיאן