Постановка задачи

Предлагается задача Community Detection поиска сообществ в неориентированном графе с весами, значения которых являются действительными неотрицательными числами.

Дан граф $G = (V,E)$ , где $V$ — множество вершин, $E$ — множество ребер, $w(u,v)$ — вес каждого ребра $e(u,v) \in E$ , $u,v \in V$ .

Цель задачи — найти такое разбиение графа $G$ на множество $C$ непересекающихся сообществ вершин $c_i \subseteq V$ :

\cup c_i = V

\forall c_i \in C

c_i \cap c_j = \varnothing

\forall c_i,c_j \in C, i \ne j

чтобы максимизировать функционал модулярности $Q$ :

Q = \sum\limits_{c \in C} \left(\frac{\sum_{in}^c}{m} - \lbrack\frac{\sum_{tot}^c}{m}\rbrack^2 \right)

, где

\sum_{in}^c = \sum_{u,v \in c, \; e(u,v) \in E} w(u,v)

\sum_{tot}^c = \sum_{in}^c + \sum_{u \in c, v \notin c, e(u,v) \in E} w(u,v)

m = \sum_{e(u,v) \in E} w(u,v)

Неформально, вершины одного сообщества должны быть сильно связаны, а вершины из разных сообществ должны быть слабо связаны.

Рисунок выполнен для графа ssca2-10 при помощи примера реализации и утилиты https://gephi.org.

Тестирование

Для оценки производительности реализаций используются три вида синтетических графов: RMAT, SSCA2 и LFR*.

R-MAT-графы [1] хорошо моделируют реальные графы из социальных сетей, Интернета.
SSCA2-граф [2] представляет собой набор независимых компонент, соединенных некоторым количеством ребер друг с другом.
LFR-граф [3] специально разработан для тестирования алгоритмов решения задачи поиска сообществ. В зависимости от параметров сообщества могут быть легко выделяемы или наоборот, сливаться. В конкурсе используется немного упрощенный LFR*-граф.

Один вычислительный узел

Три графа, на которых проводится тестирование производительности, секретны, их размер равен или чуть больше 3 Гигабайт (2^23 вершин). На вычислительном узле выложены графы, очень похожие на те, на которых проводится тестирование.

Многоузловой кластер

Тестирование проводится на 32 вычислительных узлах кластера на 3-х LFR-графах, количество вершин равно 2^25. Графы следует считывать из файлов.

Положение в таблице результатов

Позиция решения участника в итоговой таблице конкурса определяется при помощи функции подсчета рейтинга, которая кроме времени решения задачи учитывает значение полученной участником модулярности. Если модулярность больше модулярности примера реализации, то добавляется значительный бонус; если немного меньше (от 90% до 100%), то небольшой штраф; если модулярность меньше 90%, то назначается очень большой штраф. Полученное значение модулярности может быть любым. Функция подсчета рейтинга участника rating определяется следующим образом:

# mod - полученная участником модулярность
# mod_ref - модулярность, полученная при помощи примера реализации
# time - время работы алгоритма участника
ratio = mod / mod_ref 
if ratio > 1 then
    f = (ratio - 1)*10 + 1
else if 0.9 < ratio <= 1 then
    f = ratio
else
    f = 1.45e-10 * exp(25.0531 * ratio)

rating = 10000 * f / time

Значение коэффициента 1.45e-10 уточнено на сайте. В автоматической системе проведения конкурса рейтинг не изменялся и все время вычислялся с использованием коэффициента с большой точностью.

Параметры штрафа при ухудшении модулярности по сравнению с примером реализации более чем на 10%, выбраны таким образом, что при одном и то же времени решения задачи ухудшение относительной модулярности ratio от 0.9 до 0.7 ухудшает рейтинг в 150 раз.

При вычислении положения в таблице реализация участника тестируется на каждом из заданных графов. Для каждого графа автоматическая система вычисляет рейтинг по полученному времени, модулярности и известной модулярности примера реализации на данном графе. Итоговый рейтинг реализации участника является средним арифметическим полученных рейтингов.

Правила

Реализация задачи может использовать любой алгоритм. По своему усмотрению разработчики могут менять внутреннее представление графа, используя различные структуры данных, но время преобразований и всех предобработок, в том числе копирования данных на GPU, должно включаться во время решения задачи.

Требования к результату работы алгоритма решения задачи. Выходные данные должны содержать:

массив номеров сообществ, в котором для каждой вершины хранится номер сообщества.

Валидация отменена! Полученное значение модулярности может быть любым.

Вычислительные системы

Предлагается две категории систем для реализации задачи:

Один вычислительный узел (CPU и/или GPU).
Многоузловой кластер.

Организаторы предоставляют вычислительные ресурсы для участников в обеих категориях. Поощряются реализации для других архитектур, такие результаты будут рассматриваться отдельно.

Пример реализации

Версию 1.1 примера реализации лувенского алгоритма решения задачи, а также необходимую инфраструктуру для последовательной (одноузловой) генерации графов и вычисления модулярности можно скачать здесь: GraphHPC-1.1.tgz.

Вопросы

Если у Вас возникли какие-то вопросы, просьба писать по адресу contest@dislab.org.