מקדם התקבצות

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

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

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

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

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

גרף מוגדר כאוסף של \ n צמתים \ V={v_1,v_2,...v_n}, ואוסף של קשתות \ E, כך ש־\ e_{ij} היא קשת בין \ v_i ו־\ v_j. בהמשך נניח ש־\ v_i‏, \ v_j ו־\ v_k חברים ב־\ V.

הסביבה \ N_i של הצומת \ v_i מוגדרת כקבוצת הצמתים המחוברים אליו ישירות: N_i = \{v_j\} : v_j \in N_i, e_{ij} \in E.

הדרגה של הצומת \ v_i, היא מספר הצמתים המחוברים אליו ישירות, או מספר הצמתים בסביבתו, ותסומן \ k_i = |N_i|.

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

מקדם ההתקבצות \ C_i של הצומת \ v_i, הוא היחס בין מספר הקשתות בסביבה של \ v_i למספר הקשתות האפשריות בסביבתו (מספר הקשתות שהיו בסביבה, אילו היא הייתה גרף מושלם).

עבור גרף בלתי-מכוון, מספר הקשתות האפשריות הוא \frac{k_i(k_i-1)}{2} - טור חשבוני (סכום של סדרה חשבונית) מ־0 עד \ k_i-1. זאת מאחר שלצומת ה־\ k_i יש \ k_i-1 קשתות אפשריות, לצומת ה־\ k_i-1 יש \ k_i-2 קשתות אפשריות (הקשת עם הצומת ה־\ k_i כבר נספרה), וכך הלאה, עד שלצומת האחרון נותרות 0 קשתות אפשריות. כלומר, בכל סביבה \ N_i בגרף בלתי מכוון יש \frac{k_i(k_i-1)}{2} קשתות אפשריות. לכן, מקדם ההתקבצות \ C_i יהיה נתון על ידי:

C_i = \frac{|\{e_{jk}\}|}{\frac{k_i(k_i-1)}{2}} = \frac{2|\{e_{jk}\}|}{k_i(k_i-1)} : v_i \in V, v_j,v_k \in N_i, e_{jk} \in E

הביטוי במכנה מציין את מספר הקשרים האפשריים בסביבה \ N_i, בעוד שהביטוי במונה מציין את גודל קבוצת הקשתות \ e_{jk}, כך ש־\ v_j ו־\ v_k שייכים ל־\ N_i (כלומר, חלק מהסביבה של \ v_i), ו־\ e_{jk} שייך ל־\ E (כלומר, קשתות שאכן קיימות בגרף).

בגרף מכוון המצב דומה, אלא שעבור כל קשת בודדה \ e_{jk} בגרף הבלתי-מכוון, קיימות שתי קשתות "מקבילות" בגרף המכוון: \ e_{jk} ו־\ e_{kj}. לכן, מספר הקשתות האפשריות בגרף המכוון כפול ממספר הקשתות האפשריות בגרף הבלתי-מכוון. כלומר הביטוי למקדם ההתקבצות של צומת \ v_i יהיה:

C_i = \frac{|\{e_{jk}\}|}{k_i(k_i-1)} : v_i \in V, v_j,v_k \in N_i, e_{jk} \in E

אם מקדם ההתקבצות של צומת מסוים, \ v_i, שווה ל־1, זה אומר שהסביבה שלו, \ N_i, היא גרף מושלם, וכל הצמתים בה מחוברים זה לזה. אם מקדם ההתקבצות שלו הוא אפס, משמעות הדבר היא שהדרך היחידה לעבור בין שני צמתים בסביבה שלו היא דרכו - הוא היחיד שמחזיק את הסביבה מחוברת.

מקדם ההתקבצות של הגרף כולו, נחשב לממוצע מקדמי ההתקבצות של כל הצמתים בגרף: \overline{C} = \frac{1}{n}\sum_{i=1}^{n} C_i. בסוציולוגיה הגודל הזה מכונה לעתים "fraction of transitive triplets", אם כי עשויה להיות לו משמעות מתמטית שונה לעתים: היחס בין מספר הקשתות הקיימות למספר הקשתות האפשריות בגרף כולו.

באיור משמאל מוצגת סביבה בת 3 צמתים של הצומת המסומן, ומקדם ההתקבצות בקונפיגורציות שונות של קשתות: אם קיימות כל שלוש הקשתות, מקדם ההתקבצות הוא 1, אם קיימת קשת אחת מתוך שלוש, מקדם ההתקבצות הוא שליש, ואם אף צומת בסביבה של הצומת המסומן איננו מחובר לאחרים, מקדם ההתקבצות של הצומת המסומן הוא 0.

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

  1. ^ Collective dynamics of 'small-world' networks, Duncan J. Watts, Steven H. Strogatz, Nature, 1998‏ (pdf)