Алгоритм QuickSI для поиска изоморфизмов подграфов

Я изучаю алгоритм быстрого изоморфизма подграфов (QuickSI), и у меня возникла проблема с пониманием формул, касающихся расчета внутренней поддержки и средней внутренней поддержки, описанных на странице 6, (2) и (3). Если «v» означает вершину, а «e» — ребро, то что делают f(v) и f(e)? Как я могу получить значения таблицы 2 со страницы 6? Определение 4 со страницы 5 на самом деле не очень помогает мне понять. Под изоморфными отображениями из графа запросов в граф данных я понимаю взятие различных компонентов из графа запросов и просмотр, можно ли их найти в графе данных. Но время вычислений для этого кажется не слишком подходящим для больших графов.

Здесь вы можете найти оригинал статьи: http://www.cse.unsw.edu.au/~lxue/10papers/vldb08_haichuan.pdf

Заранее спасибо!


python graph algorithm subgraph isomorphism
person graiul    schedule 14.08.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Функция f описана в определении 1 — это просто функция изоморфизма, которая сохранила метки (l).

«Средняя внутренняя поддержка» — это количество «функций» (например, вершин), имеющих изоморфизм, деленное на количество графов, имеющих изоморфизм. Чтобы получить значения таблицы, вам нужно знать набор данных графиков (D), который использовался. Кажется, на него не ссылаются, кроме как в примере 4.

Действительно, делая шаг назад - нужно ли реализовывать именно этот алгоритм? Есть много более простых, которые могут быть немного медленнее, но четче. Более того, почему бы не использовать чужую реализацию алгоритма изоморфизма подграфов?

person gilleain    schedule 14.08.2017
comment
Спасибо за ваш быстрый ответ. Да, я должен реализовать это. Набор данных графиков (D) расположен на странице 1, рисунок 2. Я пытался использовать две формулы, но не смог получить ответы из таблицы 2. Если возможно, не могли бы вы помочь мне с пошаговым примером используя формулы с наборами данных? Я не смог получить ни 1,4, ни 5,1 ни для кромки типа N-C, ни для кромки типа C-C. Благодарю вас! - person graiul; 14.08.2017
comment
Хм. Странно, я тоже пытался вычислить, и значения не совпадают. Например, phi-avg(N) должно быть 4/3, верно? В D есть 4 вершины, помеченные как «N», и есть 3 графа, которые содержат f (v), то есть 3, которые имеют (хотя бы одно?) отображение. Может быть, таблица на самом деле не соответствует D, который они дают? Всегда можно спросить у авторов... - person gilleain; 15.08.2017
comment
Я работал над частью с краями. У нас есть 4 отображения для ребра NC по трем графам данных. Я пробовал следующее: 1) 4/3, четыре отображения на 3 графика. Не сработало. 2) 4/20, где 20 — общее количество ребер в трех графах. Нет успеха. 3) 4/16. 16 ребер, потому что я вычел 4 появления NC из 20 ребер. Последним средством, которое я попытаюсь сделать, будет подсчет общего количества объектов, которые содержат это ребро и могут быть сопоставлены. Если это не удастся, я, наконец, свяжусь с авторами. - person graiul; 16.08.2017