Описание
Я хотел бы идентифицировать и получить кластеры размера n в виде групп узлов из набора данных неориентированного графа (оптимально в Python).В настоящее время я застрял в какой-то сфере за пределами моей зоны комфорта и знаний, поэтому я подумал, что, возможно, стоит попробовать обратиться к заинтересованным людям здесь.
Кластер здесь характеризуется как набор узлов, которые все взаимосвязанычерез (ненаправленный) край.Для упрощения все веса ребер можно рассматривать с весом = 1. Кроме того, нет никакой дополнительной информации, хранящейся ни в узлах, ни в ребрах.
Ниже на рисунке показана структура данных и зависимости
Схема графика
Для этого я стремлюсь найти решение, которое автоматически обнаруживает наборыузлов, которые полностью взаимосвязаны, как показано ниже:
Ожидаемые результаты кластера
Где размер кластера должен распознаваться динамически и всегда учитывать максимальное количество взаимосвязанныхузлы (например, n1 и n2 не считаются собственным кластером, поскольку n3 имеет связь с ними обоими).
Подходы
Я пытался решить эту проблему с помощью концепции сильно связанных компонентов, но, похоже, он не дает желаемого результата, так как соединение между всеми узлами не является направленным.Я попытался подойти к этой проблеме также в матричной форме, как показано ниже:
График в виде матрицы
Но мне не удается изящное решение, которое не включаетнемасштабируемый подход с использованием вложенных циклов, повторяющихся по индексам.
У кого-нибудь есть идеи о том, как подойти к этому или оптимально поработать над этим с помощью совместного решения, на которое я мог бы ориентироваться?Большое спасибо !!