ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ВЫЯВЛЕНИЯ СЕТЕВЫХ МОТИВОВ (2023)
В статье описан алгоритм Кавош (Kavosh) для поиска сетевых мотивов (или статистически важных подграфов). Приведены зависимости скорости работы, полученные в результате апробации данного алгоритма на языке программирования Python. Разработанный прототип веб-приложения Motif App применим как для анализа ориентированных, так и неориентированных графов.
Идентификаторы и классификаторы
Данная формула реализована при помощи списков и словаря на Python 3. Ключом словаря представлена главная вершина, а каждое соединение с ней – листом из 4-х и более последовательных элементов, содержащих остальные ранее описанные параметры. При необходимости представленная структура данных свободно дополняема и удобна в переборе, т.к. не использует лишние данные на подобии номера вершины и сама вершина связана с ребрами в единую структуру. Это позволяет сильно сократить время на сопоставление вершин и связей между ними. Однако данная структура требует определенных вычислительных мощностей и выделенной памяти для временного хранения данных графа. В начале работы реализации Motif App алгоритма Kavosh перезаписывается вся структура данных в описанный ранее формат и проводится анализ на поиск самых слабосвязанных вершин. Каждый поиск нового подграфа начинается именно с таких вершин. Далее просматривается ребро следующей случайной вершины. Все данные по пройденным на верхних уровнях графа вершинам запоминаются во временную память. При попадании на вершину проверяется индекс i, который может принимать значение равное 0 или 1. Данный индекс отвечает за исключение не подходящих вершин графа и избежание перерасчета (вершины с индексом 0 не учитываются). При нахождении подграфа с необходимым количеством вершин все индексы возвращаются к исходному значению 1, а вершина, с которой начинался расчет удаляется из графа. Следует отметить это помогает избежать избыточного перерасчета вершин графа. Алгоритм поиска подграфов изображен на рисунке 2.
Список литературы
-
Paredes P., Ribeiro P. FaSE - Fast Subgraph Enumeration. URL: https://github.com/ComplexNetworks-DCC-FCUP/fase (дата обращения: 10.03.2022).
-
Milo R., Shen-Orr S., Itzkovitz S. [et al.].Network motifs: Simple building blocks of complex networks // Science. 2002. Vol. 298, no. 5594. P. 824-827. EDN: EJDGFF
-
Wernicke S., Rasche F. FANMOD: a tool for fast network motif detection // Bioinformatics. 2006. Vol. 22, no. 9. P. 1152-1153. EDN: ILFDXT
-
Bhuiyan M. A., Rahman M., Hasan M. Al. Guise: Uniform sampling of graphlets for large graph analysis // Proceedings of the 12th International Conference on Data Mining (ICDM). Brussels, 2012. P. 91-100.
-
Rahman, M., Bhuiyan M. A., Hasan M. Al. Graft: An efficient graphlet counting method for large graph analysis // IEEE Transactions on Knowledge and Data Engineering. 2014. Vol. 26, no. 10. P. 2466-2478.
-
Wang P., Zhao J., Zhang Х. [et al.] MOSS-5: A fast method of approximating counts of 5-node graphlets in large graphs // IEEE Transactions on Knowledge and Data Engineering. 2018. Vol. 30, no. 1. P. 73-86.
-
Юдина М. Н. Program to detect network motifs. URL: https://github.com/MNYudina/MFSView (дата обращения: 20.05.2022).
-
Юдина М. Н. Методы и алгоритмы ускоренного расчета частот встречаемости сетевых мотивов в больших случайных графах: специальность 05.13.18: дис. канд. техн. наук. Омск: Изд-во ОмГТУ, 2020. 145 с.
-
Smoly I. Y., Lerman E., Ziv-Ukelson M. [et al.] MotifNet: A web-server for network motif analysis // Bioinformatics. 2017. Vol. 33, no. 12. P. 1907-1909.
-
Kashani Z. R., Ahrabian H., Elahi E. [et al.] Kavosh: a new algorithm for finding network motifs // Bioinformatics. 2009. Vol. 10. P. 318.
Выпуск
Другие статьи выпуска
Исследуются существующие модели теории массового обслуживания. Произведены расчеты оценки эффективности потока данных для обеспечения пропускной способности между компьютерами и сервером. Проведено тестирование и сравнительный анализ потока данных. Определены дальнейшие перспективы исследования вариантов для оценки эффективности потока данных.
С учетом возрастания размера видео и его качества, возросла необходимость повышения качества сжатия видео, что привело к возникновению новых способов сжатия видео. Также одной из причин появления новых методов является передача видео через стриминговые сервисы. Целью данного исследования является изучение способов сжатия видео и определение сфер применения данных способов. Для достижения поставленной цели был сформирован ряд задач, к которым относится, изучение структуры стримингового сервиса, анализ входной и выходной информации, изучение способов сжатия видео. Итоговым результатов данной работы является вывод, какой способ подходит к определенной сфере и выборе конечного способа для дальнейшего исследования.
Цель исследования - построить модель машинного обучения для декомпозиции текстовой формулировки компетенции. В данной статье рассматриваются методы представления компетенции как множества ключевых слов и терминов. Основное содержание исследования составляет анализ применения двух моделей: BERTopic и ARTM. Описываются основные этапы исследования: сбор и предобработка данных, обучение моделей, анализ и интерпретация результата. В заключении раскрываются преимущества и недостатки применения таких моделей, а также последующие направления исследования.
В статье предложена реализация простого интеллектуального помощника, работающего по модели классификации намерений. Предложен алгоритм распределенной платформы, которая определяет намерение пользователя и отвечает заготовленным ответом в один из каналов. Представлен пайплайн обработки данных и модель, работающая с полными и разреженными признаками. Обучены несколько архитектур, выбрана лучшая, с учётом метрик быстродействия и точности.
Рассматриваются регулярные, контекстно-свободные и контекстно-зависимые грамматики, их основные свойства и возможности применения при создании документов на основе шаблона в формате LaTeX. Описывается конкретный набор грамматик, которые могут использоваться для разбора структуры документов, включая описание таблиц, списков и блоков текста. Применение данного подхода может значительно упростить и автоматизировать процесс создания и редактирования документов.
В статье представлен метод встраивания данных, основанный на стеганографических алгоритмах, который скрывает информацию в изображениях SVG формата. Встраивание скрытых данных производится с помощью классов. Алгоритм извлечения данных происходит с помощью тэгов по атрибуту. Проведено экспериментальное исследование устойчивости предложенного алгоритма. Для эксперимента было выбрано 100 сайтов с произвольным количество изображений формата SVG. В такие изображения встроена информация разного размера, скрытая в классах дочерних svg тэгов. Предложенный алгоритм может быть использован для передачи скрытых данных в сети Интернет и встраивания цифровых водяных знаков.
Издательство
- Издательство
- ОмГТУ
- Регион
- Россия, Омск
- Почтовый адрес
- 644050, Российская Федерация, г. Омск, пр-т Мира, д. 11
- Юр. адрес
- 644050, Российская Федерация, г. Омск, пр-т Мира, д. 11
- ФИО
- Корчагин Павел Александрович (Ректор )
- E-mail адрес
- info@omgtu.ru
- Контактный телефон
- +7 (381) 2653407
- Сайт
- https://omgtu.ru/