Клика

Версия 20:42, 22 февраля 2016

Клика - сплоченная группировка = подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом.

• Исходно социальный термин «клика» переопределяется в теории сетей как «набор узлов, где каждый узел прямо связан со всеми остальными».

Клика размера n -- это такой граф, в котором n вершин, причем каждая связана с каждой. Распределение размера клик обычно подчиняется power-law, а сами клики соответствуют "ядрам" некоторых сообществ.

Определение и выявление клик

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

Если сеть включает в себя части с тесными связями между узлами, т.е. с высоким значением C, которые соединены лишь редкими связями между собой, то такая сеть отличается наличием клик, или «коммунальной структурой» (community structure, cliquishness). Исходно социальный термин «клика» переопределяется в теории сетей как «набор узлов, где каждый узел прямо связан со всеми остальными». Сетевая структура, построенная в основном на кооперации еѐ узлов, часто состоит из большого числа плотных подсетей (кластеров), разделѐнных зонами с редкими связями (примером могут служить именно так устроенные стаи многих видов рыб или аналогично устроенная сеть World Wide Web). Такая кластеризация в существенно меньшей мере присуща традиционным рынкам в человеческом обществе и аналогичным конкурентным системам в биологическом мире и в мире технических информационных устройств. Соответственно, кооперативные сетевые структуры оказываются гетерогенными в плане коэффициента кластеризации. Коэффициент С достигает высокого уровня у тех узлов, которые включены в состак кластеров (клик, подсетей); этот коэффициент низок в зонах сети, расположенных между еѐ кластерами. Рынки и их аналоги часто характеризуются более равномерно распределѐнными по всей рыночной структуре значениями С, что связано с автономных характером каждого из узлов – каждого из агентов, вступающих в (квази)рыночные отношения (контракты в человеческм обществе; метаболические отношения в биосистемах).

• см. Олескин А.В. Сети как неиерархические и нерыночные структуры: реализация в биологических и социальных системах // Экономические стратегии. 2013. № 5. С. 2–7.

Кликами (cliques) называются полносвязные подграфы некоторой сети. Изучение сообществ (communities) в сетях имеет довольно длительную историю. Оно тесно связано с задачами разбиения графов на подграфы. В последние годы разработка соответствующих методов получила сильный импульс в теории сложных сетей социальной природы. Под сообществами понимаются подграфы, для которых связи между узлами внутри подграфов сильнее и многочисленнее, насыщеннее, чем между узлами различных подграфов.

В алгоритме, предложенном Гирваном и Ньюманом [Newman, Girvan, 2004], связи с максимальной важностью (betweenness centrality) удаляются одна за другой. Каждое такое удаление изменяет структуру кратчайших путей в сети, а следовательно, и важность каждой связи, и поэтому эти параметры пересчитываются после каждого удаления.

nw:maximal-cliques

A clique is a subset of a network in which every node has a direct link to every other node. A maximal clique is a clique that is not, itself, contained in a bigger clique.

Максимальная клика

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

nw:biggest-maximal-cliques

The biggest maximal cliques are, as the name implies, the biggest cliques in the current context. Often, more than one clique are tied for the title of biggest clique, so the result if reported as a list of agentsets, in random order. If you want only one clique, use one-of nw:biggest-maximal-cliques.

Как мы получили клику?

show one-of nw:biggest-maximal-cliques

ask users [set color 5] ask first sort-by [count ?1 > count ?2] nw:maximal-cliques [set color 15]

ask users [set color 5] ask first nw:biggest-maximal-cliques [set color 15]

foreach  nw:biggest-maximal-cliques [ask ? [bank_color] ]

И мы получили 2 сплоченные группы черепах Netlogo, которые к тому же пересекаются между собой.

Клика = сообщество тесно связанных участников, каждый из которых через объекты общей деятельности связан с другими участниками этого сообщества

Пример сообщества из 17 участников, работавших в общем проекте на 739 участников

Педагогический смысл

О чем говорит обнаружение клик и размеры клик?

О том, что между этими участниками идет активная коллаборация