Повна версія

Головна arrow Інформатика arrow Моделирование сложных сетей

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

Коэффициент кластеризации

Д. Уаттс (D. Watts) и С. Строгатц (S. Strogatz) в 1998 году определили такой параметр сетей, как коэффициент кластеризации. Этот коэффициент характеризует тенденцию к образованию групп взаимосвязанных узлов, так называемых клик (Clique). Для конкретного узла коэффициент кластеризации показывает, сколько ближайших соседей данного узла являются также ближайшими соседями друг для друга.

Пусть из узла выходит k связей, которые соединяют его с k другими узлами, ближайшими соседями. Если предположить, что все ближайшие соседи соединены непосредственно друг с другом, то количество связей между ними составляло бы к (к —1)/2. То есть это число, которое

соответствует максимально возможному количеству связей, которыми могли бы соединяться ближайшие соседи выбранного узла.

Отношение реального количества связей, которые соединяют ближайших соседей данного узла 1 к максимально возможному (такому, при котором все ближайшие соседи данного узла были бы соединены непосредственно друг с другом) называется коэффициентом кластеризации узла С1. Естественно, эта величина не превышает единицы.

Коэффициент кластеризации

может определяться как для каждого узла, так и для всей сети:

Watts D.J., Strogatz S.H. Collective dynamics

of "small-world" networks. Nature, 1998. - Vol. 393. -pp. 440-442.

В социальных сетях можно говорить о "структуре сообщества", когда существуют группы узлов, которые имеют высокую плотность связей между собой, при том, что плотность ребер между отдельными группами - низкая. Для больших социальных сетей наличие структуры сообществ оказалось неотъемлемым свойством. Традиционный метод для выявления структуры сообществ - кластерный анализ. Существуют десятки приемлемых для этого методов, которые базируются на разных мерах расстояний между узлами, взвешенных путевых индексах между узлами и т.п.

 
<<   ЗМІСТ   >>