 |
А. А. Рогов, Н. Д. Москин, Р. В. Воронов, К.А. Кулаков "Исследование распределения расстояний между графами с упорядоченными вершинами" |
 |
|
Аннотация.
В статье развивается подход, основанный на вероятностной модели генерации объектов, между которыми находится расстояние. Рассматривается распределение расстояний между графами с упорядоченными вершинами на основе максимального общего подграфа. Одним из возможных вариантов применения подобных расстояний является задача стилистической диагностики текстов. Представлено два алгоритмы подсчета расстояния на множестве графов. Один из них заключается в генерации и полном переборе всех пар деревьев, второй – эвристический. Это приближенный метод сбора статистики, где перебирается заданное число пар псевдослучайных деревьев, так как полный перебор может занимать много времени. С помощью этих алгоритмов были найдены матрицы расстояний между деревьями с малым и большим числом вершин n. Результаты экспериментов показали, что при малых n значение метрики не превосходит 0,5. При больших n среднее значение метрики слабо растет и стабилизируется в точке 0,587. Гипотеза о соответствии распределения нормальному закону при n=100 была отвергнута с помощью критерия Пирсона на уровне значимости 0,1.
Ключевые слова:
граф, сравнение, метрика, максимальный общий подграф, упорядочение вершин.
DOI: 10.14357/20790279240307
EDN: NCISUO Стр. 58-66.
Литература
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. S. 742–744. 9. Bron C., Kerbosh J. Algorithm 457 – Finding all cliques of an undirected graph // Communications of the ACM. 1973. Vol. 16. pp. 575–577.
|
