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

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

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

במאמר בשם Fast unfolding of communities in large networks המחברים ובראשם סטודנט לתואר שני בעבודת המאסטר שלו, Vincent D. Blondel הצליחו לעשות זאת באמצעות אלגוריתם קירוב שנקרא על שם המקום שבו נעשה העבודה, אוניברסיטת לובן בבלגיה.

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

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

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

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

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

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

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

דברו איתי:

שלמה יונה

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

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

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