Research of the distribution of distances between graphs with ordered vertices

Capa

Citar

Texto integral

Resumo

The article develops an approach based on a probabilistic model of generating objects with a distance between them. The distribution of distances between graphs with ordered vertices based on the maximum common is considered. One of the possible applications of such distances is the task of stylistic diagnostics of texts. Two algorithms for calculating distances on a set of graphs are presented. One of them consists of generating and exhaustively enumerating all pairs of trees, the second is heuristic. This is an approximate method of collecting statistics, where a given number of pairs of pseudo-random trees are iterated, since a complete search can take a long time. Using these algorithms, distance matrices between trees with a small and large number of vertices n were found. The experimental results showed that for small n the metric value does not exceed 0,5. For large n the average value of the metric grows slightly and stabilizes at the point 0,587. The hypothesis that the distribution corresponds to the normal law for n=100 was rejected using the Pearson test at a significance level of 0,1.

Sobre autores

Aleksandr Rogov

Petrozavodsk State University

Email: rogov@petrsu.ru

Head of Department, Doctor of Technical Sciences, Professor. Research interests: mathematical modeling, applied statistics, mathematical methods of pattern recognition, mathematical methods of analysis of literary texts.

Rússia, Petrozavodsk

Nikolai Moskin

Petrozavodsk State University

Autor responsável pela correspondência
Email: moskin@petrsu.ru

Professor, Doctor of Technical Sciences, Associate Professor. Research interests: digital humanities, graph-theoretical models, data mining, computational linguistics, multimedia technologies, computer graphics.

Rússia, Petrozavodsk

Roman Voronov

Petrozavodsk State University

Email: rvoronov@petrsu.ru

Professor, Doctor of Technical Sciences, Associate Professor. Research interests: mathematical modeling, optimization problems, combinatorial graph problems, mathematical methods and models of local positioning systems for mobile objects.

Rússia, Petrozavodsk

Kirill Kulakov

Petrozavodsk State University

Email: kulakov@cs.karelia.ru

Associate Professor, PhD in Physics and Mathematics, Associate Professor. Research interests: intelligent spaces, network technologies, mobile applications, electronic tourism, monitoring of industrial equipment, robotics, natural language analysis.

Rússia, Petrozavodsk

Bibliografia

  1. Moskin N.D. Teoretiko-grafovye modeli, metody i programmnye sredstva intellektual’nogo analiza tekstovoj informacii na primere fol’klornyh i literaturnyh proizvedenij [Graph-theoretical models, methods and software for the intellectual analysis of textual information on the example of folklore and literary works]. D.Sc. Diss. Petrozavodsk. 2022. 370 p. (In Russ.)
  2. Varfolomeev A.G., Kirikov P.V., Rogov A.A. Veroyatnostnyj podhod k sravneniyu rasstoyanij mezhdu podmnozhestvami konechnogo mnozhestva [A probabilistic approach to comparing distances between subsets of a finite set]. Uchenye zapiski Petrozavodskogo gosudarstvennogo universiteta [Scientific notes of Petrozavodsk State University]. 2010. 8(113). Р. 83-88. (In Russ.)
  3. Sidorov Y.V., Kirikov P.V., Rogov A.A. Sravnenie dendrogramm s ravnym chislom vershin [Comparison of dendrograms with an equal number of vertices]. Uchenye zapiski Petrozavodskogo gosudarstvennogo universiteta [Scientific notes of Petrozavodsk State University]. 2011. 8(121). Р. 108-110. (In Russ.)
  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. 14(1): 14-19. doi: 10.21638/11701/spbu10.2018.102.
  5. Gladkij A.V. Sintaksicheskie struktury estestvennogo yazyka [Syntactic structures of natural language]. Moscow, LKI Publ. 2007. 152 p. (In Russ.)
  6. Sevbo I.P. Graficheskoe predstavlenie sintaksicheskih struktur i stilisticheskaya diagnostika [Graphic representation of syntactic structures and stylistic diagnostics]. Kiev: Naukova Dumka. 1981. 192 p. (In Russ.)
  7. Moskin N.D. Metrika dlya sravneniya grafov s uporyadochennymi vershinami na osnove maksimal’nogo obshchego podgrafa [Metric for comparing graphs with ordered vertices based on maximum common subgraph]. Prikladnaya diskretnaya matematika [Applied discrete mathematics]. 2021. 52. Р. 105-113. doi: 10.17223/20710410/52/7. (In Russ.)
  8. Prüfer H. Neuer Beweis eines Satzes über Permutationen (нем.) // Archiv für Mathematik und Physik. 1918. 27: 742–744.
  9. Bron C., Kerbosh J. Algorithm 457 – Finding all cliques of an undirected graph // Communications of the ACM. 1973. 16. Р. 575–577.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

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

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») на элемент с текстом «Принять и продолжить».