מקדם התקבצות

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

תוכן עניינים

1 הגדרות
- 1.1 הגדרות עזר
- 1.2 הגדרת מקדם ההתקבצות
2 הערות שוליים

[עריכה] הגדרות

מקדם ההתקבצות של הצומת המסומן במקרים שונים

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

תחילה נגדיר גרף כאוסף של $\ 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.