По сути, целью кластеризации графов и методов обнаружения сообщества является вычисление кластеров. Есть ли разница между ними?
Нет. Цитируя, например, из Обнаружения сообщества в графиках , недавний и очень хороший опрос Санто Фортунато: «Эта функция реальных сетей называется структурой сообщества (Girvan and Newman, 2002) или кластеризацией». Нет никакого смысла в дальнейшей разработке этого вопроса, на самом деле. У меня есть ощущение, что в ранних статьях по анализу социальных сетей сети, как правило, были простыми (не взвешенными), но я бы не стал спорить об этом, и это не важно. Ответ на ваш вопрос - нет.
В « Обнаружении структур сообщества в сетях» М.Ньюман определяет кластеризацию графов как особую проблему, определенную в контексте компьютерных наук.
Давайте рассмотрим некоторые вычисления, которые можно разбить на несколько более простых операций. Они представлены как узлы в нашей сети. Ссылки соответствуют зависимостям между операциями, то есть результат одной операции нужен другой. Проблема заключается в распределении операций по нескольким процессорам для параллельной обработки. Другими словами, мы хотим назначить каждый узел (операцию) определенному классу (процессору), то есть мы хотим разбить график.
Однако есть три ограничения. Первый - получить заранее определенное количество сообществ, поскольку количество процессоров, очевидно, известно заранее. Второе - получить сбалансированную нагрузку: мы хотим, чтобы каждый процессор выполнял примерно одинаковое количество операций. С точки зрения графика, мы хотим, чтобы сообщества содержали примерно одинаковое количество узлов. Третье - получить минимально возможную связь между процессорами, потому что это замедляет процесс. Итак, с точки зрения графика, мы хотим минимизировать количество связей между сообществами.
Таким образом, с этой точки зрения обнаружение сообщества можно рассматривать как более общую проблему, чем кластеризация графов. Третье ограничение применяется в обеих проблемах, но количество и размеры сообществ априори не известны при обнаружении сообщества.
Эти два разных имени даны одной и той же вещью различными сообществами ученых, в зависимости от того, хотел бы кто-то подчеркнуть мотивацию социальных сетей или нет. Возможно, кто-то определяет кластеризацию и обнаружение сообщества как разные вещи, но большинство людей, которые изучают один из них, не смогут сказать вам, почему они не используют другой термин.
источник
Если большая сеть разбита на две части, что гарантирует вам, что эти две части представляют собой два сообщества? Два кластера имеют низкое соединение, это не означает, что каждый кластер имеет схожий тип узлов, или узлы имеют схожий тип соединений (следовательно, сообщество). Подумайте о графике социальных сетей. Там наверняка много сообществ. Также с помощью алгоритмов кластеризации вы можете разбить его на две части. В этом случае вы бы назвали каждую часть сообществом. ? Мой ответ - нет. Потому что два кластера могут быть людьми двух географических регионов. И тогда это, безусловно, не сообщества.
Алгоритмы кластеризации заботятся только о минимальном разрезе, а не о сходстве узлов, сходстве соединений или плотном соединении. Плюс в алгоритмах кластеризации количество кластеров должно быть предопределено.
Алгоритмы обнаружения сообществ, они заботятся о плотности, они находят более плотную часть сети, и такого рода алгоритмы (я видел до сих пор) не должны заранее определять количество сообществ.
Однако алгоритм поиска кластеров можно использовать для поиска сообществ, поэтому, поскольку он не гарантирует, что каждый кластер имеет хорошую структуру сообщества, каждый кластер должен быть тщательно изучен.
источник
«Нельзя тривиально применять обнаружение сообщества для решения проблемы кластеризации, и наоборот. Несмотря на их сходство, в подходах есть важные различия. Обнаружение сообщества предполагает разреженные соединения, в то время как кластеризация может работать с плотными наборами данных; в кластеризации мы обычно имеем дело с атрибутами нескольких типов в то время как обнаружение сообщества обычно имеет дело с одним типом атрибута - ребрами - часто двоичными, в случае невзвешенных сетей », для получения дополнительной информации читайте следующую статью:« Об эквивалентности между обнаружением и кластеризацией сообщества »Риккардо Гуидотти и Мишель Коссиа
источник