Алгоритм нахождения наибольшего общего подграфа
Предлагается новый переборный алгоритм решения задачи нахождения наибольшего общего подграфа. Приведены результаты численного анализа производительности алгоритма на графах различных классов и размеров, входящих в состав базы графов для оценки производительности алгоритмов решения задач установления...
Saved in:
| Date: | 2009 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/12410 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Алгоритм нахождения наибольшего общего подграфа / М.Б. Ильяшенко // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 112-120. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859838035050364928 |
|---|---|
| author | Ильяшенко, М.Б. |
| author_facet | Ильяшенко, М.Б. |
| citation_txt | Алгоритм нахождения наибольшего общего подграфа / М.Б. Ильяшенко // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 112-120. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| description | Предлагается новый переборный алгоритм решения задачи нахождения наибольшего общего подграфа. Приведены результаты численного анализа производительности алгоритма на графах различных классов и размеров, входящих в состав базы графов для оценки производительности алгоритмов решения задач установления морфизма на графах. Дана оценка потенциала применения разработанного алгоритма для решения реальных прикладных задач на графах размером порядка сотен вершин.
Запропоновано новий переборний алгоритм вирішення задачі знаходження найбільшого загального підграфа. Наведено результати чисельного аналізу продуктивності алгоритму на графах різних класів та розмірів, що складають базу графів для оцінки продуктивності алгоритмів вирішення задач встановлення морфізму на графах. Надана оцінка потенціалу застосування розробленого алгоритму для вирішення реальних задач на графах розміром до декількох сотень вершин.
A new enumerating algorithm for the solution of the problem of finding a maximal common subgraph is proposed. The results are presented for the numerical analysis of the algorithm efficiency on graphs of different classes and sizes, which compose the graph database for estimation of the efficiency of algorithms for solving problems concerning morphism on graphs. The potential of using the algorithm in solving real-world problems on graphs sizing up to several hundreds of vertices is estimated.
|
| first_indexed | 2025-12-07T15:36:01Z |
| format | Article |
| fulltext |
© М.Б. Ильяшенко, 2009
112 ISSN 1681–6048 System Research & Information Technologies, 2009, № 2
УДК 004.021
АЛГОРИТМ НАХОЖДЕНИЯ НАИБОЛЬШЕГО ОБЩЕГО
ПОДГРАФА
М.Б. ИЛЬЯШЕНКО
Предлагается новый переборный алгоритм решения задачи нахождения наи-
большего общего подграфа. Приведены результаты численного анализа произ-
водительности алгоритма на графах различных классов и размеров, входящих
в состав базы графов для оценки производительности алгоритмов решения за-
дач установления морфизма на графах. Дана оценка потенциала применения
разработанного алгоритма для решения реальных прикладных задач на графах
размером порядка сотен вершин
Графы широко применяются в различных областях науки и техники: в сис-
темах распознавания образов, химии, компьютерных системах и сетях, ло-
гистике и т.д. Если графы применяются для представления структурных
объектов, то степень сходства объектов становится равнозначна определе-
нию сходства графов, их представляющих. Изоморфизм графов использует-
ся для определения идентичности структур двух графов [1]. Более общая
операция граф–подграф изоморфизма используется для определения, явля-
ется ли один граф структурной частью другого [1,2]. В работах [3,4] рас-
смотрены вопросы применения понятия наибольшего общего подграфа для
определения степени схожести графов.
Нахождение наибольшего общего подграфа (НОП) двух заданных гра-
фов — задача известная. В работах [5, 6] алгоритм нахождения НОП приме-
нялся для сравнения молекул. В работе [7] предложен алгоритм нахождения
НОП, использующий метод поиска с возвратом. Другим, кардинально от-
личным подходом к нахождению НОП, является поиск максимальной клики
в модульном произведении графов [8, 9].
Проблемы нахождения НОП и максимальной клики являются NP-
полными задачами [10]. Поэтому было предложено множество эвристиче-
ских алгоритмов решения. Обзор таких алгоритмов, в том числе анализ их
вычислительной сложности и потенциальных возможностей применения,
сделан в работе [11]. Например, в [12] приводятся результаты численного
исследования двух алгоритмов нахождения НОП на основе базы случайных
графов. В частности, произведено сравнение производительности перебор-
ного алгоритма и алгоритма на основе нахождения максимальной клики в
модульном произведении графов, показавшее, что при низкой плотности
реберного заполнения графов более эффективным является подход, осно-
ванный на переборном алгоритме.
В данной статье приводится описание алгоритма нахождения НОП,
построенного на основе метода ветвей и границ. Приводится детальное
описание алгоритма, а также результаты исследования его
производительности на графах эталонной базы для сравнения алгоритмов
установления изоморфности.
Алгоритм нахождения наибольшего общего подграфа
Системні дослідження та інформаційні технології, 2009, № 2 113
АЛГОРИТМ
Максимальный общий подграф. Пусть даны графы ( )111 , EVG = и =2G
( )22 , EV= . Графы 11 GG ⊆′ и 22 GG ⊆′ . При этом подграф 1G′ изоморфен под-
графу 2G′ . 1G′ и 2G′ содержат максимальное число вершин среди всех воз-
можных подграфов.
Алгоритм поиска НОП удобно описывать в терминах поиска в про-
странстве состояний. Каждое состояние s процесса совмещения вершин
соответствует частичной подстановке ( )sϕ , которая содержит лишь часть
вершин полной подстановки. Каждому состоянию соответствуют подграфы
( )sG1 и ( )sG2 , полученные из вершин графов 1G и 2G , вошедших в час-
тичную подстановку ( )sϕ , и ребер, соединяющих эти вершины. В дальней-
шем обозначим ( )s1ϕ и ( )s2ϕ проекции подстановки ( )sϕ на 1V и 2V .
Алгоритм состоит из предварительной и основной частей.
В предварительной части алгоритма вершины графа 2G сортируются в
порядке убывания степени связности вершин. Первой ставится вершина с
наибольшим числом инцидентных ребер. Среди оставшихся вершин каждый
раз выбирается та, которая имеет максимальное число ребер, соединяющих
ее с уже совмещенными вершинами. Таким образом, вначале идут вершины,
имеющие большее число внутренних связей. Этот порядок следования вер-
шин делает более жесткими граничные условия, используемые в перебор-
ной части алгоритма и, в конечном счете, сужает область поиска.
Центральной является переборная часть алгоритма, основанная на ре-
курсивной функции последовательного наложения вершин с возвратом.
Вершины графа 2G остаются нетронутыми, и им в соответствие ставятся
вершины графа 1G .
В алгоритме используются следующие векторы индексов вершин гра-
фов, инцидентных совмещенным вершинам:
1In — входящие графа 1G ; 1Out — исходящие 1G ; 2In — входящие
2G ; 2Out — исходящие 2G .
Пусть на данном шаге в подстановку предполагается включить верши-
ны iV1 и iV2 . Коэффициент, используемый при изменении индексов входя-
щих и исходящих вершин, определяется как )31,1mod(2=k . Тогда
для ( ) 111 , EVV ij ∈∀ , ( ) 111 , EVV ji ∈∀ , ( ) 222 , EVV ij ∈∀ , ( ) 222 , EVV ji ∈∀ изме-
няем значения соответственно kInIn jj += 11 , kOutOut jj += 11 , =jIn2
kIn j += 2 , kOutOut jj += 22 .
Такое изменение индексов позволяет хранить в векторах 1In , 2In , 1Out
и 2Out не только количество связей каждой вершины с вершинами, уже
вошедшими в подстановку, но и косвенно, через индекс k — номер итера-
ции, на которой данная вершина была добавлена. Использование k в преде-
лах от 20 до 231 обусловлено применяемым в языке программирования С++
М.Б. Ильяшенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 114
32-разрядным типом данных. С введением 64-разрядных типов данных, под-
держиваемых на аппаратном уровне, разброс значений коэффициента k
можно будет увеличить.
На каждом шаге переборной части алгоритма среди вершин графа 1G ,
еще не вошедших в частичную подстановку ( )sϕ , выбирается вершина iV1 ,
потенциально совместимая с очередной вершиной jV2 графа 2G . Перед со-
вмещением проверяются условия допустимости добавления пары вершин
( )ji VV 21 , в частичную подстановку.
• ji InIn 21 = .
• ji OutOut 21 = .
• Множества ребер ( )( )sVE i
111 ,ϕ=′ и ( )( )sVE j
222 ,ϕ=′ должны совпа-
дать, т.е. 21 EE ′=′ .
Последнее условие является прямым следствием постановки задачи
поиска НОП. Если очередная полученная подстановка ( )sϕ больше, чем те-
кущая максимальная частичная подстановка ( )sϕ′ , то ( ) ( )ss ϕϕ =′ .
Если на очередном шаге не удается найти совместимых вершин, то вы-
полняется операция отката (backtracking), восстанавливаются значения век-
торов 1In , 2In , 1Out и 2Out предыдущего шага, и поиск продолжается, на-
чиная со следующей пары еще не совмещенных вершин.
БАЗА ГРАФОВ ДЛЯ ОЦЕНКИ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМОВ
НАХОЖДЕНИЯ НОП
Для сравнения производительности алгоритмов проверки на изоморфность,
установления граф–подграф изоморфизма и нахождения НОП предложена
эталонная база графов [13] (см. таблицу).
Наборы для различных размеров подграфов (10, 30, 50, 70 и 90% от
большего) одинаковы. Всего протестировано 50000 пар графов.
Типы графов, вошедшие в состав эталонной базы, учитывают особен-
ности реальных задач, которые решаются с применением алгоритма нахож-
дения НОП. Так для задач распознавания образов, распределения нагрузки в
компьютерных сетях, синтеза печатных плат и анализа топологии более
характерны графы с небольшой степенью вершин, низкой плотностью ре-
берного заполнения. Такие графы представлены в виде наборов графов с
ограниченной степенью вершин и нерегулярных сетей. Регулярные (сильно-
регулярные) графы, как правило, являются наихудшим случаем для пере-
борных алгоритмов решения задач морфизма на графах и характеризуют
уровень производительности алгоритма в «наихудшем случае». Такие графы
представлены наборами регулярных графов с ограниченной степенью вер-
шин и регулярных сетей. Кроме того, представлены случайные графы для
оценки производительности алгоритма на графах, не обладающих специ-
альными свойствами.
Алгоритм нахождения наибольшего общего подграфа
Системні дослідження та інформаційні технології, 2009, № 2 115
Состав набора графов эталонной базы
Тип графов Количество
пар Параметры Размеры
(вершин)
1100 =n 0,005 20–100
1100 =n 0,01 20–100 Случайно сгенерированные
графы
1100 =n 0,02 20–100
700 2D сеть 40–100 Регулярные сети
500 3D сеть 60–100
800 Нерегулярные 2D сети
ρ={0,2; 0,4; 0,6} 40–100
Нерегулярные сети
1500 Нерегулярные 3D сети
ρ={0,2; 0,4; 0,6} 60–100
700 Степень=3 40–100 Регулярные графы с
ограниченной степенью вершин 400 Степень=6 70–100
700 Степень=3, α=0,1 40–100 Нерегулярные графы с
ограниченной степенью вершин 400 Степень=6, α=0,1 70–100
Итого 10000
ИССЛЕДОВАНИЕ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМА НА ГРАФАХ
ЭТАЛОННОЙ БАЗЫ
Исследования производительности алгоритма осуществлялись на компью-
тере AMD Athlon 1700+, 512MB RAM. Компилятор Visual C++ 6.0.
Различные наборы графов обозначим следующим образом:
MCS0 — набор графов с размером подграфа 10%, MCS1 — 30%,
MCS2 —50%, MCS3 —70%, MCS4 —90%.
Характерные результаты исследования приведены на рис. 1–10. Для
удобства сравнения производительности различных алгоритмов приведены
как среднее время сравнения одной пары графов, так и среднее число пере-
бранных узлов дерева решений рекурсивного алгоритма. При сравнении пе-
реборных алгоритмов число перебранных узлов дерева решений выступает
более адекватным критерием сравнения, так как время вычислений может
сильно зависеть от особенностей программной реализации и производи-
тельности компьютера, на котором выполнялись исследования.
Результаты исследования показали, что для всех графов эталонной ба-
зы алгоритм находит решение за время, не превышающее 0,2 с, перебрав не
более 6000 узлов дерева решений. Такая производительность дает возмож-
ность использовать разработанный алгоритм нахождения НОП в реальных
прикладных задачах. Характерной особенностью алгоритма является повы-
шение производительности с ростом размера меньшего графа. Это связано с
появлением дополнительной информации в переборной части алгоритма за
счет увеличения числа ребер в графах, что обусловливает больший разброс
значений векторов 1In , 2In , 1Out , 2Out и как следствие — сужение области
поиска за счет усиления граничного условия переборной части алгоритма.
М.Б. Ильяшенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 116
Рис. 1. Время проверки регулярных графов с ограниченной степенью вершин
(N=40...100, степень=3)
Число вершин
Рис. 2. Число перебранных узлов при проверке регулярных графов с ограниченной
степенью вершин (N=40...100, степень=3)
Число вершин
Рис. 3. Время проверки нерегулярных графов с ограниченной степенью вершин
(N=40…100, степень=3, a=0,1)
Число вершин
Алгоритм нахождения наибольшего общего подграфа
Системні дослідження та інформаційні технології, 2009, № 2 117
Рис. 5. Время проверки регулярных 2D сетей (N=40…100, p=0,0)
Число вершин
Рис. 6. Число перебранных узлов при проверке регулярных 2D сетей (N=40…100,
p=0,0)
Число вершин
Рис. 4. Число перебранных узлов при проверке нерегулярных графов с ограничен-
ной степенью вершин (N=40…100, степень=3, a=0,1)
Число вершин
М.Б. Ильяшенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 118
Рис. 7. Время проверки регулярных 3D сетей (N=60…100, p=0,0)
Число вершин
Рис. 8. Число перебранных узлов при проверке регулярных 3D сетей (N=60…100,
p=0,0)
Число вершин
Рис. 9. Время проверки случайно сгенерированных графов (N=20…100, n=0,01)
Число вершин
Алгоритм нахождения наибольшего общего подграфа
Системні дослідження та інформаційні технології, 2009, № 2 119
ВЫВОДЫ
Представлен новый алгоритм нахождения наибольшего общего подграфа.
Приведены результаты численного анализа производительности алгоритма
на эталонной базе графов для оценки производительности алгоритмов мор-
физма на графах. Результаты исследования показали, что разработанный
алгоритм в состоянии сравнивать графы размерностью до 100 вершин за
время, не превышающее 0,2 с, при переборе не более 6000 узлов дерева ре-
шений. Графы большего размера в эталонной базе на данный момент отсут-
ствуют.
Производительность разработанного алгоритма позволяет применять
его для решения реальных прикладных задача на графах размерностью по-
рядка сотен вершин.
Дальнейшие усилия будут направлены на численное определение вы-
числительной сложности алгоритма путем исследования его производи-
тельности на графах большего размера, чем представленные в эталонной
базе, а также на более детальное сравнение с аналогами и расширение
функциональности для решения задач на взвешенных графах и связанными
с ними проблемами оптимизации.
ЛИТЕРАТУРА
1. Ullmann J.R. An Algorithm for Subgraph Isomorphism // Journal of the Association
for Computing Machinery. — 1976. — № 23. — P. 31–42.
2. An improved algorithm for matching large graphs / L.P. Cordella et al. // Proceed-
ings of the 3rd IAPR-TC-15 International Workshop on Graph-based Representa-
tions. — Italy, 2001. — P. 149–159.
3. On the Minimum Supergraph of Two Graphs / H. Bunke, X. Jiang, A. Kandel //
Computing. — 2000. — 65. —P. 13–25.
4. Bunke H., Sharer K. A Graph Distance Metric Based on the Maximal Common Sub-
graph // Pattern Recognition Letters. — 1998. — 19. — № 3, 4. — P. 255–259.
Рис. 10. Число перебранных узлов при проверке случайно сгенерированных графов
(N=20…100, n=0,01)
Число вершин
М.Б. Ильяшенко
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 120
5. Levi G. A Note on the Derivation of Maximal Common Subgraphs of Two Directed
or Undirected Graphs // Calcolo. — 1972. —9. — P. 341–354.
6. Molecular Structure Comparison Program for the Identification of Maximal Com-
mon Substructures / M. M. Cone, Rengachari Venkataraghven, F. W. McLafferty
// Journal of Am. Chem. Soc. — 1977. — 99, №23. — P. 7668–7671.
7. McGregor J.J. Backtrack Search Algorithms and the Maximal Common Subgraph
Problem // Software Practice and Experience. — 1982. — 12. — P. 23–34.
8. Bron C., Kerbosch J. Finding All the Cliques in an Undirected Graph // Com-
munication of the Association for Computing Machinery. — 1973. — 16. —
P. 575–577.
9. Immanuel M. Bomze. Evolution towards the Maximum Clique // Journal of Global
Optimization. — 1997. — 10, № 2. — P. 143–164.
10. Garey M.R., Johnson D.S. Computers and intractability: a guide to the theory of NP-
completeness. — S.F.: W.H. Freeman and Comp.,1979. — 251 p.
11. The Maximum Clique Problem / I.M. Bomze еt al. // Handbook of Combinatorial
Optimization. — Kluwer Academy Pub. — 1999. — 4. — P. 656.
12. A Comparison of Algorithms for Maximum Common Subgraph on Randomly Con-
nected Graphs / H. Bunke at al. // Structural, Syntactic, and Statistical Pattern
Recognition. — Springer Berlin: Heidelberg. — 2002. — P. 123–132.
13. A large database of graphs and its use for benchmarking graph isomorphism
algorithms / De Santo M. et al. // Pattern Recogn. — 2003 — 24, № 8. —
P. 1067–1079.
Поступила 17.04.2007
|
| id | nasplib_isofts_kiev_ua-123456789-12410 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-07T15:36:01Z |
| publishDate | 2009 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Ильяшенко, М.Б. 2010-10-07T19:57:49Z 2010-10-07T19:57:49Z 2009 Алгоритм нахождения наибольшего общего подграфа / М.Б. Ильяшенко // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 112-120. — Бібліогр.: 13 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/12410 004.021 Предлагается новый переборный алгоритм решения задачи нахождения наибольшего общего подграфа. Приведены результаты численного анализа производительности алгоритма на графах различных классов и размеров, входящих в состав базы графов для оценки производительности алгоритмов решения задач установления морфизма на графах. Дана оценка потенциала применения разработанного алгоритма для решения реальных прикладных задач на графах размером порядка сотен вершин. Запропоновано новий переборний алгоритм вирішення задачі знаходження найбільшого загального підграфа. Наведено результати чисельного аналізу продуктивності алгоритму на графах різних класів та розмірів, що складають базу графів для оцінки продуктивності алгоритмів вирішення задач встановлення морфізму на графах. Надана оцінка потенціалу застосування розробленого алгоритму для вирішення реальних задач на графах розміром до декількох сотень вершин. A new enumerating algorithm for the solution of the problem of finding a maximal common subgraph is proposed. The results are presented for the numerical analysis of the algorithm efficiency on graphs of different classes and sizes, which compose the graph database for estimation of the efficiency of algorithms for solving problems concerning morphism on graphs. The potential of using the algorithm in solving real-world problems on graphs sizing up to several hundreds of vertices is estimated. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Евристичні методи та алгоритми в системному аналізі та управлінні Алгоритм нахождения наибольшего общего подграфа Алгоритм знаходження найбільшого загального підграфа Algorithm for finding maximal common subgraph Article published earlier |
| spellingShingle | Алгоритм нахождения наибольшего общего подграфа Ильяшенко, М.Б. Евристичні методи та алгоритми в системному аналізі та управлінні |
| title | Алгоритм нахождения наибольшего общего подграфа |
| title_alt | Алгоритм знаходження найбільшого загального підграфа Algorithm for finding maximal common subgraph |
| title_full | Алгоритм нахождения наибольшего общего подграфа |
| title_fullStr | Алгоритм нахождения наибольшего общего подграфа |
| title_full_unstemmed | Алгоритм нахождения наибольшего общего подграфа |
| title_short | Алгоритм нахождения наибольшего общего подграфа |
| title_sort | алгоритм нахождения наибольшего общего подграфа |
| topic | Евристичні методи та алгоритми в системному аналізі та управлінні |
| topic_facet | Евристичні методи та алгоритми в системному аналізі та управлінні |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/12410 |
| work_keys_str_mv | AT ilʹâšenkomb algoritmnahoždeniânaibolʹšegoobŝegopodgrafa AT ilʹâšenkomb algoritmznahodžennânaibílʹšogozagalʹnogopídgrafa AT ilʹâšenkomb algorithmforfindingmaximalcommonsubgraph |