[ציור השער הוא מתוך תערוכת "מי מפחד ממתמטיקה" מוזיאון המדע בירושלים] (ר' קישורים בטקסט)
מה מתרחש (: אני אסף שפירא וזה נטפריקס – הפודקאסט העברי הראשון למדע הרשתות.
לא פעם השתמשנו לצד המונח "רשת" ממדע הרשתות גם במונח "גרף", מתורת הגרפים. זה נשמע קצת אותו דבר, אבל זה לא בדיוק. שמתי לב לבעיית ההמשגה הזו כשעדכנו את הערכים בויקיפדיה והוספנו את הערך "מדע הרשתות". אז נעשה קצת סדר. מדע הרשתות נמצא בתווך בין שני תחומים: מצידו האחד של מדע הרשתות נמצא תחום תורת הגרפים, שהיא במקור מתחום המתמטיקה, ועוסקת במודלים תאורטיים של גרפים. בתורת הגרפים, לא אכפת לנו מה מהות הנקודות והקווים ברשת שאנו מסתכלים עליה. ההסתכלות היא מתמטית טהורה. מצידו האחר של מדע הרשתות, ישנו תחום ניתוח הרשתות החברתיות, או SNA, שזהו תחום השואב ממדעי החברה ועוסק במחקר רשתות שהצמתים בהם הם אנשים. התחום הזה מחפש תובנות שהן יותר רלבנטיות למחקר האנושי ופחות למחקר של הרשת. מדע הרשתות עצמו מתמקד ברשתות אמיתיות, או רשתות כפי שהן בטבע, ולא בגרפים תיאורטיים. למשל, רשתות של נוירונים במוח, רשתות חשמל, רשת מגעים של התפשטות הקורונה או רשתות של מטבעות קריפטו. מה שכן, הוא עושה שימוש במושגי יסוד ובמודלים תאורטיים מתורת הגרפים למשל לצורכי השוואה לרשתות עולם אמיתי. גם תורת הגרפים וגם SNA הקדימו את מדע הרשתות. ובמקרה של תורת הגרפים, היא הקדימה אותו בלמעלה מ-280 שנה. כל מי שאי פעם נגע או נגעה בתורת הגרפים, מכירים את החידה בנושא שבעת הגשרים של קניגסברג ואת הפתרון שלה. אני שונא לספר סיפור שכולם מכירים, אז אני די בטוח שאותם אנשים לא מכירים את הפתרון הנוסף שנמצא לחידה. אבל נתחיל בסיפור הקלאסי: העיר קניגסברג, ששכנה בפרוסיה המזרחית, נחצתה על ידי הנהר פְּרֵגוֹלְיָה. הנהר היה רחב מאד ובמרכזו היו שני איים קטנים. העיר נוסדה במאה ה-13 ובמרוצת השנים נבנו בה שבעה גשרים. בגלל רוחבו, הגשרים בין הגדות עברו דרך האיים במרכז הנהר: גם מהגדה הדרומית וגם מהגדה הצפונית יצאו 2 גשרים לאי המערבי, כלומר, 4 גשרים סה"כ. גם מהגדה הדרומית וגם מהגדה הצפונית יצא גשר לאי המזרחי, כלומר 2 גשרים. ועוד גשר נוסף חיבר בין שני האיים.
האגדה מספרת שהתושבים בילו את זמנם הפנוי במסלולים ברחבי העיר בניסיון למצוא מסלול שבו יוכלו לחצות כל אחד מהגשרים פעם אחת.
ב-1736, במסגרת חליפת מכתבים עם מתמטיקאים נלהבים, הוצג ללאונרד אוֹילֶר, המתמטיקאי המפורסם, אותו אתגר מסלולי של גשרי קניגסברג. מכיוון שלא היתה אז תורת גרפים, אוילר הגדיר את הבעיה כשייכת לענף איזוטרי שהוא כינה "הגיאומטריה של המיקום", תחום שבו למרחקים בין העצמים אין חשיבות. את התיאור של הפתרון שלו הוא ניסח ללא שימוש פעם אחת במילים קשת או דרגה, מושגים שלא היו קיימים אז.
קשת היא הקשר בין הצמתים ואוילר לא מתייחס לקשרים בכלל. כנראה הניח שהקשרים ברורים מאליהם. דרגה, אגב, היא כמות הצמתים שהצומת קשורה אליה. במקרה שלנו, לכמה חלקי יבשה כל גדה או אי קשורים. אבל אוילר לא התכוון לסתם דרגה, אלא לדרגה ממושקלת. למה הכוונה?
אמרנו שבדרגה רגילה, אנחנו סופרים לכמה צמתים אנחנו קשורים. בדרגה ממושקלת, אנחנו סופרים כמה קשרים יש לכל צומת, גם אם הם כפולים. משקל, במובן הרשתי, הוא כמות הקשרים בין שני צמתים, למשל, אם אנחנו עוקבים אחרי הודעות ברשת, ושלחנו הודעה למישהו והוא שלח לנו חזרה, הדרגה הרגילה של כל אחד מאיתנו תהיה 1 אבל משקל הקשר שלנו יהיה 2. כלומר, הדרגה הממושקלת של כל אחד מאיתנו תהיה 2. כך, דרגה ממושקלת בהכרח תהיה שווה או גבוהה יותר מהדרגה הרגילה. למה אנחנו מתייחסים כאן לדרגה ממושקלת? כי במקרה שלנו, שני גשרים שמחברים את אותם שני צמתים זה שני קשרים שונים. זה לא אותו גשר שרוכבים עליו הלוך ושוב. אז מה שאוילר ניסח במושגים של ימינו הוא שניתן לעבור בין צמתים בגרף ולא לחזור על אותה קשת, רק אם כל הדרגות הממושקלות של הצמתים בגרף הם זוגיות או שהגרף מכיל שני צמתים עם דרגה ממושקלת לא זוגית. במקרה של קניגסברג, יש לנו שתי גדות, כשלכל אחת מהן דרגה ממושקלת של 3 ושני איים: אחד עם דרגה ממושקלת של 3 ואחד עם דרגה ממושקלת של 5. מכיוון שיש יותר משני צמתים אי-זוגיים, אוילר הכריז כי אין מסלול אפשרי וחרב תרבות פנאי של עיר שלמה.
אז לפני שנמשיך על אוילר, גילוי נאות על דרגה ממושקלת ביחס לדרגה רגילה. אני אישית חושב שדרגה ממושקלת זה מדד קצת מעפן. למה? כי הוא לא מספר לנו בהכרח על מרכזיות הצומת ברשת. זה אמנם נכון שצומת עם דרגה גבוהה תקבל גם דרגה ממושקלת גבוהה, אבל מה לגבי צומת שיש לו הרבה קשרים אבל כולם עם צומת בודד אחר? למרות שהוא קשור רק לצומת אחד, ולכן כנראה אין לו הרבה השפעה על הרשת, הצומת הזה יופיע כבעל דרגה ממושקלת גבוהה. אז כמו שראינו, יש לזה לפעמים שימוש, אבל, ותקראו לי שמרן, תנו לי את הדרגה הרגילה כל יום בשבוע וחיסכו ממני את הדרגות הממושקלות. באתי להרים לתורת הגרפים ויצאתי קצת מבאס. סורי. אבל באותה נימה נחזור לאוילר. כל מי שעוסק בתורת הגרפים ומדע הרשתות יצטט את אוילר כאבי התחום, אבל האם אוילר באמת הניח את היסודות לתפיסה? קצת בספק. הוא אפילו לא טרח להוכיח רשמית את המשפט שלו והיו צריכות לעבור עוד כ-130 שנה עד שמישהו יעשה זאת. ואפרופו הוכחות, מאות השנים שעברו מוכיחות שבמשך תקופה ארוכה תורת הגרפים נתפסה יותר כשעשוע מתמטי מאשר פרקטיקה מכובדת. ובינינו, זה ממש בסדר ועכשיו נרים חזרה: אין שום בושה לדעתי בלהגיד שתורת הגרפים זה סטארט אפ שפשוט הקדים את זמנו. לקח כמה מאות שנים, אבל בסוף עשה את האקזיט עם מנוע החיפוש של גוגל, חברה קטנה בשם פייסבוק והניח את היסודות לווייז. יזמות ויזמים יקרים – צריך רק סבלנות.
אבל מה נסגר עם קניגסברג? אז קניגסברג היא כבר כיום קאלינינגרד. לקראת סוף מלחמת העולם השניה, הרוסים הצליחו לכבוש את העיר מידי הנאצים. החדשות הרעות הן שבמהלך ההפצצות של בנות הברית, נהרסו לפחות חמישה מהגשרים ורק חלקם שוקמו במהלך השנים.
אבל החדשות הטובות הן שהצבא הרוסי מצא גם הוא פתרון לאתגר של אוילר, אולי באופן קצת פחות אלגנטי:
מכיוון שרק חלק משבעת הגשרים שוקמו, הדבר השאיר שתי גדות עם דרגה של 2 ושני איים עם דרגה של 3. מכיוון שבגרף שנוצר יש שני צמתים אי זוגיים, מיטיבי לכת יכולים כיום לחצות את כל הגשרים במסלול אחד.
אז מה, רוצים להרחיב את קהילת מדע הרשתות בישראל? ככל שתדרגו יותר, כך הפודקאסט יהיה חשוף לאנשים רבים יותר.
דרגו את הפודקאסט בספוטיפיי או באפל-פודקאסטס ו/או כיתבו ביקורת. ניתן לדרג גם בפודקאסט-אדיקט (בטאב של ה-reviews). מותר ומומלץ להעלות פוסט ולתייג את נטפריקס בפייסבוק/טוויטר/אינסטגרם או לינקדאין ושוב, פוסטים יצירתיים במיוחד יושמעו בפרקים הבאים.
ואם עוד לא עשיתם לייק בדף של נטפריקס בפייסבוק, זה הזמן. אתרים עם יותר לייקים, מקבלים יותר חשיפה.
לפניות/הערות/הארות/הצעות ועוד: שלחו מייל!
ולא לשכוח לעשות Subscribe לפודקאסט בכל אפליקציה שבה אתם או אתן שומעים פודקאסטים. לאלה שהצטרפו לא מזמן, אז החל מ-2021, קיימת גרסה של הפודקאסט נטפריקס גם באנגלית,
נכון להיום, האזינו לפודקאסט ביותר מ-57 מדינות, מניו זילנד ועד הוואי (:
הפרקים הראשונים דומים במהותם לפרקים בעברית, ואולי קצת יותר מעודכנים, אך הפרקים האחרונים כוללים תכנים ייחודיים שלא כולם נכנסו לגרסה העברית. מוזמנים לבדוק ואשמח מאד לפידבקים.
אשמח מאד גם לקבל פידבקים על הפורמט של סדרת הפרקים הקצרים. זה מתאים, לא מתאים? קצר מדי? מעט מדי? מאוחר מדי?
נתראה בפרק הבא של נטפריקס.
#NetworkScience #SNA #SocialNetworkAnalysis #GraphTheory #DataScience #Google #Facebook #Waze