אלגוריתם Leiden למציאת קהילות בגרף

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

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

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

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

לשני האלגוריתמים סיבוכיות זמן זהה (O(m log n. עם זאת, במבחני ביצועים אמפיריים, Leiden מהיר יותר בכ- 20%-150% ומשיג ציוני מודולריות גבוהים יותר.

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

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

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

עדיין חשוב להבין לעומק את לוביין גם אם בסופו של דבר משתמשים בליידן.

אלגוריתם Leiden למציאת קהילות בגרף

צריכים עזרה עם אלגוריתמים בגרפים? שיפורי אלגוריתמים? מחקר אלגוריתמי יישומי? צריכים עזרה עם גילוי ומניעת הונאות? דברו איתי:

שלמה יונה

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

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

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