МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский государственный университет Факультет прикладной математики и информатики Кафедра математической физики АЛГОРИТМЫ ПОИСКА СООБЩЕСТВ С ПЕРЕСЕЧЕНИЯМИ В КОМПЛЕСНЫХ СЕТЯХ МИЦКЕВИЧ АРТЁМ ДМИТРИЕВИЧ Руководитель Соболевский Станислав Леонидович проф. кафедры ММУ, доктор физ.-мат. наук Мицкевич А.Д г.

РЕФЕРАТ Объект исследования – комплексные сети. Цель проекта – изучение и анализ алгоритмов поиска сообществ с пересечениями в комплексных сетях. Результатом является выявление наиболее оптимальных алгоритмов. Областью применения является выявление сообществ в таких сферах, как математика, физика, социология, биология. Мицкевич А.Д г.

СООБЩЕСТВА В КОМПЛЕКСНЫХ СЕТЯХ Комплексные сети - существующие в природе сети (графы), обладающие нетривиальными топологическими свойствами. Сообщества – группы вершин, в которых концентрация ребер выше чем между этими группами вершин. Мицкевич А.Д г.

МОДУЛЬНОСТЬ Функция модульности говорит о «качестве» разбиения графа на сообщества. Пример одной из функций модульности: Мицкевич А.Д г.

МЕРА КАЧЕСТВА Мицкевич А.Д г. Мера качества позволяет сравнивать полученное разбиение с действительным. Например: число пар вершин с одинаковой принадлежностью сообществам, деленное на общее число пар вершин.

МЕТОД ФИЛЬТРАЦИИ КЛИК Мицкевич А.Д г. ищутся все k и более клики ищутся все цепочки k-клик, которые и будут сообществами

Мицкевич А.Д г. МЕТОД КЛАСТЕРИЗАЦИИ РЕБЕР для всех пар ребер вычисляется мера схожести этих ребер проводится иерархическая кластеризация сообществ по параметру схожести ребер

Мицкевич А.Д г. CONGA 1. вычисление «центральности» для всех ребер и меры "разделенности" для всех вершин 2. удаление ребра с максимальной «центральностью», либо разделение вершины, если ее мера "разделенности" больше максимальной "центральности" для ребер 3. пересчет «центральности» для всех ребер и меры "разделенности" для всех вершин 4. повторение операции 2

Мицкевич А.Д г. CONGA

Мицкевич А.Д г. ГЕНЕРАЦИЯ ГРАФОВ количество вершин количество сообществ и их размеры плотность ребер внутри одного сообщества и между сообществами

Мицкевич А.Д г. ГЕНЕРАЦИЯ ГРАФОВ

СРАВНЕНИЕ АЛГОРИТМОВ Мицкевич А.Д г.

СРАВНЕНИЕ АЛГОРИТМОВ Мицкевич А.Д г.

ЗАКЛЮЧЕНИЕ изучены и рассмотрены наиболее популярные на данный момент алгоритмы реализована программа, позволяющая строить графы с кластерной структурой на построенных графах проведено сравнение алгоритмов, сделаны выводы реализована визуализация полученных разбиений Мицкевич А.Д г.

СПАСИБО ЗА ВНИМАНИЕ