Треугольники VS Многоугольники: новые подходы к кластеризации в сетях

       Транзитивность, или коэффициент кластеризации, - одна из важнейших метрик сетевого анализа. Этот коэффициент рассчитывается как отношение числа замкнутых триад по отношению ко всем возможным (замкнутым и незамкнутым) триадам. Напомним, что замкнутые триады — это случай, при котором между тремя вершинами существуют все возможные связи. 

Типы триад. Источник.

       Соответственно, значения его колеблются от 0 (случай, когда замкнутых триад в графе нет) до 1 (случай полного графа, когда все триады замкнуты). Как было показано в работе Дункана Уоттса и Стивена Строгатца, в наблюдаемых социальных и биологических сетях коэффициент кластеризации, как правило, достаточно велик. Это позволяет сделать вывод о наличии тесно связанных групп в графе.

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

       Коэффициент кластеризации практически всегда используется для описания сетевых структур. Однако в последние годы возникло немало работ, которые не столько ставят под сомнение важность этого показателя, сколько заставляют задуматься о дополнительных сетевых индексах, иллюстрирующих особенности кластеризации и топологии сети, которые стоит принимать во внимание.

Глобальный и локальный коэффициент кластеризации

       Когда мы говорим о «коэффициенте кластеризации», то обычно подразумеваем глобальный коэффициент (global clustering coefficient), характеризующий склонность вершин формировать замкнутые триады. При этом мы не принимаем во внимание неоднородную природу сетей – ведь в ней могут быть одновременно как тесно связанные между собой кластеры, так и отдельные изолированные вершины.

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

       Рассмотрим различия в локальных коэффициентах кластеризации на примере (на рисунке ниже). С первого же взгляда вершины в данной сети можно разделить на две группы: вершины со связями и изолированные вершины. При более детальном рассмотрении группы связных вершин мы также видим принципиальные различия – вершины A, B, C, D и O тесно связано друг с другом, в то время как вершины H, J и F не связаны напрямую между собой. Так что в полученном связном компоненте выделяется один тесно связный кластер с высокими локальными коэффициентами показателей вершин, а также один мало связный кластер. 

Иллюстрация различий в локальном коэффициенте кластеризации

Пятиугольники – это тоже важно

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

       В работе Слейтера с коллегами, опубликованной в журнале Network Science, кластеризация в социальных сетях рассматривается не столько как результат формирования замкнутых триад, сколько как результат существования более крупных клик (групп, все вершины которых соединены друг с другом). Исследователи на примере большого числа наблюдаемых сетевых структур продемонстрировали, что клики размером 4-7 вершин встречаются в сетях значительно чаще, чем в случае случайных сетей.

Сеть с кликами из 6 (A, J, H, G, K, M) и 4 (D, E, F, L) вершин. Источник изображения

       Эти результаты подталкивают нас к более тщательному исследованию процессов формирования и эволюции социальных сетей с учетом сетевой кластеризации.

       Почти 20 лет назад Ваттс и Строгатц предложили модель формирования социальной сети «Малый мир», в основе которой лежал высокий коэффициент кластеризации. Недавние исследования показывают нам, что в сетях не все так просто и при анализе структуры и динамике сетевых структур необходимо принимать во внимание не только различные триадные структуры и связанный с ними коэффициент кластеризации, но и иные, более крупные и сложные мотивы.