מקדם התקבצות

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

הגדרות

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

הגדרות עזר

גרף מוגדר כאוסף של $\ 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.

קישורים חיצוניים

מדיה וקבצים בנושא מקדם התקבצות בוויקישיתוף