תורת הרשתות

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

הגדרת הרשת[עריכת קוד מקור | עריכה]

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

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

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

התפתחות מחקרי תורת הרשתות[עריכת קוד מקור | עריכה]

תורת הרשתות נשענת על מחקרים שנעשו בתורת הגרפים ובניתוח רשתות חברתיות במאה ה-20:

מחקרים מתורת הגרפים[עריכת קוד מקור | עריכה]

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

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

מחקרים של ניתוח רשתות חברתיות[עריכת קוד מקור | עריכה]

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

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

מחקר מדע הרשתות[עריכת קוד מקור | עריכה]

- התגלית הראשונה של תכונות אוניברסליות של רשתות שאיפשרה את מדע הרשתות, היא התגלית ב-1999 של אלברט-לסלו ברבאשי שהציג לראשונה את התהליך בו נוצרות רשתות אשר התפלגות הקשרים של הצמתים בהן אינה גאוסיינית אלא נראית כהתפלגות בעלת "זנב ארוך". בהתפלגות זו, למעט מאוד צמתים ישנם קשרים רבים ברשת ולשאר הצמתים מספר מועט של קשרים. ברבאשי הגדיר רשתות אלו בשם Scale Free Networks או רשתות חסרות סקאלה/נטולות קנה-מידה: אם התפלגות הדרגה של הרשת (כלומר, ההסתברות שלצומת שנבחר באקראי יש מספר קשרים מסוים) מקיימת פונקציה מתמטית ייחודית הנקראת Power-Law (אנ'), המרמזת כי להתפלגות הדרגה של הרשת אין קנה-מידה מאפיין. מנגד, לרשת בעלת קנה-מידה יחידי ומוגדר ישנו דמיון מסוים לרשת סריג פשוטה, בכך שלכל צומת (בערך) אותו מספר קשר. דוגמאות לרשתות בעלות קנה מידה יחיד הם מודל ארדש-רנה לגרף רנדומי והיפרקובייה. ברשת בעלת התפלגות הדרגה נטולת קנה מידה, לחלק מן השיאים ישנה התפלגות הדרגה הגדולה בסדרי גודל מהממוצע - שיאים אלה נקראים נקודות-מוקד (Hubsֿ), על אף שמונח זה מעט מטעה, מכיוון שאין סף קבוע מעליו נחשב צומת לנקודת מוקד. אם היה סף שכזה, לא הייתה הרשת נטולת קנה-מידה. התעניינות ברשתות נטולות קנה-מידה התחיל בשנות ה-90 המאוחרות, עם הדיווחים על גילויים של התפלגויות Power-Law בעולם האמיתי, כגון World Wide Web, רשתות IP, רשתות-קשר בין חלבונים, ועוד. מרבית מהדיווחים על "Power-Laws" בעולם האמיתי נכשלו במבחן סטטיסטי קפדני יותר, אך הרעיון הכללי של רשתות המראות התפלגויות זנב-עבה באופן מובהק, תופעה שקיימת ברשתות "עולם אמיתי", היה שונה לחלוטין ממה שהיה מצופה מרשת בעלת קצוות אקראיים ולא תלויים (כלומר, המקיימת את התפלגות פואסון). בכדי להמחיש את רעיון התפלגות "הזנב הארוך", ניתן לדמיין שלעיתים (נדירות) היינו מטיילים ברחוב ופוגשים אדם בגובה 5 מטר... ברבאשי חקר את מאפייני הרשתות הללו ואת התהליכים הגורמים להתפתחותן. לתוצאות מחקריו חשיבות רבה כיוון שהן נוגעות לרשתות מציאותיות חשובות רבות, כגון רשת האינטרנט ורשתות גנטיות בתאים.

רכזות ברשת והתפלגות זנב ארוך[עריכת קוד מקור | עריכה]

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

אפקט הרשת[עריכת קוד מקור | עריכה]

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

יישומים[עריכת קוד מקור | עריכה]

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

להלן מספר דוגמאות מתחומים שונים העושים שימוש בתורת הרשתות:

  • רפואה - ניתן להשתמש ברשתות על מנת לאתר מגיפות. ניקולאס כריסטאקיס הוא חוקר ידוע בזכות מחקריו על הדרך שבה רשתות חברתיות נוצרות ופועלות בתחום הרפואה והסוציולוגיה. באחד ממחקריו הוא טוען כי תופעות כמו השמנה מתפשטות בדומה למחלות מידבקות ברשת החברתית[7].
  • הניהול- בעזרת תורת הרשתות ניתן להציג את מבנה הארגון, כמו גם את תהליכי העבודה שלו, כ"רשת" ובאופן כזה מספקת המערכת מידע רב ובצורה ויזואלית ואפקטיבית יותר וכך מאפשרת לפתור בעיות ניהול. כמו כן, רשתות חברתיות עסקיות שמורכבות מארגונים שונים יכולים לעזור לנו לעמוד על סיכויי ההצלחה של שיתופי פעולה עסקיים בין חברות שונות[8][9].
  • מערכות מידע – חוקרים בודקים את ההשפעה של רשת הארגון על הצלחת התהליך של הטמעת מערכות מידע בארגון[10]
  • כלכלה- ישנם שימושים רבים לתורת הרשתות בתחום הכלכלה, למשל, חיזוי מידת הצלחה של קרן הון סיכון. כדי לעשות זאת צריך להתבסס על ניתוח הקשרים בין קרנות הון סיכון לבין עצמן בשילוב של ניתוח בין חברות הסטארט-אפ בהן משקיעות החברות לבין עצמן. דוגמה נוספת לבחינה של סיכונים פיננסיים בעזרת ההמרה לרשתות היא בדיקה האם בנקים מסוימים הם "מרכזיים" מדי בשביל להיכשל[11].
  • שיווק- ניתן להיעזר בתורת הרשתות כדי לאתר מובילי דעת בתחום השיווק או כדי ליצור "שיווק ויראלי".
  • אכיפת חוק- תורת הרשתות לסיוע מערכת אכיפת החוק ותפיסת כנופיות פשע וטרור[12][13].

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Barabási, Albert-László, and Jennifer Frangos. Linked: The New Science Of Networks Science Of Networks. Basic Books, 2002.

אלברט-לסלו ברבאשי, "קישורים - המדע החדש של רשתות", הוצאת "חמד".

  • Christakis, Nicholas A. Connected: amazing power of social networks and how they shape our lives. HarperCollins Publishers, 2010.

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Borgatti, Stephen P., and Daniel S. Halgin. "On network theory." Organization Science 22.5 (2011): 1168-1181
  2. ^ ד"ר פנחס יחזקאלי, "רשת", אתר חברת TECI, מאי 2013.
  3. ^ 1 2 3 Barabási, Albert-László, and Jennifer Frangos. Linked: The New Science Of Networks Science Of Networks. Basic Books, 2002.
  4. ^ HC Lee ,”Network Theory Introduction”, The 13th Taiwan Nuclear Physics Summer School, 2009.
  5. ^ ראובן כהן, נילי מדר ושלמה הבלין, פיזיקה של רשתות, המגזין המקוון של החברה הישראלית לפיזיקה,2004.
  6. ^ Liebowitz, Stan J., and Stephen E. Margolis. "Network externality: An uncommon tragedy." The Journal of Economic Perspectives 8.2 (1994): 133-150.
  7. ^ Christakis, Nicholas A. Connected: amazing power of social networks and how they shape our lives. HarperCollins Publishers, 2010.
  8. ^ פנחס יחזקאלי, הצדעה ל"תורת האילוצים" הוותיקה של ד"ר אלי גולדרט, פוסט ברשת החברתית TheMarker Cafe
  9. ^ פנחס יחזקאלי, תורת הרשתות והמהפכה בעולם הניהול, פוסט ברשת החברתית TheMarker Cafe
  10. ^ Tatnall, Arther, and Anthony Gilding. "Actor-network theory and information systems research." Proceedings of the 10th Australasian Conference on Information Systems. 1999.
  11. ^ Battiston, Stefano, et al. "Guida Caldarelli, 2012,“DebtRank: Too Central to Fail? Financial Networks, the Fed and Systemic Risk,”." Nature.
  12. ^ פנחס יחזקאלי, "תורת רשתות" לסיוע מערכת אכיפת החוק, פוסט ברשת החברתית TheMarker Cafe
  13. ^ פנחס יחזקאלי, חקירת חיסולו של מחמוד אל-מבחוח - השימוש בתורת הרשתות לייצור ידע, פוסט ברשת החברתית TheMarker Cafe