Определение центральности графа алгоритмом PageRank с учетом весов связей

Автор(ы): Егоркин А.А.

Выпуск: 111

Рубрика: Системный анализ

Год: 2024

Библиография: Егоркин А.А. Определение центральности графа алгоритмом PageRank с учетом весов связей // Управление большими системами. Выпуск 111. М.: ИПУ РАН, 2024. С.81-96. DOI: https://doi.org/10.25728/ubs.2024.111.3

Дата опубликования: 30.09.2024

Ключевые слова: центральность PageRank, цепи Маркова, взвешенный направленный граф

Аннотация: Работа посвящена нахождению центральности узлов взвешенных графов с учетом веса связей. Актуальность этой задачи обусловлена тем, что игнорирование весов дуг графа при нахождении центральности его узлов недопустимо для ряда прикладных задач, в первую очередь относящихся к задачам из финансовой сферы. В классической постановке алгоритма PageRank происходит потеря части информации о весах связей при формировании матрицы переходных вероятностей из матрицы смежности. Данные эффект был продемонстрирован в настоящей статье. Предложен метод определения центральности узлов сети, базирующийся на алгоритме PageRank, который позволяет учесть веса всех связей. В качестве примера рассматривался граф финансовых транзакций. Узлами графа являются клиенты коммерческого банка в том числе сам банк, а дугами – денежные переводы между узлами. Качество ранжирования определялось путем сравнения различных мер центральности с внешним параметром, который характеризует важность узла и не связан с сетевыми характеристиками графа. По результатам исследования было показано, что предлагаемая мера центральности лучшим образом ранжирует наиболее важные узлы графа по сравнению с иными мерами центральности. Также была продемонстрирована сходимость предлагаемого алгоритма.

Author(s): Egorkin A.

Article title: PageRank centrality, accounting for the weights of links

Issue: 111

Year: 2024

Keywords: PageRank, centrality, Markov chains, weighted directed graph

Abstract: The work is devoted to finding the centrality of nodes of weighted graphs. The relevance of this task is due to the fact that ignoring the weights of the arcs of the graph when finding the centrality of its nodes is unacceptable for a number of applied tasks, primarily related to tasks from the financial sphere. In the classical formulation of the PageRank algorithm, part of the information about the weights of connections is lost when forming a matrix of transient probabilities from the adjacency matrix. This effect has been demonstrated in this article. A method for determining the centrality of network nodes is proposed, based on the PageRank algorithm, which allows taking into account all the weights of the links. The graph of financial transactions was considered as an example. The nodes of the graph are the clients of a commercial bank, including the bank itself, and the arcs are money transfers between nodes. The ranking quality was determined by comparing various centrality measures with an external node parameter unrelated to the network characteristics of the transaction graph. According to the results of the study, it was shown that the proposed centrality measure ranks the most important nodes of the graph in the best way compared to other centrality measures. The convergence of the proposed algorithm was also demonstrated.