viagra super force

+7(495) 123-XXXX  г. Москва

Выпуски журналов

  • Серия
  • Серия
  • Серия
  • Серия
  • Журнал
  • Журнал
  • Журнал
  • Журнал

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

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

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

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

 

ВВЕДЕНИЕ

Работа [1] – одна из первых по графодинамике, т.е. по динамическому описанию структур с использованием орграфов. В темпоральных орграфах (Т-орграфах) структура изменяется во времени, и задача состоит в изучении динамики этой структуры. Совокупность методов описания и изучения таких систем была названа «графодинамикой» [1].
В ней в качестве наиболее важных выделялись:
    1) задача определения расстояния, дающего представления о стабильности изменений структуры по отношению к малым возмущениям и о монотонности в смысле этого расстояния процессов;
    2) задача определения в орграфе фрагмента, который не меняется или «мало» меняется во времени. В связи с расширением сфер практической применимости и в особенности при разработке новых поколений систем искусственного интеллекта, при анализе темпоральных сетей (компьютерных, социальных, коммуникационных и др.) c 2006  года актуализировались исследования по графодинамике [2-7]. В [3, 4] выделены в качестве актуальных прикладных задач следующие: 1) задача анализа изменений во времени структур корпоративных социальных сетей (КCC), в особенности, сетей коммуникаций сотрудников фирмы; 2) задача установления направления изменения структуры сети с целью повышения обоснованности управленческих решений и др. Как выделено в [3], управление КСС и их структурой – новая область менеджмента. Однако область исследования T-орграфов и T-сетей недостаточно раскрыта в современной литературе. В [6]  предложены два метода, позволяющие на основе моделей сложности исследовать изменения локальных и глобальных свойств T-орграфов, определять сходство T-орграфов на основе моделей сложности и выявлять тенденции изменения их свойств. В [7] с целью выявления монотонности процесса изменения сходства структур T-орграфов выделены два класса задач анализа сходства: 1) сходство структур одного T-орграфа; 2) сходство структур двух T-орграфов. Описаны два подхода к решению задач: подход на основе использования инвариантов T-орграфов, подструктурный (П-подход), и проведен их сравнительный анализ. В данной работе с целью всестороннего исследования сходства T-орграфов выделены два класса задач анализа сходства, включающие 28 видов задач, и методология их решения, объединяющая и обобщающая ранее известные подходы на основе использования системы надграфов структур T-орграфов и их инвариантов.
Предложенная методология позволяет получать более точные результаты определения сходства на основе характеризации T-орграфа системой надграфов, в которых дополнительно учитывается точное расположение фрагментов. С целью более эффективного вычисления мер сходства T-орграфов методология включает метод последовательно уточняющей характеризации T-орграфа и его надграфов с использованием оригинальных инвариантов, характеризующих достаточно точно как сам T-орграф, так и его надграфы. Для выявления монотонности изменения структур T-орграфов предлагаются оригинальные характеристики определения расстояния (индексов сходства) между парой T-орграфов или между структурами одного T-орграфа и его надграфов.

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


СПИСОК ЛИТЕРАТУРЫ:
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 с.
 



© 
В.В. Кохов, Журнал "Современная наука: актуальные проблемы теории и практики".
 

 

 

 
SCROLL TO TOP

 Rambler's Top100 @Mail.ru