(ר' קישורים בטקסט)
מה מתרחש (:
אני אסף שפירא וזה נטפריקס – הפודקאסט העברי הראשון למדע הרשתות.
בפרק על ה-Power law למדנו שרשתות אינן אקראיות כפי שחשבו בעבר אלא פועלות לפי חוקים. אם הגדרנו את ה-Power Law כחוק מס' 1 הרשת הרי שחוק מס' 2 הוא: רשתות מתקהלות. למה הכוונה?
הסתכלות קרובה על המבנה הפנימי של הרשת מלמדת כי הרשת בנויה מצבירים צפופים המחוברים בינהם. צבירים אלו מכונים קהילות או communities, אם אתם חוקרי רשת, או קלאסטרים, אם אתם יותר בקטע של מדעי מחשב.
הבנת אותן הקהילות תאפשר לנו לנתח- בקלות וביעילות- כל גודל של רשת, לגלות דברים שלא ידענו שלא ידענו (מה שנקרא, unknown unknown) ולספר סיפור מעניין על הדאטה שלנו. כל זאת ומה הקשר לכרובית, נגלה בפרק הזה.
אז בואו נתחיל.
אז מדוע נוצרים צבירים או קהילות ברשת?
נגיד שאנחנו מגיעים למסיבה אצל חבר. אנחנו נכנסים בדלת, ולא מזהים אף אחד. כשפתאום חבר מהצד השני של החדר עושה לנו שלום. אנחנו מצטרפים לחבורה שלנו אותה אנחנו מכירים ממזמן מהיחידה בצבא. במבט מסביב לחדר אנחנו רואים עוד חבורות: חבר'ה שעובדים יחד על איזשהו סטארטאפ, חבר'ה מהאוניברסיטה, חבורה של בנות שהרגע הגיעו וחבורה של חבר'ה שאני בכלל לא מכיר ולא מבין מה הם עושים פה. נוצרו לנו באופן טבעי צבירים של חבורות שלכל אחת מהן מכנה משותף: עבודה או לימודים משותפים, מגדר, או סתם מוזרות כללית.
הצבירים האלה נוצרו לפי היגיון של הומופיליה (או דומות, מלשון: "דומה") שגורמת לצמתים לחבור זה לזה ולקיים בינהם הרבה אינטראקציות.
בדוגמא מפרק קודם, ניתחנו את הסוציוגרמות או שרטוטי הרשתות החברתיות של מורנו. נזכיר שמורנו,
כפסיכולוג חברתי, חקר את קשרי החברות של תלמידים בתוך כיתה. בשלב מסויים במעקב אחרי הקשרים ראה מורנו שבכיתה ג'-ד', הרשת מתחלקת ל-2 קהילות עם קשר בודד בינהן. למעשה, הרשת של מורנו התפצלה לקהילות מגדר. בהערת אגב, המחקר נעשה בשנות ה-30 של המאה ה-20 וכשהצגתי אותו למורים ב-2019 הם ציינו שלמיטב ניסיונם, כיום התופעה הזאת מתרחשת מוקדם יותר.
ברשתות אנושיות, יש הרבה אפשרויות להומופיליה: שפה, דת, מוצא אתני, דעות משותפות ועוד, אבל הרכיב ההומופילי כנראה המרכזי ביותר הוא גיאוגרפיה, או ליתר דיוק, קירבה גיאוגרפית.
אם נחשוב על זה רגע, הרי שגם המאפיינים של שפה, דת ומוצא אתני קשורים מאד והרבה פעמים תלויי גיאוגרפיה.
גם דעות משותפות הן לא פעם עניין של גיאוגרפיה. למשל, ניתן להניח שהגרעין הקשה של תומכי ישראל הוא, ובכן... בישראל.
כך גם בדוגמא מפרק העולם הקטן. כזכור, מילגרם, פסיכולוג חברתי ידוע, בדק כמה תחנות יצטרך לעבור מכתב שרשרת ממקור רנדומלי ליעד רנדומלי, דרך חברים משותפים. השרשראות של המכתבים שיעדן היה בסמוך לתחילתן, כלומר שהיו בסמיכות גיאוגרפית, היו קצרות יותר ומהירות יותר.
אבל מה בעידן הרשתות החברתיות שאנו נמצאים בו? ההתפתחויות הטכנולוגיות כיום מאפשרות לכאורה קשרים חוצי עולם באותה קלות בה מתאפשרים קשרים סמוכים גיאוגרפית. האם עידן ההומופיליה הגיאוגרפית לא מגיע לקיצו?
הרי תיאורטית, אני יכול להציע חברות בפייסבוק באותה קלות למישהו שגר לידי או לאסקימואי באלסקה (יש לומר אינואיט). הענין הוא שהסיכוי שזה יקרה הוא כנראה נמוך לאין שיעור מהסיכוי שאהיה חבר של מישהו שחולק איתי את אותו מרחב.
אני בהחלט יכול להיות קשור לגורמים בחו"ל, שלא קרובים אלי, למשל בקשרי עבודה או אהדה לקבוצת ספורט מסויימת (מישהו אמר גרין ביי פאקרס?) והסיבה שנהיה בקשר היא הומופיליה על רקע עבודה או אידיאולוגיה למשל, אך קשרים אלו יהיו לרוב מעטים יותר וחלשים יותר.
כך למשל, אני מעריך שאם נחלק את רשת פייסבוק לקהילות נקבל קהילות עם הומופיליה גיאוגרפית חזקה: קהילת ישראל, קהילת צרפת, ספרד וכו'.
אך מה לגבי איזור הגבול בין המדינות, המכונה איזור הספר?
אם קירבה גיאוגרפית היא כה משמעותית, האם נקבל קהילות ספר? התשובה היא כנראה שלא.
גבולות נראים, ולא נראים, מגבילים את ההומופיליה הגיאוגרפית, למשל במקרה של מדינות ע"י שפה. מה שאומר שגיאוגרפיה היא תנאי הכרחי אך לא מספיק וללאומיות משקל חזק, לשמחת הסוכנות היהודית אם עדיין לא פורקה.
כך למשל פורסמה בניו יורק טיימס ב-2018 מפה אינטראקטיבית בה ניתן לראות איפה נמצאים החברים
בפייסבוק של אנשים במדינות השונות בארה"ב. לאור כל מה שאנחנו יודעים עכשיו, לא נתפלא שרובם המכריע של החברים היו בסמיכות ג"ג גבוהה, אבל הקשרים ירדו באופן תלול מאד ברגע שנחצו הגבולות של המדינה.
דוגמא מרתקת אחרת בהקשר גבולות הוא מחקר רשתי של כנופיות בלוס אנג'לס שפורסם ע"י ראדיל ב-2010 בו הראה שהכביש המהיר בפאסדינה משמש כגבול פיזי ורשתי בין הכנופיות.
דוגמא לגבולות ארגוניים זכורה לי מתקופת הצבא כשהחלו הניסיונות הראשוניים לייצר צוותים משולבים ממספר יחידות מתוך נקודת הנחה נכונה לכשעצמה שכשמשלבים מספר דיציפלינות יחד, התוצר המתקבל הוא שלם וטוב יותר.
חלק מהשותפים בתחילת הדרך הביעו תסכול מכך שלמרות הישיבה המשותפת, עדיין היו חסמים בעבודה והיעדרה של תחושת שותפות. לעיתים קרובות המשתתפים לא ראו עצמם כחלק מצוות אלא כנציגים של המסגרת הארגונית, או בשפה חופשית יותר, קורבנות אדם לניסיון של המנהלים להראות שיתוף פעולה. לפיכך נדרשה גם רפורמה מבנית לצד ההתארגנות הפיזית-גיאוגרפית. למתענינים בנושא, מצ"ב מאמר מגיליון "בין הקטבים" העוסק בניסיון לשת"פ בצורה מקוונת.
אז חלוקת הרשת לקהילות מראה כיצד בנויה הרשת ואת ההיגיון ההומופילי מאחוריה. אז איך זה עוזר לנו?
למשל לצרכי תיוג. כשנרצה לתייג הרבה דאטה, הקהילות יאפשרו לנו לתת לייבלים לחלקים נרחבים ברשת. נוכל גם לראות איזה לייבלים מרכזיים יותר וכמובן לאיזה לייבלים הם קשורים יותר ולאיזה פחות.
דוגמא מקורית לשימוש בחלוקה לקהילות בעולם הטקסט, ניתן למצוא במחקר מ-2012 שמומן ע"י הצבא האמריקאי שרצה המלצות למתכונים לפי רכיבים. המחקר הבנה כרשת את הרכיבים מיותר מ-46 אלף מתכונים, כשקשר בין רכיבים הוא הופעה משותפת במתכון. הקהילות ברשת התחלקו לפי הומופיליה של טעמים: מלוח, חריף ומתוק (קינוחים) ובעזרת אלגוריתמיקת SNA, החוקרים הצליחו גם להראות איזה רכיב ניתן להחליף עם איזה רכיב וכך לאפשר גמישות במטבח.
דוגמא מעולם אחר היא עולם האקדמיה. מאמרים רבים מדגימים הומופיליה בקהילות על סמך רשת מאמרים אקדמאיים. ניתן להבנות את מאגר המאמרים האקדמאיים כרשת ע"י קישור כל מאמר (צומת) למאמרים שציטטו אותו.
כשנחלק את הרשת לקהילות, הקהילות יתחלקו לפי תחומי העניין השונים המעסיקים את האקדמיה (קהילת פיסיקאים, קהילת ביולוגים וכו') שכן ההומופיליה באה לידי ביטוי בהעדפה לצטט מאמרים הקרובים לתחום העיסוק של המאמר. מאמרים בתחום הכימיה יצטטו לרוב מאמרים בכימיה. לעיתים הם יצטטו גם מאמרים מתחום הביולוגיה או מדעי המחשב, אבל הקשרים החזקים שלהם יהיו לתחום עיסוקם.
אחד מהדברים המעניינים במעבר על קהילות זה כמובן האנומליות – המקומות בהם ההומופיליה שונה משאר הרשת. למה הכוונה?
ניקח כדוגמא את רשת הפייסבוק. נניח שהחלוקה ההומופילית הנפוצה היא כפי שכבר ציינו, חלוקה גיאוגרפית למדינות. זה יהיה מאד מעניין לגלות קהילה מרכזית שההומופיליה בה היא אחרת, נגיד קהילת אוהבי חתולים. זה אומר שאהבת חתולים חזקה יותר אצל אותם אנשים מאשר הזהות הגיאוגרפית שלהם, ושהיא מספיק מענינת להיות מרכזית.
אם נרצה להשתלט על העולם, נוכל לעבור מקהילה גיאוגרפית לקהילה גיאוגרפית ולחפש בכל אחת את המשפיענים שבה או שנוכל לעשות קיצור דרך ולהיעזר בקהילת אוהבי החתולים החובקת עולם בכדי להפיץ את המסר באופן גלובאלי. אני בטוח שהחתולים יאשרו זאת.
אז למדנו שכל רשת מתקהלת לקהילות ולכל קהילה יש מגדיר הומופילי אבל יש לקהילות ברשת עוד תכונה די מדהימה. הן פרקטליות. מה זה אומר?
במבט ראשון הקהילות נראות כמו אוסף של צבירים אקראיים, אבל צלילה לתוכם תגלה שצבירים אלו מורכבים מצבירים קטנים יותר, שגם הם צפופים ומחוברים בינהם וכך הלאה וכך הלאה. זהו המבנה הפרקטלי של הרשת. אמרתי פרקטל, אמרתי כרובית.
מעבר לזה שכרובית היא המילה המצחיקה ביותר, היא דוגמא טובה למבנה הפרקטלי של הרשת.
לא יודע כמה יצא לכם לבחון כרובית מקרוב. מרחוק היא נראית כמו גוש לבן אבל במבט מקרוב ניתן לראות
שהיא בנויה ממספר גושים וגם גושים אלו בנויים מגושים קטנים יותר וכן הלאה וכל אחד מהם משמר את המבנה של הכרובית המקורית בכל רזולוציה.
לספקנים אני מציע לגשת למקרר ולהעיף מבט במגירת ירקות. כרובית – לא מה שחשבתם.
הגושים האלה נקראים פרקטליים ונרחיב עליהם בפרק בנושא הרשת הדינאמית. מה הקשר בין כרובית לרשת דינאמית? תישארו במתח.
כמו שמבנה הכרובית נשמר בכל רזולוציה, כך גם המבנה של הרשת נשמר בכל רזולוציה, בזכות הקהילות, כלומר, מבנה הרשת עונה להגדרתו של ברבאשי למבנה שהוא Scalefree.
כפי שראינו בפרק הקודם, התפלגות ה-Power Law נשמרת בכל רזולוציה בה נסתכל על הרשת וכך גם במקרה של הצבירים. בכל צביר מסתתר Power Law קטן: יהיו בו מעט צמתים מרכזיות ורוב הצמתים בעלי קשרים בודדים.
גם כשנפרק את הרשת לצבירים ואת הצבירים לתת-צבירים וכן הלאה, התפלגות ה-power law בתוכם תישמר. בכל רשת.
אז איך נחלק את הרשת לקהילות?
ראשית, נצטרך לתת הגדרה למהי קהילה רק כדי לגלות שבעצם, אין הגדרה מדעית כזאת.
נבדיל שניה בין רכיבי הקשירות, עליהם דיברנו בפרק על העולם הקטן, ובין קהילות. נזכיר שרכיבי הקשירות הם אותם "איים" ברשת ובניגוד לקהילות, יש להם הגדרה ברורה: מי שקשור אליהם נמצא ברכיב ומי שלא – לא. האיים עצמם יכולים להיות מורכבים מקהילה אחת או מספר קהילות, אבל מה מגדיר את הגבולות בין הקהילות שברכיב? אז נרחיב על זה רבות במסגרת הפרק אך לצורך הענין נסתפק בהגדרה הרווחת שהיא שכמות הקשרים בתוך קהילה גדול מכמות הקשרים היוצאים ממנה, כך שהקשתות צפופות יותר בתוך הקהילה. במילים אחרות, הקשרים בתוך הקהילה יהיו רבים וחזקים והקשרים לצמתים מחוץ לקהילה יהיו מעטים וחלשים.
אמרנו קשרים חלשים אמרנו גראנובטר. מאמרו של גראנובטר (Granovetter) מ-1973:
"עוצמתם של הקשרים החלשים", זכה למעל ל-52,000 ציטוטים והוא אולי המאמר המצוטט ביותר בתחום הרשת.
מאמרו נחשב פורץ דרך שכן עד אז המחקר עסק בעיקר בקשרים החזקים של הפרט מתוך הנחה אינטואיטיבית שהם הקשרים החשובים והמשפיעים.
גראנובטר במאמרו מזהיר מפני אינטואיציות ועושה שימוש במידע אמפירי כדי לבחון כיצד אנשים מוצאים עבודה חדשה ובכך מדגים דווקא את עוצמתם של הקשרים החלשים.
מציאת עבודה היא אירוע מאד משמעותי בחייו של הפרט והאינטואיציה מניחה שלקשרים החזקים של הפרט יהיה חלק משמעותי בכך, למשל הקשרים עם חברים קרובים, משפחה וכד'. גראנובטר הראה שדווקא הקשרים החלשים של הפרט, למשל, מכרים מהעבר כמו מהלימודים או מעבודה קודמת, הם אלו שאיפשרו מציאת עבודה חדשה. הסיבה שהוא נתן לכך זו הסירקולציה של המידע.
מידע חדש, למשל על מקומות עבודה, לא מגיע מקשרים חזקים. הסיכוי שהאנשים הקרובים לנו יחדשו לנו הוא נמוך. דווקא הקשרים החלשים מאפשרים למידע חדש להגיע.
יש במאמר גם תובנות נוספות ופחות מוכרות אך כאלה שעדיין מחזיקות מים גם כחצי מאה לאחר פרסומו.
אחת מהן היא פרדוקס הקשרים החזקים. גראנובטר איבחן שקשרים חזקים מייצרים פרדוקס ברזולוציות שונות של הרשת: במיקרו, הקשרים החזקים יוצרים לכידות בין הצמתים אך במאקרו הם דווקא תורמים לפרגמנטציה של הרשת. לטענתו, נדרש עוד להוכיח פרדוקס זה ובהמשך הפרק נראה האם הוא צדק.
במאמרו של גראנובטר תובנות נוספות אודות הרשת בהן נעסוק בפרק בנושא המודיעין ברשת.
בהערת אגב, בניגוד למאמרים שמפורסמים בימים אלו שבהם מסבירים הכותבים איך כל הקודמים טעו ואיך דווקא המאמר שלהם פורץ דרך משמעותית, גראנובטר במאמרו מרבה לפרגן לחוקרים ולמאמרים אחרים. מה לעשות, תקופה אחרת (:
באותו זמן ממש, בו פורסם מאמרו של גראנובטר, גילה חוקר בשם וויין זאכארי את הפוטנציאל בחלוקת רשת לקהילות במחקרו המפורסם אודות מועדון קראטה.
זאכארי מיפה במשך כמה שנים קשרי חברות במועדון קראטה, בשנות ה-70, שכלל עשרות חברים. כמו בהרבה סרטי קראטה משנות ה70, גם מועדון זה התפצל בעקבות סכסוך בין מדריכים לדוג'ו הטוב ולדוג'ו הרע.
מה ייחד את מחקרו של זאכארי? זאכרי הוא אנתרופולוג אבל הוא עשה שימוש בכלים מתמטיים בשביל למדל את המחקר שלו. זאכארי זיהה שיש אינטריגות במועדון שבאות לידי ביטוי בהעברת מידע בתוך קבוצה ומניעת מידע מקבוצה אחרת. לפיכך, כדי לנתח את זרימת המידע, זאכארי השתמש בשיטה הנקראת max flow/min cut שמשמשת לאופטימיזציה של זרימה בין 2 צמתים ברשת, כשאחד נקרא המקור או ה-source והשני
נקרא היעד או ה-sink. בשיטה זו מתאפשר לזהות צווארי בקבוק בזרימה. זאכארי בחר מדריך אחד כמקור ואת השני כיעד כיוון שהוא זיהה שהתחרות בין שני המדריכים על אופי הדוג'ו גוררת הפצת מידע בתוך קבוצת התומכים של כל מדריך לצד מניעת מידע מהקבוצה השניה. כלומר, זאכארי הניח שצוואר הבקבוק ברשת יהיה הגבול בין 2 הקבוצות, וכך היה. האלגוריתם חילק את גרף הקשרים שמיפה זאכארי בהתאמה כמעט מוחלטת לפיצול הפיזי במועדון, כלומר נתן תוצאה מעולה ביחס ל-groundtruth של המחקר.
החסרון בשיטת ה-min/max למציאת קהילות ברשת הוא שמניחים ידע מוקדם על הרשת. ראשית יש להגדיר מראש יעד ומקור לזרימה, והרי לא תמיד נוכל לסמן 2 צמתים כאלה. בנוסף, החלוקה המתקבלת היא ל-2 קהילות בלבד, מה שלא בהכרח תואם למציאות המורכבת. למרות זאת, זאכארי פרץ דרך בכך שניגש למחקר לא דרך תזות או תאוריות מוקדמות אלא ניסה להראות איזה סיפור הדאטה יכול לספר על הרשת, באמצעות שימוש באלגוריתמיקה.
משום כך מחקר זה משמעותי מאד לעולם הרשת וה-SNA. היתה סיבה חברתית לחלוקה לקהילות. כל קהילה התאפיינה באהדה למדריך מסוים, כלומר, היה היגיון הומופילי בחלוקה לקהילות. אלגוריתם חלוקה לקהילות איפשר לתת פרדיקציה על אותה הומופיליה, כלומר, בהינתן בחירה, במי יבחר כל אחד במועדון לתמוך. בגלל חשיבות הגילוי, מועדון הקראטה של זאכארי הוא מושג מאד מוכר בעולם הרשת. מה שאולי פחות מוכר זה שקיים מועדון הנקרא "המועדון של מועדון הקראטה של זאכארי" שמעניק פרס למדענים בתחום הרשת. התנאי לזכיה הוא שאותו מדען יהיה הראשון לדבר בכנס בנושא רשתות ושהשקף הראשון במצגת שלו יהיה התרשים של מועדון הקראטה של זאכארי.
ויש גם זווית ישראלית, אחד מהזוכים הוא אמיר רובין מאוניברסיטת באר שבע.
זוכה נוסף בפרס הוא מארק ניומן, שיחד עם שותפתו למחקר, גירבן, נתנו תנופה חדשה למחקר הקהילות כשהראו בתחילת שנות ה2000 כיצד למצוא קהילות ברשת בשיטה מוכוונת נתונים (data-oriented).
עד אז, שיטה נפוצה היתה לחלק את הגרף לקהילות ע"י יצירת הירארכיה , כלומר, hierarchical clustering, או דנדרוגרמות, כשהאינטואיציה מאחורי שיטה זו היתה שרשתות הן הירארכיות ולכן כך גם הקהילות.
הבניית הקהילות נעשתה כך: מתחילים את חלוקת הרשת לקהילות ע"י התקדמות מצמתים לאורך הקשרים החזקים שלהם (bottom-up) וקשרים אלו יגדירו את הקהילה.
שיטות נוספות מעולם הקלאסטרינג הצריכו הנחות מוקדמות על הדאטא, גם אם לא קיצוניות כמו במקרה של זאכארי ונביא דוגמאות:
כך למשל, אלגוריתם בשם k-means, מצריך ידע מוקדם לגבי כמות הקהילות אותן נרצה לקבל ברשת, כלומר שיטה זו היא יותר מוכוונת תרחיש (scenario-driven) ואולי קצת supervised. החסרון בה הוא כמובן שהרשת יכולה להתחלק למספר שונה של קהילות ממה שחשבנו. ניתן לשנות את החלוקה על סמך תצפית בתוצאה אבל הדבר דורש איטרציות רבות.
אלגוריתם קלאסטרינג נוסף הוא DBscan, אלגוריתם מ-1996 שזכה להיות אלגוריתם הקלאסטרינג המצוטט ביותר, אבל גם הוא מצריך הנחה מוקדמת לגבי הדאטא. במקרה זה ההנחה הנדרשת היא של כמה מינימום צמתים אמורים להיות בקהילה.
היו גם שיטות שהניחו התפלגות גיאוסיינית של הדאטה אבל מכיוון שאנחנו יודעים שהדאטה שלנו הוא Power law, נסרב להן בנימוס ונמשיך הלאה.
שיטה אחרת היא שיטה בשם k-clique שמגיעה ממשפחת אלגוריתמים שמניחה הנחות קשוחות לגבי איך נראית קהילה.
נגענו בכך שההגדרה של מהי קהילה היא קצת עמומה, אבל יש מצבים מובהקים בהם ניתן להגיד בוודאות שלפנינו נמצאת קהילה. למשל, במקרה של קליקה.
קליקה ( או Clique) היא קבוצה של צמתים ובה כל צומת קשור לכל הצמתים האחרים.
למשל, כדי שקהילה שבה חברים 4 צמתים תהיה קליקה, נדרשות 6 קשתות שיקשרו בינהם, שזה המקסימום האפשרי (ור' תמונה לדוגמאות).
בגלל שבקליקה כל הצמתים מחוברים ואין מקום לקשתות נוספות, היא נקראת לעיתים גם גרף שלם או completed graph.
מקרה קיצוני כזה של קהילה לא כ"כ נדיר כשמדברים על קהילות של 3 חברים, אבל ככל שעולים בכמות החברים, הסיכוי לקליקה פוחת משמעותית (כמה משמעותית? אני שם את הז'יטונים שלי על התפלגות Power Law. תמיד הימור בטוח).
זו למשל אחת הסיבות שהביאה את כותביו של תחקיר עצמאי ב-2019 על התנהלות קמפיין הבחירות בישראל בטוויטר, לחשוד שאחת מהקהילות המצייצות היא לא ספונטנית, שכן הם פעלו כקליקה גדולה וזה אירוע נדיר. התחקיר נקרא "דוח הבוטים הגדול" ובויכוח הציבורי שהתנהל אח"כ, כותבי התחקיר הואשמו שטענו או רמזו שמדובר בבוטים אך למעשה מאחורי היוזרים עמדו פעילים אמיתיים. בבחינת עומק עלה שלא מדובר בקליקה "טהורה", אלא בקהילה צפופה מאד.
לא ניכנס פה לויכוח וקישורים לדיון נמצאים כאן: - לעמדת כותבי הדו"ח - לעמדת ד"ר אורן צור וצוותו, אוניברסיטת בן גוריון
אבל מה שאין עליו ויכוח הוא שקליקה גדולה מעידה על תיאום משמעותי שבהחלט יכול להחשיד אותה כמופעלת ע"י בוטים.
העובדה שקליקות הן פחות נפוצות היא גם הסיבה שאלגוריתם מסוג k-clique הוא בעייתי. כיוון שהוא יציף לנו מהרשת רק קליקות, נקבל תמונה חלקית מאד של הקהילות ברשת. התוצאה תהיה קהילות עם הקשרים חסרים וכמו כן נתקשה להבין ממה הן מורכבות בגלל צפיפותן. חוצמזה, k-clique הוא איטי ולמי יש זמן לחכות הרבה זמן לתשובה בינונית?
כאן נכנסים לתמונה גירבן וניומן והאלגוריתם הנושא את שמם. אלגוריתם גירבן-ניומן לא מניח הנחות מראש על הקהילה או הרשת, לא מבחינת צורת הקהילות ולא מבחינת מספרן. הוא עושה זאת ע"י היפוך נקודת המבט על הקהילה:
אם בכל הדוגמאות שהבאנו עד כה, עיקר העיסוק היה למצוא את הקשרים החזקים שבונים את הקהילה, ההופכי יהיה למצוא את הקשרים החלשים שמהווים את גבול הקהילה.
במקום להבנות את הקהילה bottom-up, מלמטה למעלה, דרך הקשרים החזקים, האלגוריתם מבנה קודם את גבולות הקהילה מלמעלה למטה (Top-Down) או מהחוץ פנימה.
היגיון זה הוא הדהוד של התזה של גראנובטר מתחילת הפרק. הקשרים החזקים שתורמים ליצירת קהילה קטנה, לא יכולים להחזיק רשת גדולה וזו מתפרקת לקהילות שקשרים חלשים מייצרים את גבולות הסירקולציה שלה. אלו הגבולות בהם גירבן וניומן עשו שימוש.
כדי למצוא את אותם גבולות, הם פעלו לפי אותה לוגיקה של זאכארי שהשתמש בצווארי בקבוק כדי לחלק את הרשת. רק במקום להשתמש בניתוח זרימה בין שני צמתים, הם זיהו את צווארי הבקבוק ברשת ע"י חישוב ה-Betweenness של הקשתות בגרף. לשיטתם, הסרת הקשתות בעלות ציון ה-BTWNS הגבוה, בסדר יורד, תפרק את הרשת לרכיבי קשירות (או "איים") וכל רכיב כזה יוגדר כקהילה. המאמר של גירבן וניומן מתאפיין לא רק בשפה פשוטה וקריאה אלא גם בצניעות כותביו שהיו הראשונים להצביע על חולשות השיטה שהם מציעים:
ראשית כל, זמן החישוב הוא ארוך (כי betweenness הוא מדד ארוך לחישוב).
שנית, מתקבלות תוצאות בעייתיות כשבוחנים את האלגוריתם על רשתות צפופות.
והנה בעיה נוספת, מתי להפסיק להוריד קשתות? הרי תיאורטית אפשר להמשיך ולהסיר את הקשתות בעלות ה-BTWNS הגבוה ברשת עד שנישאר בסוף עם רשת שמורכבת רק מצמתים, שכל אחד מהם קהילה בפני עצמו, ללא קשרים בכלל.
את הפתרון לבעיה זו הביא ניומן עצמו, ב-2004, ועל הדרך פתר גם את שאר הבעיות שהציג במאמרו הקודם.
כדי להחליט מתי צריך להפסיק להסיר קשתות, עשה ניומן שימוש במדד מודולאריות (Modularity).
בפשטות, מדד זה נועד לבחון את איכות החלוקה לקהילות של האלגוריתם.
הבחינה נעשית ע"י השוואת צפיפות הקשתות בקהילה שהתקבלה למול צפיפות הקשתות ברשת רנדומלית, בעלת אותו מספר צמתים. בקהילה אמורה להיות צפיפות קשתות רבה יותר מברשת רנדומלית, כך שאם החלוקה שקיבלנו צפופה יותר מהתוצאות הרנדומליות, זה סימן חיובי שיש כאן קהילה.
היתרון הגדול של מדד זה היה גם שהוא מהיר לחישוב.
אז רגע,
אם יש לנו עכשיו כלי מהיר שנותן ציונים לחלוקה לקהילות, למה לא כבר להשתמש בו בפני עצמו כאלגוריתם לחלוקה במקום להשתמש בו רק כמדד לטיב החלוקה של אלגוריתם אחר?
וזה מה שניומן עשה ופריצת הדרך שלו הביאה לגל של אלגוריתמיקה בתחום החלוקה לקהילות.
אולי האלגוריתם המפורסם ביותר ממשפחת המודולאריטי הוא אלגוריתם הלובאין שפורסם במאמרו של בלונדל מאוניברסיטת לובאין ב-2008.
איך עובד הלובאין:
למרבה האירוניה, שיטת העבודה שלו חוזרת לנקודת המבט הישנה של בניית קהילות Bottom-Up. הלובאין עובד בכמה איטרציות:
בראשונה, הוא מתחיל בצומת רנדומלי וממפה את סביבתו הקרובה ומחשב לצמתים אלו מדד
מודולאריות. הציונים יכולים לנוע על סקאלה מ-1, שזו קהילה מושלמת ועד 1-, כלומר, מקרה מובהק שאין כאן קהילה.
אם ציון המודולאריות של הקהילה הקטנה הוא טוב מספיק, הלובאין עובר לצומת אחר ומבצע תהליך דומה עד שמסיים מעבר על כל הצמתים. התוצר של האיטרציה הראשונה יהיה הרבה קהילות קטנות. באיטרציה השניה, הלובאין מבצע אגריגציה לקהילות הקטנות ומייצר מהן קהילות גדולות יותר, באותה שיטה כמו באיטרציה הראשונה: אם החיבור בין הקהילות משמר ציון טוב למודולאריות הוא ממשיך וכך גם באיטרציה הבאה.
הלובאין גם ממושקל, כלומר, האלגוריתם גם מתייחס למשקל בין הקשרים. לדוגמא, אם צומת קשור ל-2 קהילות, הלובאין ייבחר לשייך אותה לקהילה אליה הקשרים יותר חזקים, כלומר, אלה עם המשקל הגדול יותר.
התוצר הוא קהילות אגרגטיביות, כלומר שבנויות מתתי-קהילות ותת-תת-קהילות עד לרוזולוציית הצומת.
מה היתרונות של אלגוריתם הלובאין:
ראשית, מהירות. גם על רשתות גדולות האלגוריתם נותן תוצאות בזמן מהיר והוא גם ניתן לחישוב ביזורי. התוצאות שמתקבלות נחשבות אמינות-יחסית ונעשה בו שימוש רחב במחקר. בנוסף, ציון המודולאריות שהאלגוריתם נותן לכל קהילה מאפשר לספק תובנות נוספות על הרשת ועל כך בפרק אחר שיעסוק ב-best practice של ניתוח רשתות.
לפני שאפרוט את חסרונות הלובאין אני נדרש לגילוי נאות וזה שאני מת על לובאין.
התכונה שאני אוהב בו היא שהוא unsupervised כלומר, אין בו הנחות מוקדמות על הדאטה למעט עצם הגדרת הקהילה כמקום צפוף. זאת בניגוד לאלגוריתמים אחרים שמחייבים את הקהילה להגדרות נוקשות, למשל קליקות, או שקובעים מראש לכמה קהילות הרשת צריכה להתחלק.
אז נראה שהטענה המרכזית נגד הלובאין היא מה שמכונה "בעית הרזולוציה". הלובאין מחלק את הרשת לרוב כך: מתקבלת קהילת ענק ולצידה מספר קטן של קהילות גדולות וזנב ארוך של הרבה קהילות קטנות.
אם למישהו זה מזכיר Power Law אז לא בכדי. קהילות מתחלקות Power Law.
אז מה הבעיה?
זה תלוי בגישה. יש חוקרים שהיו רוצים לראות גם את הקהילות הגדולות מפורקות כבר בשלב הראשון לקהילות קטנות יותר והרי אנחנו יודעים שזה אפשרי כי כך עובד הלובאין: הוא מקבץ קהילות קטנות לקהילה גדולה.
אישית, אני רואה בכך יתרון. כך ניתן לראות איזה קהילות קשורות יותר לקהילות אחרות ע"י זה שהן חברות באותה קהילה גדולה.
אבל כשמדובר ברשתות ענק, המכילות מיליוני צמתים, יש גבול לרזולוציית הלובאין. אחרי 3 רמות הלובאין "מתפרק", כלומר, ניתן לראות תת-קהילות, ותת-תת קהילות בקהילה הגדולה אבל ניסיון לראות קהילות עוד יותר קטנות לא יצלח ונראה שכל צומת הוא קהילה בפני עצמו. זאת מכיוון שהלובאין עובד ב-3 איטרציות או 3 רמות בלבד.
פתרון אפשרי לכך הוא להריץ את הלובאין בכל רמה בה מסתכלים על הרשת. וכאן אנו מגיעים לבעיה אחרת בלובאין וזה שכל ניתוח שעושה הלובאין נראה קצת אחרת.
למה?
הלובאין בוחר בכל ניתוח צומת רנדומלי ממנה להתחיל את התהליך. נקודת פתיחה שונה של תהליך צבירת הקהילות מלמטה-למעלה יכול לייצר שוני בחלוקה לקהילות.
כמה שונות? לא בהרבה. בכל זאת יש היגיון בדרך בה נוצרות קהילות והן לא אקראיות.
אחת מההצעות להתמודד עם בעיה זו היא להריץ את הלובאין מספר פעמים ולבחור את התוצאה שחוזרת הכי הרבה פעמים וכך גם על הדרך לבצע אופטימיזציה של החלוקה לקהילות.
נקודה אחרונה בלובאין היא שבפלט המתקבל, כל צומת יכול להיות שייך רק לקהילה אחת. במבט על רשת אנושית, למשל, יש פה לכאורה חסרון. הרי כל אדם שייך ליותר מקהילה אחת. אדם יכול להיות שייך לקהילה מגדרית ו/או גיאוגרפית ו/או משפחתית ו/או מקצועית ועוד. אז למה להגביל לקהילה אחת? ואכן, ישנם אלגוריתמים שמאפשרים לצומת להיות חברה ביותר מקהילה אחת. משפחת אלגוריתמים זו נקראת "קהילות חופפות". K-clique למשל הוא אחד מהם. צומת יכולה להיות שייכת ליותר מקליקה אחת.
אבל אישית, אני רואה בתכונה של הלובאין דווקא פיצ'ר ולא באג.
ברור שצומת יכול להיות משוייך לאינספור קהילות, אבל השאלה היא לאיזו קהילה הוא הכי שייך, נכון לזמן הניתוח. לדעתי, ההשתייכות החד-חד ערכית לקהילה חושפת את האופי האמיתי של הצומת.
למשל, אם אנסה לשכנע את אשתי שאני מקדיש הרבה זמן למשפחה, אבל ניתוח קהילות יראה שאני נמצא בקהילת העבודה שלי ולא בקהילת המשפחה, זה אומר משהו.
דוגמא אחרת מאחד המיטאפים בנושא הרשת בהם הייתי היא בקלאסיפיקציה של מוצרים. מוצר יכול להיות משוייך לכמה קטגוריות, למשל, עציץ יכול להיות מוגדר תחת קטגוריית גינה או קטגוריית נוי או קטגוריית ריהוט. חלוקה לקהילות ע"י הלובאין תאפשר לדעת כיצד הלקוחות משייכים את המוצר, גם אם לפעמים זה לא מוצא חן בעיני מומחי התוכן שלנו.
אבל מה לגבי קהילות ברשת מכוונת, כלומר, שהקשרים בה הם לאו דווקא הדדיים?
יש אלגוריתמים שמאפשרים להתחשב בכיווניות הקשרים כשהם מחלקים לקהילות (כולל הלובאין) אך לכך נתייחס בפרק אחר העוסק ב-best practice של ניתוח רשתות.
לסיכום חלק זה, נאמר שכמו שיש מאות מדדי מרכזיות ברשת כך יש מאות אלגוריתמים
שמאפשרים לחלק את הרשת לקהילות והם נובעים מהגיונות שונים.
ראינו שיש אלגוריתמים שדורשים מה-data analyst הנחות מוקדמות על הדאטא, למשל שקהילות הן קליקות בגודל מסוים או שיש ברשת מספר מוגדר של קהילות.
ראינו שיש גם אלגוריתמים שהם יותר unsupervised, כמו למשל הלובאין, שיתרונם בכך שהם data-driven ולכן אינם מחוייבים לתרחישים שנקבעו מראש ולכן הם גם אלה שיכולים לחדש לנו ולהציף לנו תופעות לא מוכרות.
נראה שמבחינת איכות החלוקה לקהילות קיימת היום תקרת זכוכית בתחום והדגש הוא על ביצועים, כלומר, מהירות החלוקה.
אז הבנו למה נוצרות קהילות, איך הן נראות ואיך למצוא אותן ברשת. אז מה עושים איתן?
קהילות וביג דאטה
עידן רשתות הענק והביג דאטה מאתגרים את יכולת ה-data scientist לנתח ולהפיק משמעויות מהדאטה, אבל למרבה המזל, באנו עם פתרונות ולא עם בעיות.
כשניגשים לנתח רשתות גדולות, חלוקה לקהילות היא הבסיס. העוצמה בחלוקה לקהילות היא היכולת לראות את כלל הרשת "במעוף ציפור" (Top-Down) וכך לנתחה במהירות ללא קשר לגודלה. הדבר מתאפשר ע"י "גרף הקהילות".
גרף קהילות הוא רשת של קשרים בין קהילות, כשכל צומת בגרף מייצג קהילה אחת שבתורה מייצגת את כל הצמתים שבה. למעשה זו אגרגציה של גרף הצמתים.
אותן תופעות שנראה ברשת הצמתים נראה גם בגרף האגרגטיבי של גרף הקהילות.
Scale-free כבר אמרנו?
גם כשנסתכל על הרשת כאוסף של צמתים או כאוסף של קהילות, אותם חוקים חלים על שניהם וחוק מספר 1 הוא ה-Power Law. ככל שהרשת תגדל, יהיו מעט קהילות גדולות הקשורות זו בזו ומהוות רכיב קשירות מרכזי ואילו רוב הקהילות הינן רכיבי קשירות שאינם קשורים לאף צומת מחוץ לקהילתן. קהילות אלה יהוו את ה"זנב הארוך" של התפלגות ה-Power law. לרוב, בכל קהילה שכזו יהיה מספר נמוך-יחסית של צמתים.
גרף קהילות שכזה, המאפשר הסתכלות על כלל הרשת מלמעלה, יכול לחשוף בפנינו את מבנה הרשת וההיגיון שעומד מאחוריה בזכות הבנת ההומופיליה של קהילה והקשרים בינהן. אבל יותר מכך, גרף קהילות יכול לגלות לנו את ה- Unknown-Unknown ("מה לא ידענו שלא ידענו").
איך נדע על משהו אם אנחנו בכלל לא יודעים שצריך לדעת אותו?
הנה עוד מקום שגישת ה-data driven של חלוקת הרשת לקהילות מאפשרת לנו להביא זהב וניתן דוגמא:
הדגמנו קודם איך חלוקה לקהילות של רשת המאמרים האקדמאיים, חושפת בפנינו את תחומי העניין השונים המעסיקים את האקדמיה והקשרים בינהם.
הסברנו גם כיצד ע"י זיהוי מרכזי הכובד, נדע לתת לייבל או תיוג לכל קהילה, למשל, אם המאמרים המרכזיים בקהילה הם בנושאי כימיה, אז מדובר בקהילת הכימיה.
אך מה אם נמצא קהילה שנתקשה למצוא לה תיוג?
למשל, אם היינו מסתכלים לפני מספר שנים על הרשת האקדמאית, היינו מוצאים קהילה לא מוכרת ובה מאמרים מכמה תחומים שונים כגון ביולוגיה, כימיה ופסיכולוגיה.
מה שכנראה גילינו הוא תחום אקדמאי חדש, במקרה זה, מדעי המוח, שלא ידענו לשאול עליו אבל הנתונים "הציפו" אותו.
דמיינו רשת ובה רק חלק מהמידע מתוייג. אם תמצאו קהילות מרכזיות שאין בהן ולו תיוג אחד הדבר יכול להצביע על פער משמעותי שלא ידעתם עליו.
האם צריך לעבור על כל הצמתים בקהילה כדי להבין מה ההומופיליה שבה, או במילים אחרות, מה הלייבל שלה? ברור שלא. כאן נחזור לחוק הרשת מס' 1: ה-power law.
כמו שלא צריך לעבור על כל הקהילות ברשת, אלא רק על המרכזיות, שכן הן מתפלגות Power Law, כך גם בכדי לאפיין קהילה, אין צורך לעבור על כל הצמתים בה. מדד ה-Degree מסייע לנו לתת את הלייבל לקהילה. הצמתים בקהילה עם הדרגה הגבוהה ביותר הם אלו שיאפיינו בצורה הטובה ביותר מה הרעיון ההומופילי שסביבו מתארגנת הקהילה. במקרה של קהילת הטוויטר של ג'סטין ביבר, זה כנראה יהיה ג'סטין ביבר.
במקרה וניתקל בקהילה בפייסבוק שבה הצמתים עם הדרגה הכי גבוהה בקהילה שאנו חוקרים הם מפתח תקווה, כנראה שהגענו ל"קהילת פתח תקווה".
גם במקרה של רשת המאמרים האקדמאית, די בכך שמרכזי הכובד באותה קהילה יזוהו כמאמרים בתחום הפיסיקה כדי לאפיין את הקהילה כקהילת הפיסיקאים, בגלל ה-Power law.
בנוסף, חלוקה לקהילות יכולה לסייע לנו למצוא את מרכזי הכובד ברשת שמענינים אותנו. בפרק על מדדי המרכזיות הבאנו כדוגמא מחקר אמריקאי שניסה לאתר את מובילי המהפכה של ה"אביב הערבי" במצרים. המחקר, באמצעות מעקב אחרי רשת טוויטר, חיפש את הגורמים עם הדרגה
הגבוהה ביותר ולסמנם כמרכזי כובד אך מצא שהגורם המרכזי הוא לא אחר מאשר ג'סטין ביבר.
אז איך חלוקת הרשת לקהילות עוזרת לנו?
חלוקת רשת הטוויטר לקהילות היתה מראה שג'סטין ביבר הוא אכן מרכז כובד, אבל מרכז כובד של קהילה שמה שמשותף לה זה ג'סטין ביבר וטעם רע. לא במפתיע, הקהילה של ג'סטין בנויה בצורה של כוכב שלא תאמינו מי נמצא במרכזו.
לעומת זאת, קהילת המהפכה צפופה הרבה יותר, עם הרבה יותר קשרים בין הצמתים, דבר שמעיד על שיח רב יותר ועל הדהוד מסרים משמעותי יותר. במרכז הכובד של קהילה זו ניתן למצוא בלוגרים מובילים ואנשים שכנראה לקחו חלק יותר משמעותי בעיצוב האירועים מאשר ג'סטין.
אגב, כפי שניתן להבין מהדוגמא, לקהילות ורשתות יש מדדים שמאפשרים לנו להעריך מה קורה בהן. המדד בו עשינו שימוש כרגע הוא מדד צפיפות הרשת, או צפיפות הקהילה.
מדד זה ניתן לחישוב בקלות ע"י חלוקת כמות הקשרים הקיימים ברשת בכמות הקשרים הפוטנציאליים שיכולים להיות ברשת. ככל שהמספר גבוה יותר, כך הרשת צפופה יותר, דבר שמעיד על אינטראקטיביות רבה יותר. קליקה, שהיא רשת או קהילה שבה כולם קשורים לכולם, תקבל ציון 1.
דוגמא לשימוש אפשרי במדד צפיפות הוא למשל במעקב השוואתי בין קהילות של חברויות במסגרת הכשרה או גיבוש. נצפה שהקהילה תהיה צפופה יותר בחלוף הזמן כמדד להצלחת הגיבוש.
על בחינת רשתות וקהילות לאורך זמן נדבר בפרק אחר העוסק בניתוח דינאמי של הרשת.
לסיכום:
תפקיד האנליסט הוא לספר את הסיפור של הדאטא. באמצעות מרכזי הכובד ניתן "לספר את הסיפור" של הקהילה (למשל, מה מעניין את הקהילה באותו זמן) ובאמצעות הקהילות המרכזיות "לספר את הסיפור" של הרשת כולה. הנחה זו מתבססת על שני חוקי הרשת: התפלגות Power law, שפירושה שמרכזי הכובד שולטים בקהילה, כלומר, הם הגורם המשותף שמלכד סביבו את הקהילה (והקהילות המרכזיות שולטות ברשת) ועל כך שהרשת מתקהלת על בסיס הומופיליה, כשמרכזי הכובד הם אינדיקטורים טובים לסוג ההומופיליה שמקבצת את הקהילה.
רוצים.ות להרחיב את קהילת מדע הרשתות בישראל? ככל שתדרגו יותר, כך הפודקאסט יהיה חשוף לאנשים רבים יותר.
דרגו את הפודקאסט בספוטיפיי או באפל-פודקאסטס ו/או כיתבו ביקורת. ניתן לדרג גם בפודקאסט-אדיקט (בטאב של ה-reviews). מותר ומומלץ להעלות פוסט ולתייג את נטפריקס בפייסבוק/טוויטר/אינסטגרם או לינקדאין ושוב, פוסטים יצירתיים במיוחד יושמעו בפרקים הבאים.
ואם עוד לא עשיתם.ן לייק בדף של נטפריקס בפייסבוק, זה הזמן. אתרים עם יותר לייקים, מקבלים יותר חשיפה.
לפניות/הערות/הארות/הצעות ועוד: שלחו מייל!
ולא לשכוח לעשות Subscribe לפודקאסט באפליקציה החביבה עליכם.ן.
נתראה בפרק הבא של נטפריקס (:
#NetworkScience #SNA #SocialNetworkAnalysis #GraphTheory #DataScience #SocialPhysics #תורת_הגרפים #Facebook #CommunityDetection #Clustering