VIP Studio - журнал «Современная наука» - Задачи и методы определения сходства темпоральных орграфов

Задачи и методы определения сходства темпоральных орграфов

В.В. Кохов, (Аспирант, Национальный исследовательский университет  Московский Энергетический институт, НИУ-МЭИ)

Серия «Естественные и Технические науки» # 2 2016

В работе предложены 28 видов задач определения сходства T-орграфов. Предложена методология решения задач, включающая три подхода на основе:
1. надграфов;
2. наибольших общих фрагментов;
3. инвариантов надграфов.
Описан метод построения системы надграфов, учитывающих расположения полупутей. Приведены примеры решения задач.

Ключевые слова: Темпоральный орграф. Инвариант. Надграф. Задачи определения сходства.

Читать полный текст статьи …

СПИСОК ЛИТЕРАТУРЫ:
1. Айзерман М.А., Гусев Л.А., Петров С.В., Смирнова И.Н. Динамичес-кий подход к анализу структур, описываемых графами (основы графодинамики) // АиТ. 1977. №7.  С. 136-151.
2. Bramsen P.J. Doing Time: Inducing Temporal Graphs. Technical report, Massachusetts Institute of Technologi. 2006. 51 p.
3. Jackson M.O. Social and Economic Networks. Princeton University Press, 2008. 647 p.
4. Haixun Wang, Charu C. Aggarwal. Managing and Mining Graph Data. Springer, 2010.
5. Kuhn F., Oshman R. Dynamic Networks: Models and Algorithms // ACM SIGACT News. 2011. № 42. – P. 82-96.
6. Кохов В.А., Кохов В.В. Методы анализа изменений глобальных и локальных свойств темпоральных орграфов. Бизнес-информатика. 2012. №03. – С. 42-51.
7. Кохов В.В. Задачи и методы анализа сходства темпоральных орграфов. Труды 14-ой национальной конференции по искусственному интеллекту с международным участием. КИИ-2014. Том 3. Казань: Изд-во РИЦ “Школа”. 2014. – С. 155-163.
8. Bunke H., Sharer K. A Graph Distance Metric Based on the Maximum Common Subgraph // Pattern Recognition Letters. Vol. 19.  1998. – No. 3-4. P. 255-259.
9. Кохов В.А., Кохов В.В. Система моделей для анализа сходства орграфов с учетом расположения полупутей. Труды 13-ой конференции по искусственному интеллекту с международным участием. КИИ-2012. В 3-х т. Том 3. М.: Физматлит, 2012. – С. 9-16.
10. Кохов В.А. Два подхода к определению сходства орграфов // Известия РАН. Теория и системы управления, 2012, №3, с. 76-95.
11. Нечепуренко М.И., Попков В.К., Кохов В.А. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука, 1990. 515 с.
12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. — М.: Мир, 1982, – 416 с.