Попытка сопоставить узлы между похожими графами

Я ищу алгоритм для сопоставления узлов в подобных графиках. Количество узлов не равно, но каждый граф представляет одну и ту же систему.

Итак, я ищу похожее или нечеткое сопоставление графов или распознавание образов.

С чего начать?

Неориентированный мультиграф с пометкой вершин Взвешенные разреженные узлы: 2172 Ребра: 3000

Узлы имеют ряд независимых атрибутов. Ребра имеют один атрибут, похожий на длину. Атрибуты узла и ребра не идентичны для соответствующих узлов и ребер между двумя графами.

Эта проблема описывается в технических статьях как частичный изоморфизм, выравнивание графов и максимальный общий подграф.


algorithm pattern-recognition graph-algorithm subgraph isomorphism
person David Francis    schedule 20.02.2014    source источник
comment
Кто-нибудь пробовал использовать cs.purdue.edu/homes/dgleich/codes/netalign< /а> ?   -  person David Francis    schedule 20.02.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вот базовый алгоритм частичного изоморфизма между двумя графами A и B..

Алгоритм

Given:
- graph A
- graph B
- threshold on A, p in [0.0,1.0)
- threshold on B, q in [0.0,1.0)

1. define: list T = { Nodes in graph B }

2. define: c = 0

3. for every Node i in graph A
   {
       for every Node j in list T
       {
           if(i and j are equivlant)
           {
               c = c + 1

               remove j from list T
           }
       }
   }

4. calculate: x = number of nodes in graph A / c

5. calculate: y = number of nodes in graph B / c

6. return (x > p AND y > q)

Пример

Правило: Узел i и Узел j эквивалентны, если они имеют одинаковую степень.

Константа: пороговое значение для A, p = 0,95 ~ 95 %.

Константа: пороговое значение B, q = 0,75 ~ 75 %.

Выходные данные. Алгоритм вернет TRUE для любого графа B, в котором набор узлов, составляющих 75 % или более, эквивалентен набору узлов, составляющих 95 % или более графа A.

person Khaled.K    schedule 26.03.2014