אנטרופיית היררכיית הרשת להכמת אי-דימיון בין גרפים

מדוע הבדלים קטנים ברשתות משמעותיים

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

הסתכלות על רשת בשכבות

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

לתת לקשתות לדבר: כיווץ זוגות קדקודים

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

מדידת אובדן מידע באמצעות אנטרופיה

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

זיהוי מבנה עדין ושינוי לאורך זמן

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

יישומים מעשיים: ניידות וחלבונים

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

מה זה אומר במונחים פשוטים

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

ציטוט: Mou, J., Wang, L., Zhang, C. et al. Network hierarchy entropy for quantifying graph dissimilarity. Commun Phys 9, 83 (2026). https://doi.org/10.1038/s42005-026-02523-9

מילות מפתח: דמיון רשתות, רשתות מורכבות, מדדי אנטרופיה, התפשטות אפידמית, רשתות מבנה חלבון