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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

Локальний коефіціент кластеризації[ред. | ред. код]

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

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

Граф формально складається з безлічі вершин і набору ребер між ними. Ребро з'єднує вершину з вершиною .

окіл для вершини <математика> визначається за допомогою її сусідів, що пов'язані наступним чином:

Визначимо як число вершин, , як околицю, , як вершину.

Локальний коефіцієнт кластеризації для вершини далі визначається як зв'язки між вершинами в межах його околиць, розділені на кількість посилань, які могли б існувати між ними. Для орієнтованого графа, відрізняється від , і, отже, для кожної околиці є посиланнь, які можуть існувати серед вершин в околиці ( це число сусідів вершини). Таким чином, Локальний коефіціент кластеризації для орієнтованих графів задається як[2]

Неорієнтовані граф володіє такою властивістю, що і вважаються однаковими. Тому, якщо вершина має сусідів, ребер може існувати серед вершин в межах околиці. Таким чином, Локальний коефіціент кластеризації для неорієнтованих графів може бути визначений як

Нехай  — це кількість трикутників на множині вершин для неорієнтованого графа . Тобто, це число підграфів з 3-ма ребрами і 3-ма вершинами, одна з яких . Нехай  — це число трійок на . Тобто, — це число підграфів (не обов'язково інддукованих) з 2-ма ребрами і 3-ма вершинами, одна з яких є і таке, що інцидентна на обох краях. Тоді ми можемо визначити коефіцієнт кластеризації як

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

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

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

Як альтернатива глобального коефіцієнта кластеризації, загальний рівень кластеризації в мережі був виміряний Уоттсом та Строгацом[2] як середнє значення локальних коефіцієнтів кластеризації всіх вершин  :[7]

Варто зазначити, що ця метрика розміщує більше ваги на низьких вузлів ступеня, в той час як співвідношення транзитивності поміщає більше ваги на високих вузлах ступеня. Насправді, зважене середнє, де кожна локальна оцінка кластеризації зважуються по збігається з глобальним коефіцієнтом кластеризації.

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

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

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

Перколяції кластерних мереж[ред. | ред. код]

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

Примітки[ред. | ред. код]

  1. P. W. Holland and S. Leinhardt (1971). Transitivity in structural models of small groups. Comparative Group Studies 2: 107–124. 
  2. а б в D. J. Watts and Steven Strogatz (June 1998). Collective dynamics of 'small-world' networks. Nature 393 (6684): 440–442. Bibcode:1998Natur.393..440W. PMID 9623998. doi:10.1038/30918. Архів оригіналу за 25 Грудня 2010. Процитовано 27 Травня 2017. 
  3. R. D. Luce and A. D. Perry (1949). A method of matrix analysis of group structure. Psychometrika 14 (1): 95–116. PMID 18152948. doi:10.1007/BF02289146. 
  4. Stanley Wasserman, Kathrine Faust, 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.
  5. Tore Opsahl and Pietro Panzarasa (2009). Clustering in Weighted Networks. Social Networks 31 (2): 155–163. doi:10.1016/j.socnet.2009.02.002. Архів оригіналу за 1 Липня 2019. Процитовано 27 Травня 2017. 
  6. а б Tore Opsahl (2009). Clustering in Two-mode Networks. Conference and Workshop on Two-Mode Social Analysis (Sept 30-Oct 2, 2009). Архів оригіналу за 21 Березня 2016. Процитовано 27 Травня 2017. 
  7. Kemper, Andreas (2009). Valuation of Network Effects in Software Markets: A Complex Networks Approach. Springer. с. 142. ISBN 9783790823660. Архів оригіналу за 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. Bibcode:2004PNAS..101.3747B. PMC 374315. PMID 15007165. arXiv:cond-mat/0311416. doi:10.1073/pnas.0400087101. 
  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. Bibcode:2008NJPh...10h3042K. arXiv:0802.2512. 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). ISSN 0031-9007. doi:10.1103/PhysRevLett.103.058701. 
  13. Huang, Wei-Min; Zhang, Li-Jie; Xu, Xin-Jian; Fu, Xinchu (2016). Contagion on complex networks with persuasion. Scientific Reports 6: 23766. ISSN 2045-2322. doi:10.1038/srep23766. 
  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. ISSN 0295-5075. doi:10.1209/0295-5075/101/18002.