משמעויות אלגוריתם לוביין לפי גישות מתמטיות שונות

6 days ago • Edited • Visible to anyone on or off LinkedIn

אתמול כתבתי על אלגוריתם Louvain למציאת קהילות בגרפים. היום אנסה להציע משמעות סטטיסטית, משמעות אלגברית ומשמעות גיאומטרית. אבל נפתח בהגדרות כדי שנבין על מה מדברים.

מודולריות, Q, היא ערך סקלארי לרוב בין 0.5- ל-1 שמודד עד כמה הקהילות שמצאנו טובות יותר מאשר חלוקה אקראית של אותו הגרף. 

 Q = (1/2m) Σᵢ,ⱼ [Aᵢⱼ - (kᵢkⱼ / 2m)] δ(cᵢ, cⱼ)

צומת i שכן של צומת j אם יש קשת שמחברת ביניהם.

Σ: סימן הסכימה, סיגמא.

Aᵢⱼ: מטריצת הסמיכויות. בתא ij משקל הקשת שמחברת בין צומת i לבין צומת j. משקל 0 אין קשת.

kᵢ, kⱼ: סכום משקלי הקשתות המחוברות לצומת i ולצומת j בהתאמה. הדרגה של הצומת. אם המשקלים תמיד 1 אז זה פשוט כמה צמתים מחוברים כשכנים באמצעות קשתות. הערכים המותרים הם אי שליליים כי הם מציינים מידת קרבה והערכים הם 0 כאשר אין קרבה או ערך גדול מאפס. 

m: סכום משקלי הקשתות בגרף כולו. לכן 2m הוא סכום כלל הדרגות.

cᵢ, cⱼ: הקהילה אליה שייך צומת i והקהילה אליה שייך צומת j.

δ(cᵢ, cⱼ): פונקציית דלתא של קרונקר. מחזירה 1 אם שני הצמתים באותה קהילה, ו-0 אחרת.

(kᵢkⱼ / 2m): התוחלת לקיום קשת בין i ל-j אילו הקשתות בגרף היו מחולקות באקראי לחלוטין, תוך שמירה על דרגות הצמתים.

אנחנו סוכמים רק על זוגות צמתים שנמצאים באותה קהילה (בגלל ה-δ). עבור כל זוג כזה, אנחנו בודקים האם הקשר ביניהם (Aᵢⱼ) חזק יותר ממה שהיינו מצפים לראות באופן אקראי (kᵢkⱼ / 2m). אם כן, זה תורם חיובית למודולריות.

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

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

במודל האקראי הזה, ההסתברות שחצי-קשת מצומת i תתחבר לחצי-קשת מצומת j היא פרופורציונלית לדרגות שלהם. התוחלת של מספר הקשתות בין i ל-j היא kᵢkⱼ / 2m.

הביטוי Aᵢⱼ - (kᵢkⱼ / 2m), בנוסחת המודולריות Q מודד את השארית. אם יש קשת בפועל Aᵢⱼ = 1 אבל התוחלת נמוכה, אז ההפרש חיובי וגדול וזו הפתעה סטטיסטית שמעידה על קשר אמיתי. האלגוריתם מנסה למקסם את סכום ההפתעות הסטטיסטיות בתוך הקהילות ומתעלם מהקשרים הבין-קהילתיים.

המשמעות האלגברית עוזרת לתשתית החישובית ולייעול של האלגוריתם. אפשר לארוז את חישוב המודולריות לתוך מטריצה אחת שנקראת מטריצת המודולדיות, שנסמנה ב-B:

Bᵢⱼ = Aᵢⱼ - (kᵢkⱼ / 2m)

נניח שאנו רוצים לחלק את הגרף ל-c קהילות. נגדיר מטריצת שיוך S בגודל n × c, כך ש-Sᵢ꜀ = 1 אם צומת i שייך לקהילה c, ו-0 אחרת. כעת, ניתן לכתוב את המודולריות כ-טרייס של הכפלת מטריצות, שהיא למעשה תבנית ריבועית

Q = (1 / 2m) Tr(Sᵀ B S)

מציאת המטריצה S שממקסמת את Q היא NP-hard. הגישה הקלאסית באמצעות Spectral Clustering הייתה למצוא את הווקטורים העצמיים המובילים של המטריצה B. הבעיה היא שפירוק לערכים עצמיים הוא בסיבוכיות O(n³). במקום לחשב וקטורים עצמיים גלובליים, האלגוריתם החמדן שלנו משנה רכיב אחד בודד במטריצה S בכל צעד, מעביר צומת מקהילה לקהילה, ובודק אם התבנית הריבועית גדלה. זה מה שמאפשר לו לרוץ בסיבוכיות O(n log n).

המשמעות הגיאומטרית היא של שינוי קנה מידה והיא באה לידי ביטוי בשלב השני של האלגוריתם, שלב האגרגציה, שלב הצבירה, שם האלגוריתם מכווץ קהילות לצמתי-על. 

אפשר להתייחס לגרף כאל סעפת בדידה, Discrete Manifold, במרחב רב-מימדי. קהילות הן אזורים צפופים, אשכולות, Clusters, במרחב הזה. האגרגציה היא למעשה פעולת הטלה של המרחב למימד נמוך יותר. אנו ממירים ענן של צמתים המקובצים קרוב זה לזה מבחינה טופולוגית, לנקודה גיאומטרית אחת, מרכז כובד. הפחתת מימדים, אם תרצו.

משקלי הקשתות החדשות בגרף המכווץ, סכום הקשתות בין הקהילות, משמרים את המרחקים הגיאומטריים, הטופולוגיים היחסיים בין מרכזי הכובד. האלגוריתם מתחיל בפתרון בעיות לוקאליות ברזולוציה גבוהה, שכנים ישירים, ובכל איטרציה הוא עושה זום-אאוט, עד שהוא ממפה את המאקרו-גיאומטריה של הרשת.

משמעויות אלגוריתם לוביין לפי גישות מתמטיות שונות

צריכים עזרה עם אלגוריתמים בגרפים? שיפור אלגוריתמים? מחקר אלגוריתמי יישומי? גרף זהויות? Identity Resolution?

דברו איתי:

שלמה יונה

מייסד ומדען ראשי, מתמטיקאי מחקר ופיתוח בע"מ

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

פודקאסט על החברה ועליי, שלמה יונה, ואופן העבודה שלנו ואיתנו: A technical deep dive about Mathematic.ai