Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ) вып. 9/2019(10)

алгоритма, состоит в итеративном присвоении метки некоторой вершины расширяющемуся кругу ее соседей по некоторым правилам. По завершении процесса распространения, исходя из присвоенных вершинам меток можно сделать вывод относительно структуры сообществ, представленных рассматриваемым графом. Вопрос присвоения или не присвоения метки некоторой вершине на каждой итерации определяется, исходя из количества соседних ей вершин, имеющих данную метку, а также веса инцидентных ребер. [6] Критериями для остановки распространения может является требование того, чтобы каждая вершина имела ту же метку, что и большинство ее соседей. В начале работы алгоритма уникальные метки присваиваются всем вершинам. Однако в этом случае, результаты его работы могут быть различными для разных попыток. Поэтому можно также присвоить так называемые “посевные” метки (Seed label) некоторым вершинам. Этом случае весьма вероятно, что их соседи будут наследовать именно их, что позволить стабилизировать вариационность полученных результатов. Следующий алгоритм для кластеризации является Лувенский алгоритм (Louvain Method) [7]. Считается одним из самых быстрых алгоритмов для графов большого размера (более 10 миллионов вершин). Наряду с обнаружением сообществ он также отражает их иерархию. Это позволяет выявить структуру сети на разных уровнях детализации - от больших групп до малых. Ключевым понятием данного алгоритма является модулярность. Она является мерой качества текущего распределения вершин графа по кластерам. Таким образом, в процессе работы для разбиения подсчитывается показатель модулярности, которая оптимизируется на последующих итерациях путем перераспределения вершин. Перераспределение, увеличивающее модулярность, заключается в формировании групп таким образом, чтобы внутри них вершины имели больше связей между собой, чем с вершинами других групп. Работа алгоритма состоит из двух повторяющихся шагов. На первом шаге для выбранных вершин с целью максимизации модулярности определяются группы из их прямых и непрямых соседей. На втором шаге на основе групп с первого шага происходит формирование более крупных групп. Это происходит на основе общего числа связей между вершинами отдельных групп, то есть две группы объединяются в одну большую, если общее число связей между их вершинами больше, чем с вершинами других групп. Среди графовых алгоритмов можно также выделить алгоритмы генерации графов Girvan-Newman (GN) [8] и Lancichi-netti-Fortunato-Radicchi (LFR) [9]. В основном они применяются для проверки алгоритмов определения сообществ. Для этого они позволяют сгенерировать граф с известным числом сообществ и характеристиками, похожими на характеристики реального графа, и провести тестирование выбранного алгоритма. 3. Особенности применения графовых баз данных Рассмотрим некоторые особенности графовых баз данных, которые необходимо учитывать при их использовании для решения задач анализа данных. В первую очередь, следует отметить, что следует избегать применения графовой модели для анализа транзакционных данных. Особенно если их объем (т.е. количество элементов) предполагается очень большим. Например, к этому можно 142