Сходство Каца - Матрица / График Операции (JAVA + JUNG)

Question

Я тестирую некоторые метрики сходства на графике. Я использую JUNG API для обработки графиков. Мне удалось вычислить основные метрики, такие как общие соседи и предпочтительные вложения. Теперь я хочу вычислить метрику Каца следующим образом: katz (v1, v2) = B.paths_1 (v1, v2) + B ^ 2.paths_2 (v1, v2) + ... + B ^ n.paths_n (v1, v2) где paths_n (v1, v2) - это количество путей длины "n" между v1 и v2; и B скаляр. Я ограничиваю n до 4, поэтому итоговую матрицу Каца можно легко вычислить с помощью: B.A + (B.A) ^ 2 + ... + (B.A) ^ 4 где A - матрица смежности графа. Дело в том, что графики, с которыми я работаю, очень большие, и я не могу сохранить всю матрицу Каца в памяти. Кроме того, мне не понадобятся все результаты, потому что я тестирую только несколько пар узлов. Однако я не могу найти эффективный способ подсчета индивидуальных баллов без необходимости проходить по графику. Есть идеи?

Answer 1

Чтобы вычислить индивидуальный балл ketz(v1,v2), вам просто нужно рассмотреть подматрицу смежности, которая содержит только вершины, которые находятся на расстоянии менее 4 от v1 или v2.

Вы можете найтиэти вершины используют поиск по дыханию из v1 и из v2.

Но на самом деле вы можете добиться гораздо большего, если будете непосредственно считать #paths при выполнении BFS, начиная с v1.Вам нужно только запомнить расстояние от v1 и в каждой вершине проверить, достигли ли вы v2.Если это так, увеличьте значение соответствующего счетчика.

Что-то вроде этого (псевдокод):

Queue q = new Queue();
q.enqueue((v1, 0));
int[] counts = new int[] { 0,0,0,0,0 };

while (!q.empty()) {
    (v, dist) = q.dequeue();
    for(Vertex w : v.Neighbors()) {
        if(dist < 3)
            q.enqueue((w, dist+1));

        if(dist < 4 && w == v2)
            counts[dist+1]++;
    }
}

Так что после запуска вы получите counts[n] = paths_n(v1,v2) для n = 1,2,3,4