Исследование распределения расстояний между графами с упорядоченными вершинами
- Авторы: Рогов А.А.1, Москин Н.Д.1, Воронов Р.В.1, Кулаков К.А.1
-
Учреждения:
- Петрозаводский государственный университет
- Выпуск: Том 74, № 3 (2024)
- Страницы: 58-66
- Раздел: Информатика сообществ и формирование социальных сетей
- URL: https://journal-vniispk.ru/2079-0279/article/view/293509
- DOI: https://doi.org/10.14357/20790279240307
- EDN: https://elibrary.ru/NCISUO
- ID: 293509
Цитировать
Полный текст
Аннотация
B статье развивается подход, основанный на вероятностной модели генерации объектов, между которыми находится расстояние. Рассматривается распределение расстояний между графами с упорядоченными вершинами на основе максимального общего подграфа. Одним из возможных вариантов применения подобных расстояний является задача стилистической диагностики текстов. Представлено два алгоритма подсчета расстояния на множестве графов. Один из них заключается в генерации и полном переборе всех пар деревьев, второй – эвристический. Это приближенный метод сбора статистики, где перебирается заданное число пар псевдослучайных деревьев, так как полный перебор может занимать много времени. С помощью этих алгоритмов были найдены матрицы расстояний между деревьями с малым и большим числом вершин n. Результаты экспериментов показали, что при малых n значение метрики не превосходит 0,5. При больших n среднее значение метрики слабо растет и стабилизируется в точке 0,587. Гипотеза о соответствии распределения нормальному закону при n=100 была отвергнута с помощью критерия Пирсона на уровне значимости 0,1.
Ключевые слова
Об авторах
Александр Александрович Рогов
Петрозаводский государственный университет
Email: rogov@petrsu.ru
Заведующий кафедрой. Доктор технических наук, профессор. Область научных интересов: математическое моделирование, прикладная статистика, математические методы распознавания образов, математические методы анализа литературных текстов.
Россия, ПетрозаводскНиколай Дмитриевич Москин
Петрозаводский государственный университет
Автор, ответственный за переписку.
Email: moskin@petrsu.ru
Профессор. Доктор технических наук, доцент. Область научных интересов: цифровые гуманитарные науки, теоретико-графовые модели, интеллектуальный анализ данных, компьютерная лингвистика, мультимедиа-технологии, компьютерная графика.
Россия, ПетрозаводскРоман Владимирович Воронов
Петрозаводский государственный университет
Email: rvoronov@petrsu.ru
Профессор. Доктор технических наук, доцент. Область научных интересов: математическое моделирование, задачи оптимизации, комбинаторные задачи на графах, математические методы и модели систем локального позиционирования мобильных объектов.
Россия, ПетрозаводскКирилл Александрович Кулаков
Петрозаводский государственный университет
Email: kulakov@cs.karelia.ru
Доцент. Кандидат физико-математических наук, доцент. Область научных интересов: интеллектуальные пространства, сетевые технологии, мобильные приложения, электронный туризм, мониторинг промышленного оборудования, робототехника, анализ естественных языков.
Россия, ПетрозаводскСписок литературы
- Москин Н.Д. Теоретико-графовые модели, методы и программные средства интеллектуального анализа текстовой информации на примере фольклорных и литературных произведений. Дис. … докт. техн. наук. Петрозаводск. 2022. 370 с.
- Варфоломеев А.Г., Кириков П.В., Рогов А.А. Вероятностный подход к сравнению расстояний между подмножествами конечного множества // Ученые записки Петрозаводского государственного университета. 2010. №8(113). С. 83-88.
- Сидоров Ю.В., Кириков П.В., Рогов А.А. Сравнение дендрограмм с равным числом вершин // Ученые записки Петрозаводского государственного университета. Серия: Естественные и технические науки. 2011. № 8 (121). С. 108-110.
- Rogov A.A., Varfolomeyev A.G., Timonin A.O., Proenca K.A. A probabilistic approach to comparing the distances between partitions of a set // Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes. 2018. Vol. 14, № 1. P. 14-19. doi: 10.21638/11701/spbu10.2018.102.
- Гладкий А.В. Синтаксические структуры естественного языка. М.: ЛКИ. 2007. 152 с.
- Севбо И.П. Графическое представление синтаксических структур и стилистическая диагностика. Киев: Наукова Думка. 1981. 192 с.
- Москин Н.Д. Метрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа // Прикладная дискретная математика. 2021. № 52. С. 105-113. doi: 10.17223/20710410/52/7.
- Prüfer H. Neuer Beweis eines Satzes über Permutationen (нем.) // Archiv für Mathematik und Physik. 1918. Bd. 27. Р. 742–744.
- Bron C., Kerbosh J. Algorithm 457 – Finding all cliques of an undirected graph // Communications of the ACM. 1973. Vol. 16. Р. 575–577.
Дополнительные файлы
