SNA קלאסיקות: Community structure in social and biological networks או: חלוקת רשת לקהילות

מאמר זה, של Girvan&Newman משנת 2001, היה כנראה בין המאמרים הראשונים שעסקו בכיצד למצוא קהילות ברשת בשיטה מוכוונת נתונים (data-oriented).

עד אז, חלוקה לקהילות נעשתה בצורה הירארכית (hierarchical clustering או דנדרוגרמות/dendrograms) כשההגיונות המובילים היו:

1. רשת היא הירארכית/מסודרת וכך גם הקהילות בה.

2. קהילה תוגדר ע"י הקשרים החזקים שבה (Bottom-Up, כלומר, הבניית הקהילה תיעשה ע"י מציאת הקשרים החזקים של הצמתים והוספה הדרגתית של קשרים חלשים יותר לתרשים).

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

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

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

1. זמן חישוב ארוך (betweenness הוא מדד ארוך לחישוב).

2. תוצאות בעייתיות על רשתות צפופות.

בעיות אלו ייפתרו בהמשך ע"י שימוש במודולאריות (Modularity), תחום שניומן-עצמו יפתח ב-2004. האלגוריתם אולי המפורסם ביותר ממשפחת המודיולאריטי הוא הלובאין (Louvain Algorithm), שלמרבה האירוניה, חוזר לנקודת המבט הישנה של בניית קהילות Bottom-Up.

ובכל זאת, המאמר הנ"ל שם על המפה את הרעיון של ניתוח קהילתי לייצור תובנות על רשת והביא לגל של אלגוריתמיקה בתחום זה.