רשת מורכבת

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

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

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

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

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

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

רשתות נטולות קנה-מידה[עריכת קוד מקור | עריכה]

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

התעניינות ברשתות נטולות קנה-מידה התחיל בשנות ה-90 המאוחרות, עם הדיווחים על גילויים של התפלגויות Power-Law בעולם האמיתי, כגון World Wide Web, רשתות IP, רשתות-קשר בין חלבונים, ועוד. מרבית מהדיווחים על "Power-Laws" בעולם האמיתי נכשלו במבחן סטטיסטי קפדני יותר, אך הרעיון הכללי של רשתות המראות התפלגויות זנב-עבה באופן מובהק היה שונה לחלוטין ממה שהיה מצופה מרשת בעלת קצוות אקראיים ולא תלויים (כלומר, המקיימת את התפלגות פואסון).

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

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

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

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

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

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

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

  • Albert-László Barabási, Linked: How Everything is Connected to Everything Else, 2004, ISBN 0-452-28439-2
  • Alain Barrat, Marc Barthelemy, Alessandro Vespignani, Dynamical processes on complex networks, Cambridge University Press, 2008, ISBN 978-0-521-87950-7
  • Stefan Bornholdt (Editor) and Heinz Georg Schuster (Editor), Handbook of Graphs and Networks: From the Genome to the Internet, 2003, ISBN 3-527-40336-1
  • Guido Caldarelli, Scale-Free Networks Oxford University Press, 2007, ISBN 0-19-921151-7
  • Reuven Cohen and Shlomo Havlin, Complex Networks: Structure, Robustness and Function, Cambridge University Press, 2010, ISBN 978-0-521-84156-6
  • S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: From biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0-19-851590-1
  • Mark Newman, Networks: An Introduction, Oxford University Press, 2010, ISBN 978-0-199-20665-0
  • Mark Newman, Albert-László Barabási, and Duncan J. Watts, The Structure and Dynamics of Networks, Princeton University Press, Princeton, 2006, ISBN 978-0-691-11357-9
  • R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A statistical physics approach, Cambridge University Press, 2004, ISBN 0-521-82698-5
  • Duncan J. Watts, Six Degrees: The Science of a Connected Age, W. W. Norton & Company, 2003, ISBN 0-393-04142-5
  • Duncan J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness, Princeton University Press, 2003, ISBN 0-691-11704-7

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