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