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

В задаче кластеризации графа с данным количеством кластеров и их желаемыми размерами предлагается алгоритм решения и анализируются его свойства. Одной из мотиваций для данной постановки может быть задача аллокации серверов в нескольких больших вычислительных кластерах, где мы хотим связанные друг с другом объекты расположить в одном кластере для минимизации издержек при обмене сообщениями. Эта задача отличается от стандартной задачи нахождения комьюнити в графе. Для решения этой задачи мы применяем некоторые идеи, позаимствованные из метода Glauber Dynamics. В то же время в задаче не требуется никакой дополнительной информации о вершинах, кроме их ребер, поэтому задача носит характер обучения без учителя. Предлагается алгоритм для решения задачи и оценивается время его работы для достижения почти полного восстановления кластеров в модели mean-field SBM. Другим достоинством алгоритма является то, что он имеет локальную природу, что значит, что он может быть эффективно распределен без необходимости синхронизации.