הבנת אלגוריתם לוביין לפי תחומי מתמטיקה שונים

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

הקסם שלו נובע מיוריסטיקה במקום יומרה לפתור אופטימלית ונוטה להתנהג כמו O(n log n), כש-n מספר הצמתים, ברשתות טיפוסיות דלילות. להבדיל, חלוקה אופטימלית לקהילות, ע"י מקסום מדד המודולריות, היא בעיה NP-hard. הוא עובד בשני שלבים איטרטיביים: הוא מעביר צמתים בין קהילות שכנות כדי לשפר את המודולריות המקומית. ואז הוא מבצע אגרגציה, מקבץ כל קהילה לצומת-על, ומתחיל את התהליך מחדש על רשת קטנה ודחוסה יותר.

נתאר את שני השלבים הפשוטים האלה מבעד למשקפיים של תחומים שונים במתמטיקה.

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

במשקפיים של אלגברה ליניארית, ניתן לארוז את כל חישובי הסטייה של הרשת מהממוצע האקראי לתוך מטריצה ממורכזת אחת, מטריצת המודולריות. לפתע, ספירת הקשתות הופכת לחישוב של זוויות; ההחלטה האם להעביר צומת לקהילה היא למעשה מכפלה סקלרית בין וקטור הצומת לווקטור הקהילה. כאשר הזווית בין הווקטורים חדה והמכפלה חיובית, זה אומר שהצומת והקהילה מתואמים מבנית ומצביעים לאותו כיוון. מה לגבי השלב השני של יצירת צמתי-על? זו אינה סתם פעולת קיבוץ, אלא פעולת הפחתת מימדים למטריצה, שנועדה לשמר את הערכים העצמיים הגבוהים שלה. במקום לחשב וקטורים עצמיים באופן קלאסי בסיבוכיות של (O(n³ , האלגוריתם החמדן הזה מבצע אופטימיזציה ישירה על המרחב הדיסקרטי שדוחפת אותו לאותם כיוונים אלגבריים.

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

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

הבנת אלגוריתם לוביין לפי תחומי מתמטיקה שונים

דברו איתי:

שלמה יונה

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

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

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