Алгоритм распространения констант для задачи поиска сообществ в социальном графе
Автор студенческой работы: Светлана Илларионова
Свойства и структура алгоритмов[править]
Общее описание алгоритма[править]
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.
Математическое описание алгоритма[править]
Дан граф [math]\displaystyle{ G = (V, E) }[/math], где [math]\displaystyle{ V }[/math] — множество вершин, [math]\displaystyle{ E }[/math] — множество ребер, [math]\displaystyle{ w (u, v) }[/math] — вес каждого ребра [math]\displaystyle{ e(u, v) \in E, u, v \in V }[/math].
Цель задачи — найти такое разбиение графа [math]\displaystyle{ G }[/math] на множество [math]\displaystyle{ C }[/math] непересекающихся сообществ вершин [math]\displaystyle{ c_i \subseteq V }[/math]: [math]\displaystyle{ \cup c_i = V, \forall c_i \in C }[/math] [math]\displaystyle{ c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, }[/math] чтобы максимизировать функционал модулярности [math]\displaystyle{ Q }[/math]:
[math]\displaystyle{ Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right) }[/math],
где [math]\displaystyle{ \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), }[/math]
[math]\displaystyle{ \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v) }[/math],
[math]\displaystyle{ m = \sum_{e(u, v) \in E} w(u, v). }[/math]
[math]\displaystyle{ \sum_{in}^{c} }[/math] — сумма весов всех внутренних рёбер сообщества.
[math]\displaystyle{ \sum_{out}^{c} }[/math] — сумма весов всех рёбер, исходящих из вершин сообщества.
[math]\displaystyle{ m }[/math] — нормализующий коэффициент, сумма весов рёбер графа.
Вычислительное ядро алгоритма[править]
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.
Макроструктура алгоритма[править]
В реализации данного алгоритма нет необходимости выделять макроструктуры для его дальнейшего описания.
Схема реализации последовательного алгоритма[править]
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины [math]\displaystyle{ current }[/math]. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин [math]\displaystyle{ i }[/math]-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной [math]\displaystyle{ current }[/math]. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.
Последовательная сложность алгоритма[править]
Сложность алгоритма: [math]\displaystyle{ O(n + m) }[/math], где [math]\displaystyle{ n, m }[/math] — число вершин и ребер.
Информационный граф[править]
Данные на [math]\displaystyle{ i }[/math] итерации зависят от данных на [math]\displaystyle{ i- 1 }[/math] итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.
Ресурс параллелизма алгоритма[править]
Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.
Параллельная сложность: [math]\displaystyle{ O(n) }[/math], где [math]\displaystyle{ n }[/math] — число вершин. Это убословлено тем фактом, что [math]\displaystyle{ O(n + m) = O(n) + O(m) }[/math], так как есть часть алгоритма, которая обрабатывает ребра графа, и мы её можем распараллелить.
Входные и выходные данные алгоритма[править]
На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR. Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
Выходными данными алгоритма является множество меток вершин в зависимости от их принадлежности компонентам.
Свойства алгоритма[править]
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
- время работы
- количество итераций слабо зависит от размера графа
- прост в понимании
Недостатками алгоритма являются:
- недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
- при некоторых входных данных может давать плохие решения
Программная реализация алгоритма[править]
Особенности реализации последовательного алгоритма[править]
Локальность данных и вычислений[править]
Возможные способы и особенности параллельной реализации алгоритма[править]
Масштабируемость алгоритма и его реализации[править]
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
Размер графа [math]\displaystyle{ 2^{18} }[/math], средняя степень вершины 200. Без OpenMP.
| Число процессов | Число потоков | Время (с) |
|---|---|---|
| 1 | 1 | 29.7823 s. |
| 2 | 1 | 15.4772 s. |
| 4 | 1 | 8.2046 s. |
| 8 | 1 | 5.09298 s. |
| 16 | 1 | 2.63555 s. |
Размер графа [math]\displaystyle{ 2^{18} }[/math], средняя степень вершины 200. С OpenMP.
| Число процессов | Число потоков | Время (с) |
|---|---|---|
| 1 | 4 | 9.21499 s. |
| 2 | 4 | 4.37143 s. |
| 4 | 4 | 3.41528 s. |
| 8 | 4 | 3.87224 s. |
Размер графа [math]\displaystyle{ 2^{21} }[/math], средняя степень вершин 30. Без OpenMP
| Число процессов | Число потоков | Время (с) |
|---|---|---|
| 1 | 1 | 68.7771 s. |
| 2 | 1 | 36.1929 s |
| 4 | 1 | 21.6286 s. |
| 8 | 1 | 23.8237 s. |
Размер графа [math]\displaystyle{ 2^{21} }[/math], средняя степень вершин 30. C OpenMP
| Число процессов | Число потоков | Время (с) |
|---|---|---|
| 1 | 4 | 21.5797 s. |
| 2 | 4 | 11.7228 s. |
| 4 | 4 | 11.5657 s. |
Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.
Динамические характеристики и эффективность реализации алгоритма[править]
Выводы для классов архитектур[править]
Существующие реализации алгоритма[править]
Пример одноузловой реализации данного алгоритма описан в статье Engineering Parallel Algorithms for Community Detection in Massive Networks
Литература[править]
1. "Lancichinetti-Fortunato-Radicchi Benchmark." Wikipedia, the free encyclopedia. 30 October 2015. Web. 13 November 2016 https://en.wikipedia.org/wiki/Lancichinetti-Fortunato-Radicchi_Benchmark
2. "Help:Wiki markup." Wikipedia, the free encyclopedia. 12 November 2016. Web. 13 November 2016 https://en.wikipedia.org/wiki/Help:Wiki_markup
3. "Label Propagation Algorithm." 9 November 2016. Web. 13 November 2016. https://en.wikipedia.org/wiki/Label_Propagation_Algorithm
4. Спецкурс "Параллельная обработка больших графов" Лекция 4. к.т.н. Александр Сергеевич Семенов. 11 November 2016. Web. 13 November 2016. http://dislab.org/PLGP/PLGP_lecture4.pdf
5. "Sparse matrix." Wikipedia, the free encyclopedia. 30 October 2016. Web. 13 November 2016. https://en.wikipedia.org/wiki/Sparse_matrix
6. А.С.Антонов "Параллельное программирование с использованием технологии MPI".-М.: Изд-во МГУ, 2004.-71 с.
7. "OpenMP 4.5 Specifications" Nov 2015. Web. http://www.openmp.org/wp-content/uploads/openmp-4.5.pdf