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

רשתות וגרפים

רשתות הן תופעה נפוצה בתחומים שונים של חיינו, המקיפה אותנו בכל אשר נפנה. בכל בית ומשרד אנו פוגשים ברשתות האינטרנט וה-World Wide Web (דפי האינטרנט), ברשתות מחשב מקומיות וברשתות הטלפון והחשמל. מעגלים חשמליים וקשרים בין אטומיים במולקולות מייצגים רשתות מתחום מדעי הטבע. רשת העצבים וכלי הדם הן דוגמאות לרשתות במדעי החיים, והרשימה עוד ארוכה.

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

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

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

תמונה 1: תעבורת האינטרנט בין מדינות שונות – צבע הקווים מייצג את כמות המידע המועבר (לקוח מתוך
http://www.nd.edu/~networks/visual)

תמונה 2: מפת קווי התעופה של חברת תעופה בארה"ב

פיזיקה סטטיסטית ורשתות אקראיות

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

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

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

מרחק בין שני קודקודים בגרף מוגדר כמספר הקשתות המינימלי שיש לחצות על מנת לעבור בין שניהם. אחת התכונות המעניינות של גרפים לא מסודרים היא, שבניגוד לגרפים מסודרים, המרחק הממוצע בין שני קדקודים הוא קטן, ואינו פרופורציוני לגודל הגרף (למעשה, כאשר N הוא מספר הקדקודים בגרף, המרחק הממוצע פרופורציוני ל- logN). ברשת ה-WWW, המכילה כמיליארד דפים, מעריכים כי המרחק הממוצע בין שני דפים (מספר הקישורים עליהם צריך ללחוץ על-מנת להגיע מדף אחד לשני) הוא כ- 20 בלבד. גם חבילות המידע המועברות ברשת האינטרנט (כדוגמת הודעות E-mail) עוברות מספר קטן של שרתים בדרכן מהמחשב בבית לאתר בו אנו מעונינים ובחזרה. תכונה זו היא חיונית לתעבורה יעילה, שכן היא מאפשרת העברה מהירה של חבילות המידע, ומקטינה את כמות חבילות המידע המסתובבות ברשת בכל רגע, שאילולי כן עלולות היו לפקוק את הרשת.

בשנות ה-60 המציאו פול ארדוש (Erdös) ואלפרד רניי (Rényi) מודל ראשון לרשתות אקראיות. במודל זה מפוזרים הקישורים באופן אקראי בין קדקודי הגרף. רבות מתכונותיו של מודל זה נחקרו. נמצא כי כאשר מספר הקשתות קטן, יורכב הגרף כולו מאיים קטנים שאינם קשורים ביניהם. אך כאשר מספר הקשתות גדול מחצי מספר הקדקודים, תהיה בגרף קבוצת קדקודים המקושרים ביניהם, המהווה חלק משמעותי מהגרף (ובנוסף לכך יהיו בו איים מבודדים קטנים).

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

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

דוגמא לרשת מסוג זה היא רשת הקשרים בין שחקנים, כאשר השחקנים הם הקדקודים והקשתות מחברות בין שחקנים שהופיעו יחד באותו סרט. בגרף זה המרחק בין כל שני שחקנים הוא קטן למרות מספר השחקנים הגדול. באתר http://www.cs.virginia.edu/oracle/ ניתן למצוא מהו המרחק בין השחקן קווין בייקון לבין כל שחקן אחר. המרחק הממוצע הוא כ-3 סרטים בלבד. דוגמא נוספת היא גרף ארדוש, אותו מגדירים מתמטיקאים לכבודו של פול ארדוש שהיה אחד המתמטיקאים הפוריים ביותר בהסטוריה, וכתב מאמרים עם כ-500 מתמטיקאים. בגרף זה כל קדקוד הוא מתמטיקאי, ובין מתמטיקאים שכתבו מאמר במשותף מחברת קשת. מספר ארדוש של מתמטיקאי מוגדר כמרחקו על הגרף מפול ארדוש. גם בגרף זה המרחקים בין מתמטיקאים קטנים ביותר. פרטים נמצאים באתר http://www.oakland.edu/~grossman/erdoshp.html.

תמונה 3: רשתות מחשבים והתפלגויות הקשרים של הקודקודים המרכיבים אותן

תמונה 4: שריג ריבועי (משמאל), שריג משולש (שני משמאל),
שריג ריבועי תלת-ממדי (שני מימין) ומולקולה המורכבת משריג של אטומים (מימין)

תמונה 5: רשתות גנים באדם ובזבוב

תמונה 6: רשת מטבולית (מתוך Jeong et al, Nature 2000)

תמונה 7: התפלגות הקשרים ברשתות מטבוליות עבור אורגניזמים שונים
(מתוך Jeong et al, Nature 2000)

פרקולציה – חלחול

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

במודל החלחול ממולא שריג דו- או תלת-ממדי באופן אקראי בנקודות שחורות (המייצגות לדוגמא את הנפט) ונקודות לבנות (המייצגות במקרה זה את הסלע), כאשר ההסתברות לכל צבע נקבעת מראש. מסתבר שבריכוזים קטנים של הצבע השחור יהיו רק איים שחורים קטנים - ובמקרה זה אין טעם לקדוח במקום. ככל שיעלה הריכוז יעלה גודלם של האיים, עד שמגיעים לריכוז מסוים, שמעליו ייווצר גוש שחור גדול שאורכו יהיה כאורך השריג כולו והוא יגיע מצד אחד של השריג לצדו השני, אפילו אם השריג גדול מאד (גוש זה נקרא "צביר מחלחל"). זוהי דוגמא לתופעה המכונה ע"י הפיזיקאים מעבר פאזה מסדר שני. כאמור, מעברים אלה מהווים שינוי בהתנהגות הקולקטיבית של המערכת – כמו השינוי בין המצב בו אין קשר בין צדי השריג לבין המצב בו הם מקושרים. במודל החלחול, כמות הנפט שניתן לחלץ מהאדמה תלויה בגודלו של הצביר הגדול ביותר. אם לדוגמא מתגלה מדגימות הנלקחות ממרבץ הנפט כי הוא מכיל 70% נפט ו-30% סלע, לא ניתן יהיה לחלץ את כל הנפט במרבץ (שהיא 70% מנפחו הכולל). עם זאת, כמות הנפט הניתנת לשאיבה ניתנת לחישוב ע"י שיטות מתורת החלחול וסימולציות מחשב המדמות שריג ש-70% מקדקודיו שחורים ו-30% לבנים ומחשבות מהו גודל הצביר הגדול ביותר שניתן למצוא, ואיזה חלק מתוכו ניתן לשאוב. מחישוב זה ניתן להעריך מהי כמות הנפט שתישאב בפועל, והאם השאיבה כדאית.

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

רשתות חסרות סקלה

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

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

כמצויין לעיל, גם במערכות מלאכותיות כמו האינטרנט וה-WWW, התפלגות מספר הקישורים בקדקודים השונים הינה חסרת סקלה ( P(k)~k-λ ). הקשר בין השינוי בקישוריות לבין השינוי בשכיחות נקרא חוק-חזקה. כאשר 3>λ>2 תכונות הרשת שונות משמעותית מתכונות רשת ארדוש. עבור λ גדול יותר דומות תכונות הרשת המתקבלת לגרפים של ארדוש. מעריכים כי ברשת האינטרנט החזקה היא בערך 2.5 (כלומר מספר הקדקודים בעלי קישוריות כפולה יהיה קטן פי 22.5, כלומר פי 5.6 בערך). העובדה שהתפלגות כזו קיימת גם ברשתות מלאכותיות היא מפתיעה, וטרם הוצע הסבר המקובל על כל החוקרים באשר לדרך בה נוצרה התפלגות מסוג זה באינטרנט וב-WWW. אולם ייתכן כי אופיים של מבנים אלה, שאינם מתוכננים באופן מסודר, מביא לכך שתהליכים דומים ייתרחשו בכל קני המידה - מרמת המחשב הבודד, דרך הרשת המקומית ועד לרשת האינטרנט כולה.

יציבות האינטרנט

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

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

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

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

מגפות וחיסון

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

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

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

עולמות קטנים ועולמות זעירים

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

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

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

תמונה 9: שריג דו-מימדי ריבועי (באמצע), בעל צביר מחלחל מעל סף הפרקולציה (מימין)
וללא צביר מחלחל (משמאל)

תמונה 10: פרקולציה ברשתות המורכבות על שריג דו-מימדי, עבור התפלגויות קשרים שונות

סיכום

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

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

לקריאה נוספת:

Linked/ A. L. Barabasi בעברית "קישורים" מאת א"ל ברבשי. יצא בקרוב בהוצאת חמד-ידיעות אחרונות

מספר מאמרים:
על גרפים:

B. Hayes “Graph theory in practice: Parts I,II”, American Scientist, 1,3/2000
S. Strogatz “Exploring complex networks”, Nature Volume 410 Number 6825 Page 268 (2001)

על רשתות "העולם הקטן":

“Small worlds” / D. J. Watts, Princeton University Press (1999)
R. Cohen, S. Havlin, “Scale-free networks are ultrasmall”, Physical Review Letters 90, page 58701 (2003)

על האינטרנט:

R. Albert, H. Jeong and A. L. Barabasi “Internet: Diameter of the World-Wide Web”, Nature Volume 401 Page 130 (1999)
R. Albert, H. Jeong and A. L. Barabasi “Error and attack tolerance of complex networks”, Nature Volume Page 378 (2000).
R. Cohen, K. Erez, D. ben-Avraham and S. Havlin “Resilience of the Internet to random breakdown”, Physical Review Letters, 85, Page 4626 (2000).
R. Cohen, K. Erez, D. ben-Avraham and S. Havlin “Breakdown of the Internet under intentional attack”, Physical Review Letters, 86, Page 3682 (2001).
A.F. Rozenfeld, R. Cohen, D. ben-Avraham, S. Havlin “Scale-free networks on lattices”, Physical Review Letters 89, page 218701 (2002)
R. Cohen, D. ben-Avraham, S. Havlin, “Efficient immunization strategies”, Physical Review Letters, (in press) (2003)