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

входящую (indegree) и исходящую (outdegree) степенную центральность, в зависимости от того какие инцидентные дуги рассматривают при подсчете. На практике это позволяет выявить важных инициаторов сигналов или основных коллекторов, получающих сигнал от многих узлов сети. Важным является так называемая центральность по собственному вектору (Eigenvector centrality), которую можно рассматривать как разновидность степенной. Она отражает своего рода «полезную» степенную центальность вершины, то есть меру связи вершины с теми, которые в свою очередь имеют большое число инцидентных ребер. Один из распространенных алгоритмом для ее определения является - PageRank. Он работает итеративно, осуществляя последовательные переходы с некоторой вероятностью от произвольной начальной вершины к другим и уточняя начальную оценку центральности вершин, до того как сойдется или закончится заданное число итераций. Его вариацией является персонализированный PageRank (Personalised Page Rank), который ограничивает множество вершин для возможных переходов и тем самым позволяет оценить центральность выбранной вершины, исходя из дуг, инцидентных вершинам этого ограниченного набора. Еще одним видом графовых алгоритмов являются алгоритмы кластеризации вершин. Их также называют алгоритмами определения сообществ (Community Detection Algorithms) по распространенной прикладной задаче, решаемой ими. Эти алгоритмы направлены на выявления множеств вершин, связанных инцидентными им ребрами преимущественно между собой, чем с другими вершинами графа. При практическом применении эти алгоритмы используются в задачах определения групповых предпочтений, установления устойчивости социальных групп, визуализации графов. К алгоритмам этом группы в первую очередь относится алгоритмы определения числа треугольников (Triangle count) и локального коэффициента кластеризации (The local clustering coefficient). Треугольником называется клика из 3 вершин, то есть множество из трех вершин графа, в котором каждая соединена с двумя другими. Определение локального коэффициента кластеризации для вершины и ее прямых соседей — смежных с ней вершин, вычисляется как отношение удвоенного числа треугольников, включающих данную вершину, к количеству всех возможных связей между рассматриваемыми вершинами [4]. Тем самым, данные алгоритмы позволяют установит меру связности вершины и ее соседей между собой. Глобальный коэффициент кластеризации можно определить как средневзвешенную сумму локальных коэффициентов для всех вершин. Алгоритм определения компонент сильной связности (Strongly Connected Components, SCC) позволяет выявить такие наборы связанных вершин в ориентированном графе, где каждая вершина доступна в обоих направлениях от любой другой в этом же наборе. Для неориентированного графа применяется также похожий алгоритм для поиска связанных компонент (Connected Components), который отличается требованием только наличия пути между двумя вершинами. [5]. Оба алгоритма ввиду их сравнительно невысокой вычислительной сложности применяются для грубого выявления групп, предварительного анализа графа, поиске циклов, а также для общего понимания структуры графа. Следующим алгоритмом поиска сообществ является алгоритм распределения меток (Label Propagation algorithm, LPA). Идея, лежащая в основе 141