Complex Networks

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

ולעניינו.
לפני כשנה, במהלך ביקור ביריד של שבוע הספר נתקלתי בספר Linked: The New Science of Networks (כמובן בתרגום עברי, שאיני זוכר איך תורגם כרגע). קניתי, קראתי ובעיקר נחשפתי לעולם המחקר הזה של רשתות מורכבות.
אז הנה אני, מנסה לערוך לכם הכרות לנושא ואולי קצת לסכם לעצמי גם כמה דברים על הדרך.

אז מהן רשתות מורכבות?
כדי לענות על זה, כדאי שנתחיל קודם בביאור מושג הרשת. הרשת היא אוסף ישויות שמחוברות (או מתייחסות) אחת לשניה ביחס כלשהו. דוגמאות לא חסרות:
1. רשתות חברתיות (מכרים, חברים לעבודה, משפחה)
2. רשתות של תגובות ביו כימיות: כל צומת ברשת היא מולקולה, ושתי מולקולות קשורות אחת לשניה אם הן מגיבות ביחד בתגובה כימית.
3. רשתות ניורונים במוח
4. רשתות של חשמל: תחנות כוח, ממסרים והכבלים המחברים בינהם
5. רשת האינטרנט (כמובן...): כל דף הוא צומת והקישורים הם אותם לינקים שאנחנו מכירים.
וכו' וכו'

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

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

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

מבחינה הסטורית, מחקר על רשתות בתחומים שונים הוא לא חדש בכלל.
כך למשל, מחקר על רשתות חברתיות החל כבר בשנות ה 20 של המאה ה 20 (אפילו קצת לפני זה, אבל מי סופר), כולל הניסוי המפורסם של סטנלי מילגרם מ 1967.
את הבסיס המתמטי למחקר על רשתות רנדומליות הניחו ארדוס ורניי כבר ב 1959 בעבודתם על גרפים רנדומליים.
בשנות ה 90 ווטס וסטרוגץ חקרו את רשתות של "עולם קטן" (יש תרגום יותר טוב למונח Small World Networks?) ואלברט ברבשי, הסופר של Linked שהוזכר כבר למעלה, פיתח את המושג של רשתות חסרות סקאלה.

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

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

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

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

תגיות: networks,technology