Алговики - Вклад [ru]

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T22:17:32Z

LanaLana: /* Макроструктура алгоритма */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
В реализации данного алгоритма нет необходимости выделять макроструктуры для его дальнейшего описания.

== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рисунок 2. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

Параллельная сложность: <math>O(n)</math>, где <math>n</math> — число вершин.
Это убословлено тем фактом, что <math>O(n + m) = O(n) + O(m)</math>, так как есть часть алгоритма, которая обрабатывает ребра графа, и мы её можем распараллелить.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Выходными данными алгоритма является множество меток вершин в зависимости от их принадлежности компонентам.

== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 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>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==
Пример одноузловой реализации данного алгоритма описан в статье [https://arxiv.org/pdf/1304.4453.pdf 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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T19:25:44Z

LanaLana: /* Масштабируемость алгоритма и его реализации */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рисунок 2. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

Параллельная сложность: <math>O(n)</math>, где <math>n</math> — число вершин.
Это убословлено тем фактом, что <math>O(n + m) = O(n) + O(m)</math>, так как есть часть алгоритма, которая обрабатывает ребра графа, и мы её можем распараллелить.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Выходными данными алгоритма является множество меток вершин в зависимости от их принадлежности компонентам.

== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 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>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==
Пример одноузловой реализации данного алгоритма описан в статье [https://arxiv.org/pdf/1304.4453.pdf 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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T19:21:02Z

LanaLana: /* Входные и выходные данные алгоритма */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рисунок 2. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

Параллельная сложность: <math>O(n)</math>, где <math>n</math> — число вершин.
Это убословлено тем фактом, что <math>O(n + m) = O(n) + O(m)</math>, так как есть часть алгоритма, которая обрабатывает ребра графа, и мы её можем распараллелить.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Выходными данными алгоритма является множество меток вершин в зависимости от их принадлежности компонентам.

== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==
Пример одноузловой реализации данного алгоритма описан в статье [https://arxiv.org/pdf/1304.4453.pdf 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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T19:19:58Z

LanaLana: /* Существующие реализации алгоритма */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рисунок 2. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

Параллельная сложность: <math>O(n)</math>, где <math>n</math> — число вершин.
Это убословлено тем фактом, что <math>O(n + m) = O(n) + O(m)</math>, так как есть часть алгоритма, которая обрабатывает ребра графа, и мы её можем распараллелить.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
Выходными данными алгоритма является множество меток вершин в зависимости от их принадлежности компонентам.

== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==
Пример одноузловой реализации данного алгоритма описан в статье [https://arxiv.org/pdf/1304.4453.pdf 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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T19:08:57Z

LanaLana:

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рисунок 2. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

Параллельная сложность: <math>O(n)</math>, где <math>n</math> — число вершин.
Это убословлено тем фактом, что <math>O(n + m) = O(n) + O(m)</math>, так как есть часть алгоритма, которая обрабатывает ребра графа, и мы её можем распараллелить.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
Выходными данными алгоритма является множество меток вершин в зависимости от их принадлежности компонентам.

== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T19:06:05Z

LanaLana: /* Входные и выходные данные алгоритма */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рисунок 2. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

Параллельная сложность: <math>O(n)</math>, где <math>n</math> — число вершин.
Это убословлено тем фактом, что <math>O(n + m) = O(n) + O(m)</math>, так как есть часть алгоритма, которая обрабатывает ребра графа, и мы её можем распараллелить.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
Выходными данными алгоритма является множество меток вершин в зависимости от их принадлежности компонентам.

== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T19:02:56Z

LanaLana: /* Ресурс параллелизма алгоритма */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рисунок 2. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

Параллельная сложность: <math>O(n)</math>, где <math>n</math> — число вершин.
Это убословлено тем фактом, что <math>O(n + m) = O(n) + O(m)</math>, так как есть часть алгоритма, которая обрабатывает ребра графа, и мы её можем распараллелить.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T18:51:28Z

LanaLana: /* Информационный граф */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рисунок 2. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 2 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T18:50:48Z

LanaLana: /* Информационный граф */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
[[File:Community detection information graph.svg|thumb|right|100px|Рис.1. Информационный граф]]
Данные на <math>i</math> итерации зависят от данных на <math>i- 1</math> итерации. На рисунке 1 изображены вершины графа и влияние на их принадлежность той или иной компоненте на последующей итерации знаний о распределении вершин по компонентам на текущей итерации.

== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T18:05:07Z

LanaLana: /* Последовательная сложность алгоритма */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
Сложность алгоритма: <math>O(n + m)</math>, где <math>n, m</math> — число вершин и ребер.

== Информационный граф==
== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T17:59:18Z

LanaLana: /* Вычислительное ядро алгоритма */

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации. Вычислительное ядро включает в себя цикл, в котором необходимое число раз осуществляется прохождение по всем вершинам графа и отнесения их к соответствующим компонентам.

== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
== Информационный граф==
== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T15:34:28Z

LanaLana:

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами. Приведем примеры, где в реальной жизни могут втсречаться такие структуры: задачи, возникающие в социальной медиа структуре (то есть это многочисленные социальные сети), задачи, связанные с медициной и биоинформатикой, бизнес-задачи. Главная идея, которую преследуют, решая вышеперечисленные проблемы — это выделение из общей совокупности объектов, групп, объекты внутри которых сильно взаимосвязаны. В качестве подхода к решению будем рассматривать алгоритм Label Propagation, применяя который получим, что вершины одного сообщества будут сильно связаны, а вершины из разных сообществ будут слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
Вычислительное ядро — та часть алгоритма, на которую приходится основное время работы алгоритма. В данном случае к вычислительному ядру не относится только часть инициализации.
== Макроструктура алгоритма==
???
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
== Информационный граф==
== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==

==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T13:29:38Z

LanaLana:

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами.
В качестве подхода к решению будем рассматривать алгоритм Label Propagation.
Вершины одного сообщества должны быть сильно связаны, а вершины из разных сообществ должны быть слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма==
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
== Информационный граф==
== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==
==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

== Алгоритм решения==

== Результаты работы алгоритма ==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

=Литература =

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-20T13:29:13Z

LanaLana:

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

= Свойства и структура алгоритмов =
[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]
== Общее описание алгоритма==
Рассматривается задача поиска сообществ в неориенетированном графе с весами, значениями которых являются действительными неотрицательными числами.
В качестве подхода к решению будем рассматривать алгоритм Label Propagation.
Вершины одного сообщества должны быть сильно связаны, а вершины из разных сообществ должны быть слабо связаны.

== Математическое описание алгоритма ==

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма==
== Схема реализации последовательного алгоритма==
В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

== Последовательная сложность алгоритма==
== Информационный граф==
== Ресурс параллелизма алгоритма==

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Входные и выходные данные алгоритма==

На вход алгоритму подаётся граф, который хранится как разреженная матрица смежности в формате CSR.
Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.
== Свойства алгоритма==
К достоинствам алгоритма Label Propagation можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

=Программная реализация алгоритма=
==Особенности реализации последовательного алгоритма==
==Локальность данных и вычислений==
==Возможные способы и особенности параллельной реализации алгоритма==
==Масштабируемость алгоритма и его реализации==
==Динамические характеристики и эффективность реализации алгоритма==
==Выводы для классов архитектур==
==Существующие реализации алгоритма==

== Алгоритм решения==

== Результаты работы алгоритма ==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

== Литература ==

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-13T15:52:17Z

LanaLana:

Автор студенческой работы: [[Участник:LanaLana|Светлана Илларионова]]

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

[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]

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

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.
Вершины одного сообщества должны быть сильно связаны, а вершины из разных сообществ должны быть слабо связаны.

== Алгоритм решения==

В качестве подхода к решению будем рассматривать алгоритм Label Propagation. К достоинствам данного алгоритма можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

Граф хранится как разреженная матрица смежности в формате CSR.

Разбиваем мноество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Результаты работы алгоритма ==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

== Литература ==

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-13T15:46:50Z

LanaLana: /* Результаты работы алгоритма */

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

[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]

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

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.
Вершины одного сообщества должны быть сильно связаны, а вершины из разных сообществ должны быть слабо связаны.

== Алгоритм решения==

В качестве подхода к решению будем рассматривать алгоритм Label Propagation. К достоинствам данного алгоритма можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

Граф хранится как разреженная матрица смежности в формате CSR.

Разбиваем мноество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Результаты работы алгоритма ==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200. Без OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 29.7823 s.
|-
| 2
| 1
| 15.4772 s.
|-
| 4
| 1
| 8.2046 s.
|-
| 8
| 1
| 5.09298 s.
|}

Размер графа <math>2^{18}</math>, средняя степень вершины 200. С OpenMP.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.

== Литература ==

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-13T15:09:39Z

LanaLana:

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

[[file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщества]]

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

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

Цель задачи — найти такое разбиение графа <math>G</math> на множество <math>C</math> непересекающихся сообществ вершин <math>c_i \subseteq V</math>:
<math> \cup c_i = V, \forall c_i \in C </math>
<math> c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, </math> чтобы максимизировать функционал модулярности <math>Q</math>:

<math> Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)</math>,

где <math> \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), </math>

<math> \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)</math>,

<math> m = \sum_{e(u, v) \in E} w(u, v).</math>

<math>\sum_{in}^{c} </math> — сумма весов всех внутренних рёбер сообщества.

<math>\sum_{out}^{c} </math> — сумма весов всех рёбер, исходящих из вершин сообщества.

<math>m</math> — нормализующий коэффициент, сумма весов рёбер графа.
Вершины одного сообщества должны быть сильно связаны, а вершины из разных сообществ должны быть слабо связаны.

== Алгоритм решения==

В качестве подхода к решению будем рассматривать алгоритм Label Propagation. К достоинствам данного алгоритма можно отнести следующие его аспекты:
* время работы
* количество итераций слабо зависит от размера графа
* прост в понимании
Недостатками алгоритма являются:
* недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
* при некоторых входных данных может давать плохие решения

В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины <math>current</math>. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин <math>i</math>-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной <math>current</math>. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

Граф хранится как разреженная матрица смежности в формате CSR.

Разбиваем мноество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.

== Результаты работы алгоритма ==

Тестирование производилось на графах LFR (Lancichinetti-Fortunato-Radicchi), которые широко используются для анализа работы методов выделения сообществ в графах, так как являются хорошо приближенными к реальным моделям.

Размер графа <math>2^{18}</math>, средняя степень вершины 200.
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 9.21499 s.
|-
| 2
| 4
| 4.37143 s.
|-
| 4
| 4
| 3.41528 s.
|-
| 8
| 4
| 3.87224 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. Без OpenMP
{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 1
| 68.7771 s.

|-
| 2
| 1
| 36.1929 s
|-
| 4
| 1
| 21.6286 s.
|-
| 8
| 1
| 23.8237 s.
|}

Размер графа <math>2^{21}</math>, средняя степень вершин 30. C OpenMP

{| class="wikitable"
|-
! Число процессов
! Число потоков
! Время (с)
|-
| 1
| 4
| 21.5797 s.

|-
| 2
| 4
| 11.7228 s.
|-
| 4
| 4
| 11.5657 s.
|}

Алгоритм перестает масштабироваться, начиная с определенного момента, когда время синхронизации меток для вершин становится соразмерным с временем вычисления меток. Чем менье степень вершин, тем раньше алгоритм перестает масштабироваться.
== Литература ==

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

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-13T13:47:39Z

LanaLana:

Алгоритм распространения констант для задачи поиска сообществ в социальном графе

2016-11-13T12:38:54Z

LanaLana: Новая страница: «== Постановка задачи == file: Search-communities.jpg|thumb|right|200px|Рисунок 1. Пример разбиения на сообщест…»