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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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