Реализация распределенных алгоритмов расчета метрик качества кластеризации графов с использованием модели mapreduce и вершинно-ориентированных графовых вычислений

Резюме: Цель. Исследование особенностей реализации расчета метрик качества кластеризации графов с помощью модели вершинно-ориентированных вычислений и MapReduce. Материалы и методы. Для определения метрик качества использованы базовые понятия теории графов, а при разработке процедур их расчета — вычислительная парадигма MapReduce и вершинно-ориентированный подход, применяемый в графовых вычислениях. Результаты. Предложены и апробированы распределенные алгоритмы расчета метрик качества кластеризации графов. Выводы. Полученные результаты можно использовать для анализа качества разбиения больших графов, полученного с помощью произвольного алгоритма распределенной кластеризации.

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

G. Danilov, S.I. Rodzin

Distributed implementation of the graphs clusterization goodness metrics calculation using mapreduce and vertex-oriented graph processing model

Summary: Goal. Research of the implementation features of the graph clusterization goodness metrics using the vertexoriented graph computing model and MapReduce. Materials and methods. The basic concepts of graph theory were used to define the goodness metrics, and the MapReduce with a vertex-oriented graph-computational approach were used to develop the goodness metrics calculation algorithms. Results. Distributed algorithms for calculating graph clustering goodness metrics are proposed and tested. Conclusion. The results can be used to analyze the quality of the partitioning of large graphs that obtained using an arbitrary distributed clustering algorithm.

Keywords: Distributed graph processing, graph clustering, goodness metrics.

doi 10.34219/2078-8320-2020-11-3-31-35