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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

הגדרות

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

L=DA,

כאשר:

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

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

התאים במטריצת L נתונים על ידי: Li,j:={deg(vi)if i=j1if ij and vi is adjacent to vj0otherwise כאשר deg(vi) היא הדרגה של הקודקוד ה-i.

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

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

Lsym:=D1/2LD1/2=ID1/2AD1/2,

התאים ב-Lsym נתונים על ידי:[1]

Li,jsym:={1if i=j and deg(vi)01deg(vi)deg(vj)if ij and vi is adjacent to vj0otherwise.

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

האיברים של Lrw נתונים על ידי: Li,jrw:={1if i=j and deg(vi)01deg(vi)if ij and vi is adjacent to vj0otherwise.

דוגמה

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

גרף מטריצת דרגות מטריצת שכנויות מטריצת לפלסיאן
(200000030000002000000300000030000001) (010010101010010100001011110100000100) (210010131010012100001311110130000101)

תכונות

עבור גרף לא מכוון G, שמטריצת הלפלסיאן שלו היא L עם ערכים עצמיים λ0λ1λn1:

מטריצת החילה

עבור גרף G=(V,E), שבו V הם קבוצת הקודקודים ו-E היא קבוצת הקשתות, מטריצת החילה (Incidence matrix)‏ M היא מטריצה בגודל |E|×|V| שהתא ה-Mev עבור e=(i,j)E ו-vV נתון על ידי:

Mev={1,ifv=i1,ifv=j0,otherwise.

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

L=MTM

כאשר MT הוא שחלוף השורות והעמודות של M.

הפירוק לווקטורים עצמיים של מטריצת הלפלסיאן L, עם וקטורים עצמיים עם גודל יחידה 𝐯i וערכים עצמיים λi:

λi=𝐯iTL𝐯i=𝐯iTMTM𝐯i=(M𝐯i)T(M𝐯i).

מאחר ש-λi יכול להיכתב כמכפלה פנימית של הווקטור M𝐯i עם עצמו, זה מראה כי λi0 ולכן כל הערכים העצמיים של L הם לא שליליים.

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

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

Lsym:=D1/2LD1/2=ID1/2AD1/2

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

ניתן לחשב אותה כך: Lsym=SS*, כאשר S היא מטריצה שבה השורות מאונדקסות על יד הקודקודים והעמודות על פי הקשתות של הגרף כך שבעמודה המתאימה לקשת e=(u,v), התא בשורה u הוא הוא בעל ערך 1du, ובשורה המתאימה ל-v הוא בעל ערך 1dv, ו-0 ביתר התאים. (הערה: S* מייצג את השחלוף של S).

כל הערכים העצמיים של מטריצת הלפלסיאן המנורמלת ממשים ואי שליליים. אפשר להראות זאת כך: מאחר ש-Lsym היא סימטרית, הערכים העצמיים בה ממשיים. בנוסף הם אי שליליים: עבור הווקטור העצמי g של Lsym עם הערך העצמי המתאים λ ונניח כי g=D1/2f. (אפשר לחשוב על g ו-f כפונקציות ממשיות על הקודקודים v.) אז:

λ = g,Lsymgg,g = g,D1/2LD1/2gg,g = f,LfD1/2f,D1/2f = uv(f(u)f(v))2vf(v)2dv > 0

כאשר משתמשים במכפלה הפנימית f,g=vf(v)g(v), סכום כל הקודקודים v, ו-uv מסמן סכום על כל הזוגות הלא סדורים של קודקודים סמוכים {u,v}. הסכום u,v(f(u)f(v))2 נקרא סכום דיריכלה של f כאשר הביטוי g,Lsymgg,g נקרא מנת רייליג (Rayleigh quotient) של g.

תהא 1 פונקציה המניחה את הערך 1 עבור כל קודקוד. אז D1/21 הוא פונקציה עצמית שלLsym עם ערך עצמי 0.

הערכים העצמיים של מטריצת הלפלסיאן הסימטרית המנורמלת מקיימים 0=μ0...μn12. ערכים עצמיים אלו ידועים כספקטרום של מטריצת הלפלסיאן המנורמלת.

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

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

Lrw:=D1L

כאשר D היא מטריצת דרגות. מאחר שמטריצת הדרגות D היא אלכסונית, המטריצה ההופכית שלה D1 היא מטריצה אלכסונית גם כן, שהערכים על האלכסון שלה הם ההופכיים של האיברים המתאימים להם ב-D. עבור קודקודים מבודדים (בעלי דרגה 0), נהוג להגדיר את האיבר המתאים Li,irw ל-0. התוצאה של הגדרה כזו היא תכונה יפה שמספר הערכים העצמיים שערכם הוא 0 שווה למספר רכיבי הקשירות בגרף. איברי המטריצה Lrw נתונים על ידי:

Li,jrw:={1if i=j and deg(vi)01deg(vi)if ij and vi is adjacent to vj0otherwise.

השם מטריצת לפלסיאן מנורמלת של מהלך אקראי בא מהעובדה כי מטריצה זו היא פשוט מטריצת המעברים של מהלך מקרי בגרף. לדוגמה ei וקטור הבסיס הסטנדרטי ה-i, אז x=eiLrw הוא וקטור הסתברות המתאר את ההתפלגות של מיקום מהלך אקראי לאחר צעד אחד מהקודקוד i, כלומר xj=(vivj). באופן כללי יותר אם x הוא התפלגות של מיקום מהלך אקראי בקודקודי הגרף אז x=x(Lrw)t היא ההתפלגות של מיקום מהלך אקראי לאחר t צעדים.

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

Lrw=D12(ILsym)D12,

Lrw דומה למטריצת הלפלסיאן המנורמלת (הסימטרית) Lsym. מסיבה זו, אפילו אם Lrw אינה הרמיטית באופן כללי, יש לה ערכים עצמיים ממשיים.

לעיתים מתייחסים למטריצה ID1A גם כן כמטריצת לפלסיאן של הילוך מקרי מאחר שהתכונות שלה דומות לאלו של מטריצת לפלסיאן דיסקרטית סטנדרטית מתחום האנליזה הנומרית.

שימושים

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

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

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

יהא G גרף קשיר בעל n קודקודים, ויהיו λ1,λ2,...,λn1 ערכים עצמיים שונים מאפס של הלפלסיאן L של G. אזי t(G), מספר העצים הפורשים של G, הוא:

t(G)=1nλ1λ2λn1

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

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

קבוע צ'יגר (Cheeger) הוא מדד מספרי האם גרף מכיל "צוואר בקבוק". הקבוע מוגדר על ידי h(G)=min0<|S|n2|(S)||S| (מהי קבוצת הקודקודים בגודל של עד חצי ממספר הקודקודים, שעבורה מספר הקשתות שיצאו ממנה ביחס לגודל שלה יהיה מינימלי).

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

12(λ2)h(G)2(λ2).

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

בתחום של ניתוח אשכולות (Clustering), מתעניינים בבעיה שבהינתן דוגמאות x1,...,xm (כאשר xin:i[1,m]), מספר k ופונקציית דמיון רוצים למצוא חלוקה הדוגמאות ל-k קבוצות כך שהדוגמאות בכל קבוצה יהיו דומות זו לזו.

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

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

הערות שוליים

  1. Laplacian Matrix ב-mathworld
  2. Algebraic Connectivity ב-mathworld
  3. F. R. K. Chung, Laplacians of graphs and Cheeger inequalities
  4. אולריקה פון לוקסבורג, A Tutorial on Spectral Clustering, מכון מקס פלנק
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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