תורת הרשתות

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

הגדרת הרשת

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

התפתחות מחקרי תורת הרשתות

מבחינה היסטורית, מחקר על רשתות בתחומים שונים אינו חדש. את הבסיס המתמטי למחקר על רשתות הניח אוילר ב-1736. הוא פתר את הבעיה הידועה כבעיית הגשרים של קניגסברג, בעזרתה פיתח את יסודות הגרף המהווה צירוף של צמתים וקישורים.
מאתיים שנה מאוחר יותר ב-1959, פיתחו שני המתמטיקאים, ארדש ורניי את תיאורית הרשתות האקראיות. וכן, בסוף שנות ה-60 של המאה ה-20 החלו לראות מחקרים על רשתות חברתיות, כולל הניסוי המפורסם של סטנלי מילגרם מ-1967 שטבע את המושג " שש דרגות של הפרדה". הרעיון אומר כי באופן תאורטי כל שני אנשים בעולם מקושרים ביניהם על ידי חמישה אנשים אחרים לכל היותר. זהו מקרה פרטי של תופעת העולם הקטן - התופעה המשוערת שבעולם המודרני ישנה שרשרת קצרה של מתווכים המקשרת בין כל שני אנשים בעולם.
ב-1973 הציג הסוציולוג מארק גרנובטר את מאמרו המפורסם "עוצמתם של קשרים חלשים" בו טען כי בתחומים כשיווק, כלכלה או פוליטיקה, קשרים חלשים מאפשרים גישה לאוכלוסיות שאינן נגישות דרך קשרים חזקים, ושקשרים חלשים אלו תורמים יותר להפצת מידע בין בני אדם. כמו כן, המחקר בדק כיצד מבנה ופריסה של רשת חברתית הקיימת בין שני אנשים ומעבר להם עצמם, משפיעים על פריסה של הרשת החברתית עצמה ועל ההפצה של מידע אל מחוץ לאותה רשת חברתית.
במאמר שפורסם ב-1998 על ידי וואטס וסטרוגאטס הם הוכיחו כיצד נוצרת תופעת העולם הקטן. חיווט מחדש של אחוז קטן של הקישורים במודל הרשת הרנדומית  של ארדש ורניי יוצר את טופולוגיית העולם הקטן. הטופולוגיה החדשה מאופיינת שני מדדים עיקריים: מצד אחר נשמרות קהילות (צבירים) של צמתים עם קישורים מרובים בין חברי הקהילה, מדד המוכר בשם (Clustering coefficient). יחד עם זאת, מצד שני, הקהילות הללו אינן מנותקות זו מזו וניתן בקלות להגיע מקהילה לקהילה וזאת בזכות מספר מועט של צמתים המחברים בין קהילות שונות. 
ב-1999 אלברט-לסלו ברבאשי, הציג לראשונה את התהליך בו נוצרות רשתות אשר התפלגות הקשרים של הצמתים בהן, אינה גאוסיינית, אלא נראית כהתפלגות בעלת "זנב ארוך". למעט מאד צמתים עשרות רבות של קשרים ושאר הצמתים ברשת מאופיינים במספר מועט של קשרים (Total Degree  - המדד לתיאור מספר קשרים היוצאים ונכנסים לכל צומת). רשתות אלו נקראות בשם Scale Free Networks, מכיוון שניתן למצוא בהם צמתים עם כמות קשרים גדולה מאד שחורגת מה"סקאלה" שאנו מצפים. לצורך הדוגמה, אם גובה האנשים היה מתפלג באופן Scale free ניתן לדמיין שלעיתים (נדירות) היינו מטיילים ברחוב ופוגשים אדם בגובה 5 מטר... א.ל. בראבשי חקר את מאפייני הרשתות הללו ואת התהליכים הגורמים להתפתחותן. לתוצאות מחקריו חשיבות רבה כיוון שהן נוגעות לרשתות מציאותיות חשובות רבות, כגון רשת האינטרנט ורשתות גנטיות בתאים.

הרשתות האקראיות

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

רכזות וחוק ה-80/20

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

אפקט הרשת

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