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

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