זיהוי צמתים משפיעים באמצעות קליפה-ק-היררכית ושילוב שכונות מורחבות

מדוע חלק מהקשרים חשובים יותר מאחרים

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

מחפשים שחקנים מרכזיים ברשתות מורכבות

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

שילוב מבט מקרוב ומבט רחב

HKEN מתחילה בהענקת משקל התחלתי לכל צומת שמשלב שתי תובנות. הראשונה היא דרגה (degree) — מספר הקשרים הישירים שלה — סימן בסיסי לחשיבות מקומית. השנייה היא מיקומה במבנה הרחב של הרשת, הנמדד באמצעות ערך קליפת-k (k-shell), שמחשף עד כמה הצומת מוטמעת בליבת הרשת ולא בשוליים. מאחר שדרגות יכולות להיות גדולות בהרבה מערכי קיליפה, HKEN מחדש מעלה אותן למדד משותף כדי שאף אחד מהמרכיבים לא יגבר על האחר. כך מתקבל אומד מאוזן ראשוני של הפוטנציאל להשפעה של כל צומת, בהתבסס הן על שכונתו והן על מיקומו הגלובלי.

להקשיב לשכנים קרובים ורחוקים

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

הפיכת השפעה גולמית לדירוג סופי

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

בדיקת השיטה ברשתות אמיתיות

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

מה המשמעות בעולם האמיתי

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

ציטוט: Wang, F., Sun, Z., Wang, G. et al. Identifying influential nodes through hierarchical k-shell and extended neighborhood integration. Sci Rep 16, 10215 (2026). https://doi.org/10.1038/s41598-026-40209-y

מילות מפתח: צמתים משפיעים, רשתות מורכבות, התפשטות מידע, מרכזיות ברשת, מודל SIR