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

применяемые для решения известных задач теории графов. Их можно разделить на следующие на 3 группы: • алгоритмы решения задачи поиска кратчайшего пути на графе и ее вариации; • алгоритмы определения центральности вершины (Degree centrality); • алгоритмы кластеризации вершин графа. В первую группу входят алгоритмы поиска в длину (Bread-first search, BFS) и ширину (Depth-first search, DFS), нахождение кратчайшего пути между каждой парой вершин из двух наборов (All pairs shortest path, APSP) нахождение пути от заданной вершины до всех вершин некоторого набора (Single-Source Shortest Paths, SSSP), поиск минимального связующего дерева (Minimum Spanning Tree, MST), т.е. набора дуг с минимальной суммарной стоимостью, соединяющих все вершины графа без учета циклов. Вторую группу составляют алгоритмы определения центральности вершины (Degree centrality). К ним относится вычисление центральности на основе близости вершин - центральность по близости (Closeness centrality), то есть определение вершин с кратчайшим расстоянием до всех остальных узлов. При решении практических задач это позволяет найти вершину, из которой наиболее быстро можно распространить некоторый сигнал по всей сети. Однако в реальных ситуациях графы часто являются несвязными. В этом случае длина пути между вершинами двух компонентов считается равной бесконечности, что в свою очередь приводит к неверным результатам оценки центральности (бесконечной центральности) для несвязанных узлов. В таких случаях применяют оценку центральности в рамках отдельных компонент графа с помощью алгоритма Вассермана-Фауста (Wasserman Faust) [2]. Иной способ подсчета центральность по близости для несвязных графов состоит в игнорирование бесконечных путей. Он реализован в алгоритме подсчета гармонической центральности (Harmonic/Valued Centrality) [3] и заключается в том, что бесконечный путь между несвязанными вершинами дает нулевой вклад в результирующую оценку центральности. Другой подход к определению центральности базируется на идее, что важные вершины располагаются на наиболее востребованных путях в графе. Это так называемая промежуточная центральность. Ее расчет можно применять для решения задач поиска «узких» мест или критических участков различных сетей. Для подсчета в этом случае применяется алгоритм, определяющий центральность вершины в зависимости от того, какая доля всех кратчайших путей между каждой парой вершин проходит через нее. Однако в больших графах перебор всех пар вершин может потребовать неприемлемое количество времени, поэтому используют более быстрый Randomized-Approximate (RA-brandes) алгоритм, дающий приблизительные результаты. Его отличие состоит в том, что рассматриваются не все пары узлов, а лишь их подмножество, которое определяется случайным образом или с учетом степени вершины, то есть вершины со сравнительно низкой степенью имеют низкую вероятность быть включенными в рассмотрение. Еще один вид центральности и одновременного способ ее подсчета это центральность по степени (degree centrality). Она определяется как отношение количества инцидентных вершине дуг к общему количеству вершин. Выделяют 140