Коефіцієнт кластеризації

В теорії графів коефіцієнт кластеризації є мірою ступеня, в якій вузли в графі мають тенденцію групуватися разом. Наявні дані свідчать про те, що в більшості реальних мереж, і, зокрема, в соціальних мережах, вузли, як правило, створюють тісно пов'язані групи, що характеризуються відносно високою щільністю зв'язків; ця ймовірність більше ніж середня ймовірність випадкового зв'язку між двома вузлами (Holland і Leinhardt, 1971; Watts and Strogatz, 1998).

Існують два варіанти цього терміну: глобальний і локальний. Глобальний варіант було створено для загального уявлення про кластеризацію в мережі, в той час як локальний описує вкладеність окремих вузлів.

Глобальний коефіцієнт кластеризації

Глобальний коефіцієнт кластеризації заснований на трійках вузлів. Трійка складається з трьох з'єднаних вузлів. Тому трикутник включає в себе три замкнуті трійки, по одній по центру на кожному з вузлів (n.b. це означає, що три трійки в трикутнику відбуваються водночас з перекриттям вибору вузлів). Глобальний коефіцієнт кластеризації — це число замкнутих трійок (або 3-х трикутників) над загальним числом трійок (відкритих і закритих). Перша спроба виміряти цей коефіцієнт була зроблена Луче і Перрі (1949). Цей термін дає вказівку на кластеризацію у всій мережі (глобальну), і може бути застосований до обох типів мереж: ненаправлених і спрямованих(часто званих транзитивними див. Вассерман і Фауст, 1994, стор. 243).

Глобальний коефіцієнт кластеризації визначається наступним чином:

${\displaystyle C={\frac {3\times {\mbox{number of triangles}}}{\mbox{number of connected triplets of vertices}}}={\frac {\mbox{number of closed triplets}}{\mbox{number of connected triplets of vertices}}}.}$

У цій формулі, зв'язана трійка визначається як зв'язний підграф, що складається з трьох вершин і двох ребер. Таким чином, кожен трикутник утворює три з'єднаних трійки, пояснюючи множення на три у формулі. Узагальнення на ^[en] було запропоноване Опсахлем і Панзарасою (2009), і перевизначення, двох режимів мереж(як бінарних так і вагових) було запропоноване Опсахлем (2009).

Локальний коефіціент кластеризації

Приклад локального коефіціенту кластеризації на неорієнтованому графі. Локальний коефіцієнт кластеризації синього вузла обчислюється як частка зв'язків між сусідами, які фактично реалізовані за допомогою порівняння з числом всіх можливих з'єднань. На малюнку, синій вузол має трьох сусідів, які можуть мати максимум 3 зв'язки між собою. У верхній частині малюнка всі три можливі зв'язки є реалізованими (товсті чорні сегменти), що дає нам локальний коефіцієнт кластеризації рівний 1. У середній частині малюнка тільки одне з'єднання є реалізованим (товста чорна лінія) і 2 з'єднання відсутні (пунктирні червоні лінії), що дає нам локальний коефіцієнт кластера рівний 1/3. І, нарешті, жоден з можливих зв'язків між сусідами синього вузла не буде реалізованим, що дає локальне значення коефіцієнта кластеризації рівне 0.

Локальний коефіціент кластеризації з вершиною (вузлом) в графі рахує, наскільки близько його сусіди повинні бути угруповані (повний граф). ^[en] і Стівен Строгац ввели цей термін в 1998 році, щоб визначити, чи є граф графом «Світ тісний».

Граф ${\displaystyle G=(V,E)}$ формально складається з безлічі вершин ${\displaystyle V}$ і набору ребер ${\displaystyle E}$ між ними. Ребро ${\displaystyle e_{ij}}$ з'єднує вершину ${\displaystyle v_{i}}$ з вершиною ${\displaystyle v_{j}}$.

окіл ${\displaystyle N_{i}}$ для вершини <математика> ${\displaystyle v_{i}}$ визначається за допомогою її сусідів, що пов'язані наступним чином:

${\displaystyle N_{i}=\{v_{j}:e_{ij}\in E\lor e_{ji}\in E\}.}$

Визначимо ${\displaystyle k_{i}}$ як число вершин, ${\displaystyle |N_{i}|}$, як околицю, ${\displaystyle N_{i}}$, як вершину.

Локальний коефіцієнт кластеризації ${\displaystyle C_{i}}$ для вершини ${\displaystyle v_{i}}$ далі визначається як зв'язки між вершинами в межах його околиць, розділені на кількість посилань, які могли б існувати між ними. Для орієнтованого графа, ${\displaystyle e_{ij}}$ відрізняється від ${\displaystyle e_{ji}}$, і, отже, для кожної околиці ${\displaystyle N_{i}}$ є ${\displaystyle k_{i}(k_{i}-1)}$ посиланнь, які можуть існувати серед вершин в околиці (${\displaystyle k_{i}}$ це число сусідів вершини). Таким чином, Локальний коефіціент кластеризації для орієнтованих графів задається як

${\displaystyle C_{i}={\frac {|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.}$

Неорієнтовані граф володіє такою властивістю, що ${\displaystyle e_{ij}}$ і ${\displaystyle e_{ji}}$ вважаються однаковими. Тому, якщо вершина ${\displaystyle v_{i}}$ має ${\displaystyle k_{i}}$ сусідів, ${\displaystyle {\frac {k_{i}(k_{i}-1)}{2}}}$ ребер може існувати серед вершин в межах околиці. Таким чином, Локальний коефіціент кластеризації для неорієнтованих графів може бути визначений як

${\displaystyle C_{i}={\frac {2|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.}$

Нехай ${\displaystyle \lambda _{G}(v)}$ — це кількість трикутників на множині вершин ${\displaystyle v\in V(G)}$ для неорієнтованого графа ${\displaystyle G}$. Тобто, ${\displaystyle \lambda _{G}(v)}$ це число підграфів ${\displaystyle G}$ з 3-ма ребрами і 3-ма вершинами, одна з яких ${\displaystyle v}$. Нехай ${\displaystyle \tau _{G}(v)}$ — це число трійок на ${\displaystyle v\in G}$. Тобто,${\displaystyle \tau _{G}(v)}$ — це число підграфів (не обов'язково інддукованих) з 2-ма ребрами і 3-ма вершинами, одна з яких є ${\displaystyle v}$ і таке, що ${\displaystyle v}$ інцидентна на обох краях. Тоді ми можемо визначити коефіцієнт кластеризації як

${\displaystyle C_{i}={\frac {\lambda _{G}(v)}{\tau _{G}(v)}}.}$

Легко показати, що два попередніх визначення є однаковими, так як

${\displaystyle \tau _{G}(v)=C({k_{i}},2)={\frac {1}{2}}k_{i}(k_{i}-1).}$

Ці міри є рівними 1, якщо кожен сусід зв'язаний із ${\displaystyle v_{i}}$ також пов'язаний з будь-якою іншою вершиною в околиці, і ці міри дорівнюють 0, якщо жодна з вершин, що пов'язана з ${\displaystyle v_{i}}$ зв'яжеться з будь-якою іншою вершиною, що пов'язана з ${\displaystyle v_{i}}$.

Мережевий середній коефіцієнт кластеризації

Як альтернатива глобального коефіцієнта кластеризації, загальний рівень кластеризації в мережі був виміряний Уоттсом та Строгацом як середнє значення локальних коефіцієнтів кластеризації всіх вершин ${\displaystyle n}$ :

${\displaystyle {\bar {C}}={\frac {1}{n}}\sum _{i=1}^{n}C_{i}.}$

Варто зазначити, що ця метрика розміщує більше ваги на низьких вузлів ступеня, в той час як співвідношення транзитивності поміщає більше ваги на високих вузлах ступеня. Насправді, зважене середнє, де кожна локальна оцінка кластеризації зважуються по ${\displaystyle k_{i}(k_{i}-1)}$ збігається з глобальним коефіцієнтом кластеризації.

Граф вважається графом «Світ тісний», якщо його середній локальний коефіцієнт кластеризації ${\displaystyle {\bar {C}}}$ значно вище, ніж у випадкового графа, побудованого на той самій множині вершин, а також якщо граф має приблизно таку ж відстань- найбільш коротку довжину шляху як і відповідний випадковий граф.

Узагальнення терміну ^[en] було запропоновано Барратом та ін. (2004), і перевизначення до двочасткових графів S (названих також дворежимними мережами) було запропоноване Латапу та ін. (2008) і Опсахлем (2009).

Ця формула не є визначеною для графів з ізольованими вершинами; див. Кайзер (2008) та Бармпотіусом та ін.. Мережі з максимально можливим середнім коефіцієнтом кластеризації мають модульну структуру, і в той же час, вони мають найменшу можливу середню відстань між різними вузлами.

Перколяції кластерних мереж

Для вивчення стійкості кластерних мереж був розроблений перколяційний підхід.

Примітки

1. and (1971). Transitivity in structural models of small groups. Comparative Group Studies. 2: 107—124.
2. and Steven Strogatz (June 1998). . Nature. 393 (6684): 440—442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998. Архів оригіналу за 25 Грудня 2010. Процитовано 27 Травня 2017.
3. and (1949). A method of matrix analysis of group structure. Psychometrika. 14 (1): 95—116. doi:10.1007/BF02289146. PMID 18152948.
4. , Kathrine Faust, 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.
5. and (2009). . Social Networks. 31 (2): 155—163. doi:10.1016/j.socnet.2009.02.002. Архів оригіналу за 1 Липня 2019. Процитовано 27 Травня 2017.
6. (2009). . Conference and Workshop on Two-Mode Social Analysis (Sept 30-Oct 2, 2009). Архів оригіналу за 21 Березня 2016. Процитовано 27 Травня 2017.
7. Kemper, Andreas (2009). . Springer. с. 142. ISBN . Архів оригіналу за 15 Травня 2019. Процитовано 27 Травня 2017.
8. Barrat, A.; Barthelemy, M.; Pastor-Satorras, R.; Vespignani, A. (2004). The architecture of complex weighted networks. Proceedings of the National Academy of Sciences. 101 (11): 3747—3752. arXiv:cond-mat/0311416. Bibcode:2004PNAS..101.3747B. doi:10.1073/pnas.0400087101. PMC 374315. PMID 15007165.
9. Latapy, M.; Magnien, C.; Del Vecchio, N. (2008). Basic Notions for the Analysis of Large Two-mode Networks. Social Networks. 30 (1): 31—48. doi:10.1016/j.socnet.2007.04.006.
10. Kaiser, Marcus (2008). Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks. New Journal of Physics. 10 (8): 083042. arXiv:0802.2512. Bibcode:2008NJPh...10h3042K. doi:10.1088/1367-2630/10/8/083042.
11. Barmpoutis, D.; Murray, R. M. (2010). Networks with the Smallest Average Distance and the Largest Average Clustering. arXiv:1007.4031 [q-bio.MN].
12. Newman, M. E. J. (2009). Random Graphs with Clustering. Physical Review Letters. 103 (5). doi:10.1103/PhysRevLett.103.058701. ISSN 0031-9007.
13. Huang, Wei-Min; Zhang, Li-Jie; Xu, Xin-Jian; Fu, Xinchu (2016). Contagion on complex networks with persuasion. Scientific Reports. 6: 23766. doi:10.1038/srep23766. ISSN 2045-2322.
14. Huang, Xuqing; Shao, Shuai; Wang, Huijuan; Buldyrev, Sergey V.; Eugene Stanley, H.; Havlin, Shlomo (2013). The robustness of interdependent clustered networks. EPL (Europhysics Letters). 101 (1): 18002. doi:10.1209/0295-5075/101/18002. ISSN 0295-5075.