Исследование распределения расстояний между графами с упорядоченными вершинами

Обложка

Цитировать

Полный текст

Аннотация

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

Доцент. Кандидат физико-математических наук, доцент. Область научных интересов: интеллектуальные пространства, сетевые технологии, мобильные приложения, электронный туризм, мониторинг промышленного оборудования, робототехника, анализ естественных языков.

Россия, Петрозаводск

Список литературы

  1. Москин Н.Д. Теоретико-графовые модели, методы и программные средства интеллектуального анализа текстовой информации на примере фольклорных и литературных произведений. Дис. … докт. техн. наук. Петрозаводск. 2022. 370 с.
  2. Варфоломеев А.Г., Кириков П.В., Рогов А.А. Вероятностный подход к сравнению расстояний между подмножествами конечного множества // Ученые записки Петрозаводского государственного университета. 2010. №8(113). С. 83-88.
  3. Сидоров Ю.В., Кириков П.В., Рогов А.А. Сравнение дендрограмм с равным числом вершин // Ученые записки Петрозаводского государственного университета. Серия: Естественные и технические науки. 2011. № 8 (121). С. 108-110.
  4. 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.
  5. Гладкий А.В. Синтаксические структуры естественного языка. М.: ЛКИ. 2007. 152 с.
  6. Севбо И.П. Графическое представление синтаксических структур и стилистическая диагностика. Киев: Наукова Думка. 1981. 192 с.
  7. Москин Н.Д. Метрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа // Прикладная дискретная математика. 2021. № 52. С. 105-113. doi: 10.17223/20710410/52/7.
  8. Prüfer H. Neuer Beweis eines Satzes über Permutationen (нем.) // Archiv für Mathematik und Physik. 1918. Bd. 27. Р. 742–744.
  9. Bron C., Kerbosh J. Algorithm 457 – Finding all cliques of an undirected graph // Communications of the ACM. 1973. Vol. 16. Р. 575–577.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».