Задача
Дан неориентированный граф без весов G = (V,E) . Цель задачи — для каждой вершины графа v вычислить значение Betweenness Centrality:
BC(v) = \sum\limits_{s \ne v \ne t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}} , где
\sigma_{st} — количество кратчайших путей между вершинами s и t , а \sigma_{st}(v) — количество кратчайших путей между вершинами s и t , проходящих через вершину v .
Тестовые системы
  • Мощный SMP-узел (28 ядер) c NVIDIA GPU K20x.
  • 36-узловой вычислительный кластер с сетью Ангара.
Правила
  • Можно использовать любой язык и технологию программирования (рекомендуется C/C++, OpenMP, CUDA, MPI).
  • Можно использовать любой алгоритм.
  • Итоговая оценка определяется, в первую очередь, размером обработанного графа, а затем скоростью его обработки.
  • В примере на C++ реализовано решение задачи. Немного улучшив пример реализации, даже неопытные участники могут легко попасть в таблицу результатов.
Принять участие
  • Начать решать задачу можно уже сейчас.
  • Доступ на тестовые системы осуществляется с помощью SSH начиная с 1-го февраля 2017.