Клика

Клика

Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе (Задача о клике) является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик. Клика размера 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 участников

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

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

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

Дополнение о группах

http://faculty.ucr.edu/~hanneman/nettext/C11_Cliques.html - О кликах и других субструктурах в сети.

Как только между узлами возникает связь они становятся группой. В биграфе социальная связь формируется через социальный объект

The idea of a clique is relatively simple. At the most general level, a clique is a sub-set of a network in which the actors are more closely and intensely tied to one another than they are to other members of the network. In terms of friendship ties, for example, it is not unusual for people in human groups to form "cliques" on the basis of age, gender, race, ethnicity, religion/ideology, and many other things. The smallest "cliques" are composed of two actors: the dyad. But dyads can be "extended" to become more and more inclusive -- forming strong or closely connected regions in graphs. A number of approaches to finding groups in graphs can be developed by extending the close-coupling of dyads to larger structures.

Диада - наименьшая клика, состоящая из 2 узлов