Автор:  Егоркин А.А.
Название:  Определение центральности графа алгоритмом PageRank с учетом весов связей
Выпуск:  111
Рубрика:  Системный анализ
Год:  2024
Библиография:  Егоркин А.А. Определение центральности графа алгоритмом PageRank с учетом весов связей // Управление большими системами. Выпуск 111. М.: ИПУ РАН, 2024. С.81-96. DOI: https://doi.org/10.25728/ubs.2024.111.3
Ключевые слова:  центральность PageRank, цепи Маркова, взвешенный направленный граф
Ключевые слова (англ.):  PageRank, centrality, Markov chains, weighted directed graph
Аннотация:  Работа посвящена нахождению центральности узлов взвешенных графов с учетом веса связей. Актуальность этой задачи обусловлена тем, что игнорирование весов дуг графа при нахождении центральности его узлов недопустимо для ряда прикладных задач, в первую очередь относящихся к задачам из финансовой сферы. В классической постановке алгоритма PageRank происходит потеря части информации о весах связей при формировании матрицы переходных вероятностей из матрицы смежности. Данные эффект был продемонстрирован в настоящей статье. Предложен метод определения центральности узлов сети, базирующийся на алгоритме PageRank, который позволяет учесть веса всех связей. В качестве примера рассматривался граф финансовых транзакций. Узлами графа являются клиенты коммерческого банка в том числе сам банк, а дугами – денежные переводы между узлами. Качество ранжирования определялось путем сравнения различных мер центральности с внешним параметром, который характеризует важность узла и не связан с сетевыми характеристиками графа. По результатам исследования было показано, что предлагаемая мера центральности лучшим образом ранжирует наиболее важные узлы графа по сравнению с иными мерами центральности. Также была продемонстрирована сходимость предлагаемого алгоритма.
Аннотация (англ.):  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.

В формате PDF

Просмотров: 105, загрузок: 27, за месяц: 8.

Назад