Демонстрация использования алгоритма "PageRank" на графе со сложными атрибутами вершин и ребёр.
sudo apt install ccache
sudo apt install ninja-buildgit clone https://github.com/SparseLinearAlgebra/PageRankBenchmark.git
cd PageRankBenchmark
git submodule init
git submodule update —recursive
make build./build/main
Полный код разбираемого примера можно увидеть в файле.
Цель примера --- показать, как в рамках GraphBLAS можно работать со сложными атрибутами вершин и рёбер графа.
В качестве примера возьмём следующую задачу. Пусть есть граф с двумя типами вершин: пользователи и карты. Также есть два типа ориентированных рёбер:
- "Перевод": соединяет две карты (откуда и куда перевод)
- "Владеет": соединяет пользователя и карту (от владельца карты к карте)
Каждый тип вершины имеет свой набор атрибутов.
- "Пользователь": пол, возраст
- "Карта": тип, лимит средств
Пусть будут следующие типы карт: МИР, VISA, MASTERCARD.
При этом рёбра типа "Перевод" в качестве атрибутов содержат общую сумму и "количество транзакций". Рёбра типа "Владеет" не имеют атрибутов.
Для примера возьмём следующий граф.
У каждой вершины есть уникальный идентификатор, синие рёбра отображают переводы, красные --- отношение владения, розовые вершины --- пользователи, синие --- карты.
Хотим выбрать по некоторому критерию пользователей и их карты, а затем для анализа переводов хотим посчитать PageRank на подграфе, заданном переводами между отобранными картами. Выбрать хотим все карты системы "МИР", которыми владеют люди старше заданного возраста. Покажем, как это можно сделать, используя матрично-векторные операции, в частности GraphBLAS.
GraphBLAS позволяет в качестве атрибутов использовать пользовательские типы (фиксированных размеров), потому объявим необходимый нам набор типов.
// Тип карты
typedef enum
{
VISA,
MIR,
MASTERCARD,
} System;
// Пол
typedef enum
{
MALE,
FEMALE,
} Gender;
// Данные о пользователе
typedef struct
{
Gender gender;
uint8_t age;
} User;
// Данные о карте
typedef struct
{
System system;
double limit;
} Card;
// Данные о переводах
typedef struct
{
double sum;
uint32_t count;
} EdgeTX;Граф представлен как набор матриц и векторов: по одной матрице на каждый тип рёбер и по одному вектору на каждый тип вершин. Матрицы и вектора в большинстве случаев будут разреженными и мы будем использовать символ '$.$' для обозначения отсутствующего элемента. Считаем при этом, что все вершины, вне зависимости от типа, занумерованы с 0 подряд (id вершин на рисунке). Таким образом, нам понадобятся две матрицы:
И два вектора:
Первым делом фильтруем пользователей по возрасту.
Скажем, нас будут интересовать пользователи старше 30 лет.
Для этого в GraphBLAS есть функция Select, которая фильтрует коллекции, используя функцию-предикат принимаемую в качестве аргумента.
Так как нам предстоит работать с пользовательскими типами, то придётся написать собственный предикат.
void check_user_age(bool *z, const User *x, GrB_Index _i, GrB_Index _j, const uint8_t *y)
{
*z = (x->age > *y);
}Два дополнительных параметра типа GrB_Index позволяют, при необходимости, использовать в фильтре координаты рассматриваемого элемента.
Для того, чтобы выбрать карты, принадлежащие выбранным пользователям, нам необходимо получить "концы" рёбер типа Owns, исходящие из выбранных пользователей. Чтобы сделать это, выполним один шаг обхода в ширину, который в терминах линейной алгебры выражается через умножение вектора текущих вершин на матрицу смежности. Текущие вершины в нашем случае --- выбранные пользователи. То есть нам необходимо вычислить следующее произведение.
Здесь нам впервые потребуется переопределить поэлементные операции для
В качестве конкретных реализаций для
Мы получили не совсем карты, но вектор, который указывает, какие карты нас интересуют.
Вспомним, что мы хотим взять только карты "МИР".
Для этого снова будем использовать Select, а полученный вектор
Чтобы получить переводы только между отобранными картами, воспользуемся тем фактом, что выбор исходящих рёбер, инцидентных заданному множеству вершин --- это умножение матрицы смежности на диагональную матрицу, в которой ненулевые элементы на местах интересующих нас вершин, слева. Для входящих рёбер нужно аналогичное умножение справа. То есть нам необходимо вычислить следующее произведение.
То есть данном случае нам необходимо умножить на диагональную матрицу и слева, и справа (нам важно, чтобы все рёбра шли только между отобранными картами).
Здесь операции
В качестве конкретных реализаций для
Для
Подграф готов.
Теперь необходимо сконструировать матрицу, по которой непосредственно будем считать PageRank.
Сейчас метки рёбер --- структуры, хранящие информацию о переводах, а мы хотим получить одно число.
При этом важно, чтобы сумма весов всех исходящих рёбер была равна единице.
Для примера действовать будем следующим образом: возьмём "средний размер транзакции" (вычислим как
В нашем случае подобная функция должна быть применена к каждой строке матрицы, задающей переводы. При этом должна быть определена функция
Вычисления построим следующим образом. Сперва выполним редукцию по колонкам с использованием функции
Далее на полученной матрице запускаем классический алгоритм PageRank (правда, без "телепортации" в несвязанные вершины), который в терминах линейной алгебры реализуется по определению: итеративное умножение исходной матрицы на вектор.