רשת מורכבת

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

הגדרה

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

רשתות נטולות קנה-מידה

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

רשתות עולם-קטן

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