Распределённый расчёт графовых статистик на реальных и синтетических социальных графах. Кирилл Чихрадзе

2 План доклада: 1. Что есть граф? Типы графов и сетей. 2. Основные статистики графа: определения и примеры. 3. Параллелизация алгоритмов по подсчётам статистик.

3 Граф это упорядоченная пара G=(V, E), где V непустое множество вершин (или узлов), а E множество пар вершин, называемых рёбрами

4 Граф это упорядоченная пара G=(V, E), где V непустое множество вершин (или узлов), а E множество пар вершин, называемых рёбрами Типы графов

5 Граф это упорядоченная пара G=(V, E), где V непустое множество вершин (или узлов), а E множество пар вершин, называемых рёбрами Типы графов Неориентированные

6 Граф это упорядоченная пара G=(V, E), где V непустое множество вершин (или узлов), а E множество пар вершин, называемых рёбрами Типы графов Неориентированные Ориентированные

7 Типы сетей Нейронные сети: вершины нейроны, рёбра соединения между ними.

8 Типы сетей Нейронные сети: вершины нейроны, рёбра соединения между ними. Белковые сети: вершины белки, рёбра физическое взаимодействие между ними.

9 Типы сетей Нейронные сети: вершины нейроны, рёбра соединения между ними. Белковые сети: вершины белки, рёбра физическое взаимодействие между ними. Дорожные сети: вершины пересечения дорог, рёбра собственно дороги.

10 Типы сетей Нейронные сети: вершины нейроны, рёбра соединения между ними. Белковые сети: вершины белки, рёбра физическое взаимодействие между ними. Дорожные сети: вершины пересечения дорог, рёбра собственно дороги. Коммуникационные сети моделируют связи с рёбрами, представляющими собственно связи.

11 Типы сетей Нейронные сети: вершины нейроны, рёбра соединения между ними. Белковые сети: вершины белки, рёбра физическое взаимодействие между ними. Дорожные сети: вершины пересечения дорог, рёбра собственно дороги. Коммуникационные сети моделируют связи с рёбрами, представляющими собственно связи. Сети цитирования: вершины статьи, рёбра цитирования этих статей

12 Типы сетей Нейронные сети: вершины нейроны, рёбра соединения между ними. Белковые сети: вершины белки, рёбра физическое взаимодействие между ними. Дорожные сети: вершины пересечения дорог, рёбра собственно дороги. Коммуникационные сети моделируют связи с рёбрами, представляющими собственно связи. Сети цитирования: вершины статьи, рёбра цитирования этих статей. Вэб-графы: вершины страницы, рёбра гиперссылки между ними.

13 Типы сетей Нейронные сети: вершины нейроны, рёбра соединения между ними. Белковые сети: вершины белки, рёбра физическое взаимодействие между ними. Дорожные сети: вершины пересечения дорог, рёбра собственно дороги. Коммуникационные сети моделируют связи с рёбрами, представляющими собственно связи. Сети цитирования: вершины статьи, рёбра цитирования этих статей. Вэб-графы: вершины страницы, рёбра гиперссылки между ними. Социальные сети.

14 Социальный граф это граф, узлы которого представлены социальными объектами, такими как пользовательские профили с различными атрибутами (например: имя, день рождения, родной город и т. д.), сообщества, медиаконтент и т. д., а ребра социальными связями между ними.

15 План доклада: 1. Что есть граф? Типы графов и сетей. 2. Основные статистики графа: определения и примеры. 3. Параллелизация алгоритмов по подсчётам статистик.

16 Степень вершины количество рёбер графа, инцидентных данной вершине

17 Расстояние между вершинами наименьшее число рёбер пути, соединяющего две вершины. Диаметр графа это максимальное из расстояний между парами его вершин d= d= d=4

18 Компонента связности неориентированного графа некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества

19 Компонента связности неориентированного графа некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества

20 Ориентированный граф называется сильно связным, если любые две его вершины сильно связаны. Две вершины s и t графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Компонентами сильной связности ориентированного графа называются его максимальные по включению сильно связные подграфы.

21 Коэффициент кластеризации измеряет плотность подграфа, состоящего из вершин, находящегося на расстоянии единицы от центрального актора. c i = 2 e jk: v j, v k N i, e jk E k i (k i 1) c i = e jk: v j, v k N i, e jk E k i (k i 1) Глобальный коэффициент кластеризации: с = 3 число треугольников в сети число "вилок" = 6 число треугольников в сети число путей длины 2 1 треугольник и 8 «вилок» с = 3 8

22 Зачем нужны эти статистики: - сравнение сгенерированных и сэмплированных графов; - классификация графов; - сравнение моделей генерации случайных графов; - контроль качества техник сэмплирования;

23 Безмасштабная сеть Безмасштабная сеть сеть, в которой распределение степеней подчиняется power law: P k

k β Свойства: - «малый мир» (эффективный диаметр мал); - наличие т.н. хабов вершин, степени которых очень велики по сравнению со степенями остальных узлов; - малочувствительность к поврежедениям/иерархичность (большие хабы окружены меньшими, а те, в свою очередь, ещё меньшими, что позволяет сохранять почти все связи при потере одного из хабов);

24 Безмасштабная сеть Примеры: - социальные сети; - семантические сети; - различные компьютерные сети, включая WWW; - белковые сети; - схемы авиационных линий;

25 доля от всех вершин Распределение степеней вершин Классическое Power law p x = Cx α Распределение степеней вершин в Facebook (средняя степень = 280) степень степень

26 количество вершин Распределение степеней вершин Распределение степеней вершин в сэмпле Twitter (средняя степень = 15, V=11,316,811) степень (входящая) степень (исходящая)

27 количество вершин Распределение степеней вершин Распределение степеней вершин в сэмпле Amazon (средняя степень = 17, V=403,394) Граф Amazon: вершины товары, рёбра между вершинами если два товара часто покупают вместе. степень

28 количество вершин Распределение степеней вершин Распределение степеней вершин в Web-Google (средняя степень = 12, V=875,713) вершины страницы, рёбра гиперссылки степень (входящая) степень (исходящая)

29 количество вершин Распределение степеней вершин Распределение степеней вершин в Google+ (средняя степень = 265, V=102,100) степень (входящая) степень (исходящая)

30 Доля пар вершин на указанном расстоянии Диаметр N(h) показывает процент пар вершин, достижимых за h шагов. Facebook N(h) Расстояние (h)

31 Доля пар вершин на указанном расстоянии Диаметр N(h) показывает процент пар вершин, достижимых за h шагов. Facebook N(h) d eff = h max h=1 h N h N h 1 N h max N(0) Расстояние (h)

32 Доля пар вершин на указанном расстоянии Диаметр N(h) показывает процент пар вершин, достижимых за h шагов. Facebook N(h) d eff = h max h=1 h N h N h 1 N h max N(0) d U.S. = 4. 3 d Global = 4. 7 Расстояние (h)

33 Количетво пар вершин на указанном расстоянии Диаметр N(h) показывает количество пар вершин, достижимых за h шагов. Twitter d eff = Расстояние (h)

34 Количетво пар вершин на указанном расстоянии Диаметр N(h) показывает количество пар вершин, достижимых за h шагов. Amazon d eff = Расстояние (h)

35 Количетво пар вершин на указанном расстоянии Диаметр N(h) показывает количество пар вершин, достижимых за h шагов. Web-Google d eff = Расстояние (h)

36 Количетво пар вершин на указанном расстоянии Диаметр N(h) показывает количество пар вершин, достижимых за h шагов. Google+ d eff = Расстояние (h)

37 количество компонент Компоненты связности размер компоненты Наибольшая компонента связности графа Facebook 99,91%

38 средний коэффициент кластеризации Коэффициент кластеризации Для пользователя Facebook со степенью 100 средний коэффициент кластеризации 0.14, т.е. 14% его друзей состоят в друзьях друг у друга. степень

39 средний коэффициент кластеризации Коэффициент кластеризации Twitter cc average = степень

40 средний коэффициент кластеризации Коэффициент кластеризации Amazon cc average = степень

41 средний коэффициент кластеризации Коэффициент кластеризации Web-Google cc average = степень

42 средний коэффициент кластеризации Коэффициент кластеризации Google+ cc average = степень

43 Сравнения с помощью статистик Сгенерированный граф Facebook d eff = d eff = Наибольшая компонента 99,97% Наибольшая компонента 99,91%

44 План доклада: 1. Что есть граф? Типы графов и сетей. 2. Основные статистики графа: определения и примеры. 3. Параллелизация алгоритмов по подсчётам статистик.

45 Распределённый алгоритм подсчёта диаметра

46 Распределённый алгоритм подсчёта диаметра

47 Распределённый алгоритм подсчёта диаметра

48 Распределённый алгоритм подсчёта диаметра d n + m Time complexity of HADI O( M ) Space complexity of HADI O( n + m log n) n количество вершин; m количество рёбер; d количество итераций; M количество машин Определяет эффективный диаметр расстояние, за которое 90% связанных пар вершин достигнут друг друга.

49 Распределённый алгоритм подсчёта распределения степеней Mapper Reducer

Использование модели социальной сети с сообществами пользователей для распределённой генерации случайных социальных графов

Использование модели социальной сети с сообществами пользователей для распределённой генерации случайных социальных графов Институт системного программирования РАН Кирилл Чихрадзе 10-я Международная конференция

Некоторые задачи анализа социальных сетей. Славнов Константин

Некоторые задачи анализа социальных сетей Славнов Константин 15.10.2014 План Что это такое. Примеры. Особенности Что можно посчитать Как можно моделировать Деанонимизация Что такое социальная сеть Дружеские

Распределённая генерация случайных графов на основе моделей социальных сетей

Распределённая генерация случайных графов на основе моделей социальных сетей Институт системного Кирилл программирования РАН Чихрадзе et al. chykhradze@ispras.ru GraphHPC-2015 5 марта, 2015 Москва, Россия

ФИЗИЧЕСКИЙ ФАКУЛЬТЕТ. Курсовая работа по дисциплине Параллельное программирование. Образование гигантского кластера в случайных сетях.

Московский государственный университет имени М.В.Ломоносова ФИЗИЧЕСКИЙ ФАКУЛЬТЕТ Курсовая работа по дисциплине Параллельное программирование Образование гигантского кластера в случайных сетях. Выполнил

Анализ процессов в социальных сетях. Николай Скворцов

Анализ процессов в социальных сетях Николай Скворцов Сетевые процессы и классы задач Социальные сети живые системы Модели развития сетей Закономерности различных моделей Устойчивость сети к воздействиям

Методы построения социо-демографических профилей пользователей сети Интернет

Чем старше человек, тем больше ему лет Методы построения социо-демографических профилей пользователей сети Интернет Институт Системного программирования РАН Факультет ВМК МГУ Содержание Введение Постановка

Методы получения репрезентативной выборки пользователей социальных сетей

Методы получения репрезентативной выборки пользователей социальных сетей Гомзин Андрей Геннадьевич ИСП РАН 18 марта 2014 г. Андрей Гомзин (ИСП РАН) Сэмплинг социальных сетей 18 марта 2014 г. 1 / 70 План

Лекция 9. Алгоритм DFS. Осень 2010 МИФИ. (МИФИ) Лекция 9 Осень / 10

Лекция 9 Алгоритм DFS. МИФИ Осень 2010 (МИФИ) Лекция 9 Осень 2010 1 / 10 Напоминание. Граф G(V, E). (МИФИ) Лекция 9 Осень 2010 2 / 10 Напоминание. Граф G(V, E). Разновидности: Ориентированные / неориентированные.

Задачи на графы. Беркунский Е.Ю., кафедра ИУСТ, НУК

Задачи на графы Беркунский Е.Ю., кафедра ИУСТ, НУК eugeny.berkunsky@gmail.com http://www.berkut.mk.ua Определения Граф или неориентированный граф G это упорядоченная пара G: = (V,E), для которой выполнены

Тема 2.3. Деревья. Характеристики графов. Тема Деревья и их свойства.

Тема 2.3. Деревья. Характеристики графов Тема 2.3.1. Деревья и их свойства. Выполните задания НА ЗНАНИЕ ТЕОРЕТИЧЕСКОГО МАТЕРИАЛА А) граф с семью вершинами и шестью ребрами, не имеющий циклов, Б) связный

Анализ сообществ в социальных сетях. Николай Скворцов

Анализ сообществ в социальных сетях Николай Скворцов Социальные сети как области с интенсивным использованием данных Телекоммуникационные связи (звонки, адресные книги и др.) Информационные сети (медиа,

Элементы теории графов. Деревья, плоские графы, раскраски графов

Элементы теории графов Деревья, плоские графы, раскраски графов Дерево Деревом называется неориентированный связный граф, не содержащий циклов. В дереве существует один и только соединяющий каждую пару

Современные проблемы анализа данных пользователей социальных сетей

Современные проблемы анализа данных пользователей социальных сетей Коршунов Антон Викторович korshunov@ispras.ru Gartner Hype Cycle for Emerging Technologies 2012 Социальная сеть Пользователи, объекты,

Тема 2.2. Маршруты, связность, расстояния. Задачи об обходах. Тема Маршруты, циклы, связность, расстояния, диаметр и центр графа

Тема 2.2. Маршруты, связность, расстояния. Задачи об обходах Тема 2.2.1. Маршруты, циклы, связность, расстояния, диаметр и центр графа Маршрутом в графе называется чередующаяся последовательность вершин

Задача по теории графов с решением Характеристики графа

ЗАДАНИЕ. Задача по теории графов с решением Характеристики графа Считая данный граф неориентированным, обозначить его вершины и рёбра разными символами и определить. 3.1. Локальные степени и окружения

Лекция 3: Маршруты и связность

Уральский федеральный университет, Институт математики и компьютерных наук, кафедра алгебры и дискретной математики Определения маршрута, цепи, цикла Определение Маршрутом в графе называется последовательность

Тема Основные понятия теории графов

Тема 2.1.1. Основные понятия теории графов Преимущества использования теории графов Простой и мощный инструмент моделирования систем и решения задач упорядочения объектов Методы ТГ (комбинаторные) отличаются

Алгоритмы на графах ч.1. Беркунский Е.Ю., кафедра ИУСТ, НУК

Алгоритмы на графах ч.1 Беркунский Е.Ю., кафедра ИУСТ, НУК eugeny.berkunsky@gmail.com http://www.berkut.mk.ua Определения Граф или неориентированный граф G это упорядоченная пара G: = (V,E), для которой

Алгоритмы и структуры данных

Алгоритмы и структуры данных Косяков Михаил Сергеевич к.т.н., доцент кафедры ВТ Тараканов Денис Сергеевич ассистент кафедры ВТ Бабаянц Александр Амаякович https://vk.com/algoclass_2018 Содержание курса

Лекция 14: Орграфы. Б.М.Верников, А.М.Шур

Уральский федеральный университет, Институт математики и компьютерных наук, кафедра алгебры и дискретной математики Вступительные замечания Если мы захотим изобразить схему дорожного движения в городе

Метрические характеристики. Матричное представление графов

Теория конечных графов Метрические характеристики. Матричное представление графов Лектор: к.ф.-м.н., старший преподаватель кафедры прикладной информатики и теории вероятностей РУДН Зарипова Эльвира Ринатовна

ИСПОЛЬЗОВАНИЕ ОСОБЕННОСТЕЙ ВЗВЕШЕННЫХ ГРАФОВ ДЛЯ БОЛЕЕ БЫСТРОГО ОПРЕДЕЛЕНИЯ ИХ ХАРАКТЕРИСТИК А. Р. Ураков, Т. В. Тимеряев

ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2012 Прикладная теория графов 2(16) УДК 519.173.5 ИСПОЛЬЗОВАНИЕ ОСОБЕННОСТЕЙ ВЗВЕШЕННЫХ ГРАФОВ ДЛЯ БОЛЕЕ БЫСТРОГО ОПРЕДЕЛЕНИЯ ИХ ХАРАКТЕРИСТИК А. Р. Ураков, Т. В. Тимеряев

Пыркина Ольга Евгеньевна

Московский семинар по социофизике им. Д.С.Чернавского Институте проблем управления РАН ПРИМЕНЕНИЕ ГРАФОВОЙ АНАЛИТИКИ ДЛЯ АНАЛИЗА СИСТЕМЫ ОБОРОТА ЭЛЕКТРОННЫХ ДЕНЕГ: ВОЗМОЖНОСТИ, ОЦЕНКИ, ПЕРСПЕКТИВЫ Доклад

Структура сложных сетей. Юрий Лифшиц. Осень 2006

Структура сложных сетей Лекция N 4 курса Алгоритмы для Интернета Юрий Лифшиц ПОМИ РАН - СПбГУ ИТМО Осень 2006 1 / 34 M.E.J. Newman Six degrees of separation - - это гипотеза, утверждающая что от любой

ВВЕДЕНИЕ В БИОИНФОРМАТИКУ

ВВЕДЕНИЕ В БИОИНФОРМАТИКУ Лекция 6 Элементы теории графов Новоселецкий Валерий Николаевич к.ф.-м.н., доц. каф. биоинженерии valery.novoseletsky@yandex.ru Сайт курса http://intbio.org/bioinf2018 2 Задача

> пространства R и множества E = < e i

3 Задание: Дан неориентированный граф G, где V(G) - множество вершин; Е(G) - множество ребер Изобразить его графически Определить степени его вершин Указать висячие/изолированные вершины Является ли граф

Ориентированные графы

Теория конечных графов Ориентированные графы Лектор: к.ф.-м.н., доцент кафедры прикладной информатики и теории вероятностей РУДН Зарипова Эльвира Ринатовна zarip@mail.ru Литература. Зарипова Э.Р., Кокотчикова

Лектор - доцент Селезнева Светлана Николаевна. Лекции по Дискретным моделям. Магистратура, 1-й курс, факультет ВМК МГУ имени М.В.

Лекция 7. Задача выбора маршрутов и ее частный случай задача распределения рейсов по дням. Графовая модель для задачи распределения рейсов. Хроматическое число графа. Критерий двураскрашиваемости графа.

Транспортные схемы (сети ЭВМ) Модели процессов Планирование (Сетевой график) Алгоритмизация Модели органической химии. Моделирование задача Эйлера

Содержание Введение 1. Основные понятия теории графов 2. Степень вершины 3. Маршруты, цепи, циклы 5. Ориентированные графы 6. Изоморфизм графов 7. Плоские графы 8. Операции над графами 9. Способы задания

Теория графов. Максименкова Ольга Вениаминовна, старший преподаватель департамента программной инженерии факультета компьютерных наук НИУ ВШЭ

Теория графов Максименкова Ольга Вениаминовна, старший преподаватель департамента программной инженерии факультета компьютерных наук НИУ ВШЭ Соглашения о терминологии() Обозначение графа G = (V, E), где

Кластеризация. Каждый кластер состоит из похожих объектов Объекты из разных кластеров существенно отличаются

Кластеризация Дано: матрица «объекты-признаки» X Найти: 1. Множество кластеров Y 2. Алгоритм кластеризации a(x), который приписывает каждый объект к одному из кластеров Каждый кластер состоит из похожих

Институт радиоэлектроники и информационных технологий. Кафедра информатики и систем управления

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМ. Р.

Элементы теории графов. Влияние в сетевых структурах

Элементы теории графов. Влияние в сетевых структурах Ф.Т. Алескеров НИУ ВШЭ и ИПУ РАН Определение графа Граф G(V, E) математический объект, состоящий из множества вершин V = 1,, n множества рёбер E V V.

Практическая работа 7 Выполнение операций над графами Цель работы: закрепить умения вычислять числовые характеристики и выполнять операций над

Практическая работа 7 Выполнение операций над графами Цель работы: закрепить умения вычислять числовые характеристики и выполнять операций над графами Оборудование (приборы, материалы, дидактическое обеспечение):

Лекция: Графы. Основные понятия. Связные графы. Деревья. Остовное дерево. Число висячих вершин в остовном дереве.

Лекция: Графы. Основные понятия. Связные графы. Деревья. Остовное дерево. Число висячих вершин в остовном дереве. Лектор - доцент Селезнева Светлана Николаевна Лекции по Дискретным моделям. Магистратура,

Тема: Основные понятия теории графов. Неориентированные графы. e 1. e 4. e 5. e 2

Лабораторный практикум по дисциплине «Теория конечных графов» Тема: Основные понятия теории графов Неориентированные графы Лабораторная работа Дан граф G V, E V e e e e V e V e e Определить: ) Множества

Методы анализа социальных сетей. Базовые понятия

Методы анализа социальных сетей. Базовые понятия Николай Ильич Базенков, к.т.н. Институт проблем управления им. В.А. Трапезникова Российской академии наук 16 сентября 2015 г. Содержание курса Лекция 1

Darwini: Геренация реалистичных синтетических графов

Darwini: Геренация реалистичных синтетических графов Sergey Edunov Facebook Dionysios Logothetis Facebook Cheng Wang University of Houston Avery Ching Facebook Maja Kabiljo Facebook Проблема Нам самим

Практическая работа 13 «Построения остовного дерева» Теоретический материал и методические указания к выполнению заданий. 1.

Практическая работа «Построения остовного дерева» Цели занятия: - закрепить усвоение теоретического материала по данной теме через решение упражнений; - научиться строить графы; - научиться строить остовное

Лекция 7: Двудольные графы

Уральский федеральный университет, Институт математики и компьютерных наук, кафедра алгебры и дискретной математики Определение и пример Определение Граф G = V,E называется двудольным, если существуют

Лабораторный практикум по теории графов

Зарипова ЭР РУДН, Физ-мат Лабораторный практикум по теории графов Тема: Основные понятия теории графов Неориентированные графы Дан граф G( VE, ) (рис ): Лабораторная работа V e V e e e V e V e e Рисунок

Выявление аномалий в графах с использованием программной платформы Apache Spark

Выявление аномалий в графах с использованием программной платформы Apache Spark А.В. Мазеев, А.С. Семенов, Д.И. Дорофеев 1.03.2018 План Обзор методов выявления аномалий Выявление аномалий в реальном графе

Методы построения социо-демографических профилей пользователей сети Интернет

ОГЛАВЛЕНИЕ. для общения 22

ОГЛАВЛЕНИЕ Введение 8 1 Особенности онлайн социальных сетей для общения, как объекта деструктивных управляющих воздействий 13 1.1 Структурно-функциональная специфика онлайн социальных сетей для общения

АСИМПТОТИКА ВЕРОЯТНОСТИ СВЯЗНОСТИ ГРАФА С НИЗКОНАДЁЖНЫМИ РЁБРАМИ 1 Г. Ш. Цициашвили, М. А. Осипова, А. С. Лосев

ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2013 Прикладная теория графов 1(19) УДК 519.248:62-192+519.176 АСИМПТОТИКА ВЕРОЯТНОСТИ СВЯЗНОСТИ ГРАФА С НИЗКОНАДЁЖНЫМИ РЁБРАМИ 1 Г. Ш. Цициашвили, М. А. Осипова, А. С.

Network analysis. Кольцов С.Н

Network analysis Кольцов С.Н Исследование социальных сетей Исследование сетей (Network analysis) Теория графов раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется

M.E.J. Newman. Структура сложных сетей. Юрий Лифшиц

M.E.J. Newman Структура сложных сетей Лекция N 4 курса Алгоритмы для Интернета Юрий Лифшиц ПОМИ РАН - СПбГУ ИТМО Осень 2006 Six degrees of separation - - это гипотеза, утверждающая что от любой человек

Приближенные алгоритмы для NP-полных задач

Приближенные алгоритмы для NP-полных задач В некоторых случаях, требуется за приемлемое время решить задачу, про которую известно, что она NP-полна. Найти точное решение за полиномиальное время возможно

1. Организация учебного процесса 2. Неориентированные графы

Теория конечных графов. Организация учебного процесса 2. Неориентированные графы Лектор: к.ф.-м.н., доцент кафедры прикладной информатики и теории вероятностей РУДН Зарипова Эльвира Ринатовна ezarip@mail.ru

Лектор Селезнева Светлана Николаевна Лекции на сайте факультет ВМК МГУ имени М.В.

Лекция 1. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья. Лектор Селезнева Светлана Николаевна selezn@cs.msu.su

Чем отличается настоящая карта контактов ДНК от случайной матрицы

Чем отличается настоящая карта контактов ДНК от случайной матрицы Валерия Ковалева, Сергей Нечаев valeriya.kovaleva@phystech.edu МФТИ, Сколтех Май 2017 Введение Карта контактов - симметричная бинарная

АЛГОРИТМЫ НА ГРАФАХ: ВВЕДЕНИЕ

Элементы теории алгоритмов и структур данных АЛГОРИТМЫ НА ГРАФАХ: ВВЕДЕНИЕ Примечание Данный материал является вспомогательной презентацией и сам по себе не может рассматриваться как конспект курса лекций

Задача A. Остовное дерево (1 балл)

Задача A. Остовное дерево (1 балл) spantree.in spantree.out Даны точки на плоскости, являющиеся вершинами полного графа. Вес ребра равен расстоянию между точками, соответствующими концам этого ребра. Требуется

Программа коллоквиума по дискретной математике (основной поток)

Программа коллоквиума по дискретной математике (основной поток) В начале коллоквиума Вы получите билет, в котором будет три вопроса: вопрос на знание определений, задача, вопрос на знание доказательств.

ЛЕКЦИЯ 1 ОБХОДЫ ГРАФОВ

ЛЕКЦИЯ 1 ОБХОДЫ ГРАФОВ Существуют два классических понятия, связанных с обходами графов: эйлеров цикл и гамильтонов цикл. Определение 1: Эйлеров цикл (в графе) цикл, который содержит все ребра этого графа.

Лекция 4. Графы. Основные понятия. Связные графы. Деревья. Остовное дерево. Число висячих вершин в остовном дереве.

Лекция 4. Графы. Основные понятия. Связные графы. Деревья. Остовное дерево. Число висячих вершин в остовном дереве. Лектор д.ф.-м.н. Селезнева Светлана Николаевна Лекции по «Дискретным моделям». Магистратура,

Кластеризация и алгоритм EM

и алгоритм EM Казанский Федеральный Университет, 2014 и алгоритм EM Outline Иерархическая кластеризация методами теории графов 1 Иерархическая кластеризация методами теории графов 2 и алгоритм EM Суть

План практикума по курсу «Алгоритмы и структуры данных»

План практикума по курсу «Алгоритмы и структуры данных» Приводится примерный список задач для разбора на практических занятиях (38 часов 19 пар). Занятия 1-4 (8 часов). Работа с файлами. 1. Дан текстовый

Задача вершинного покрытия

Задача вершинного покрытия Сергей Воронов Московский физико-технический институт (государственный университет) Факультет управления и прикладной математики 11 декабря 2013 г. Сергей Воронов (МФТИ) Задача

Алгоритмы и структуры данных

Задачу нахождения потока максимальной мощности (максимального потока) можно записать в виде

6. Потоки в сетях В данном разделе сеть это связный ориентированный граф G = (V, E) без петель и мультидуг с одним источником s и одним стоком t, в котором каждой дуге (i, j) E приписана пропускная способность

Лабораторная работа 7

Лабораторная работа Тема: «Метод Форда» Цель работы: Получить практические навыки решения сетевых задач методом Форда. Предварительная подготовка: спец. дисциплина «Математические методы» Количество часов:

1 / 24

Точные алгоритмы и открытые проблемы Лекция N 2 курса Современные задачи теоретической информатики Юрий Лифшиц yura@logic.pdmi.ras.ru ИТМО Осень 2005 1 / 24 Закон Хоара (о больших задачах) : "Внутри каждой

MST на мультипроцессоре: сравнение вариантов алгоритма Борувки. Зайцев Вадим, Новосибирский ГУ Калгин Константин, к.ф.-м.н.

MST на мультипроцессоре: сравнение вариантов алгоритма Борувки Зайцев Вадим, Новосибирский ГУ Калгин Константин, к.ф.-м.н., ИВМиМГ СО РАН Минимальное остовное дерево (MST) Остовное дерево - ациклический

Кластеризация и алгоритм EM

Академический Университет, 2012 Outline Иерархическая кластеризация методами теории графов 1 Иерархическая кластеризация методами теории графов 2 Суть лекции Иерархическая кластеризация методами теории

Теория сложных сетей новый инструмент анализа в экономических задачах. к.э.н. Сергей Вячеславович Макрушин ноябрь 2016 г.

Теория сложных сетей новый инструмент анализа в экономических задачах к.э.н. Сергей Вячеславович Макрушин SVMakrushin@fa.ru ноябрь 2016 г. Знакомство с теорией сложных сетей 2 ТЕОРИЯ СЛОЖНЫХ СЕТЕЙ 3 Теория

Занятие 10. Графы I. Определения, хранение

Занятие 10. Графы I. Определения, хранение Задачи стр. 6 Подсказки стр. 11 Разборы стр. 12 Справочник стр. 15 Многие, совершенно различные системы реального мира, например хорошо представляются при помощи

Тема 6. Эйлеровы графы

Тема 6. Эйлеровы графы 6.1. Эйлеровы графы, необходимые и достаточные условия эйлеровости Определение. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой

ПРАКТИКА 6 ГРАФЫ. Граф системы управления представляет собой ориентированный граф, который обладает следующими свойствами:

ПРАКТИКА 6 ГРАФЫ Математическую модель системы управления наглядно можно представить с помощью ориентированных графов. Графом называется совокупность множества V точек, называемых вершинами, и множества

Разработка и реализация алгоритма инкрементальной поуровневой визуализации сетей цитирования

Разработка и реализация алгоритма инкрементальной поуровневой визуализации сетей цитирования Мезин Александр Евгеньевич гр. 9202 ФИТ НГУ Научный руководитель Апанович Зинаида Владимировна к.ф.-м.н., с.н.с

Элементы теории графов. Теория Графов. Alexander Lazarev. Institute of Control Sciences of Russian Academy of Sciences учебный год

Теория Графов Alexander Lazarev Institute of Control Sciences of Russian Academy of Sciences 2009-2010 учебный год Outline 1 Элементы теории графов Степени вершин О машинном представлении графов Поиск

Элементы теории графов. Основные определения.

Элементы теории графов. Основные определения. Ориентированный граф Задано множество X=. На множестве Х задано бинарное отношение R X X Ориентированный граф упорядоченная пара множеств (X,

Лектор доцент Селезнева Светлана Николаевна Лекции на сайте Факультет ВМК МГУ имени М.В.

Лекция: Графы и сети. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами. Планарные графы. Формула Эйлера для планарных графов. Наибольшее число ребер в планарных графах. Непланарность

Тема 10. Раскрашивание графов

Тема 10. Раскрашивание графов 10.1. Хроматическое число Определение. Граф G называется k-раскрашиваемым, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные

Вступительная работа ЛКШ 2009, группа A, 15 апреля, 2009

Не забывайте, что решение задач теоретической и математической частей должно содержать не только ответ, но и его обоснование (доказательство)! 1 Теоретическое задание Задание A-T1 Докажите, что не существует

Программа "зимнего"коллоквиума по дискретной математике(основной поток)

Программа "зимнего"коллоквиума по дискретной математике(основной поток) В начале коллоквиума Вы получите билет, в котором будет три вопроса: контрольный вопрос на понимание определения, задача на понимание

Программа "зимнего"коллоквиума по дискретной математике(основной поток)

Math-Net.Ru Общероссийский математический портал

Math-Net.Ru Общероссийский математический портал В. В. Быкова, Структурная декомпозиция графа и еë применение для решения оптимизационных задач на разреженных графах, ПДМ. Приложение, 2014, выпуск 7, 154

Основы теории графов. V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г.

V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E множества, отображение инциденции f: Е V&V множества Е в V&V V= множество точек, E=

Лекция 8: Институты, сети и трансакционные издержки

Лекция 8: Институты, сети и трансакционные издержки Сети и институт Затраты на существование сетей Сети и трансакционные издержки Инструментарий теории графов Примеры сетей 1 Основные понятия Сетью называется

Дипломная работа. Распределенная генерация случайного графа со степенным распределением вершин. Выполнил: Никомаров Сергей Евгеньевич группа 075

Дипломная работа Распределенная генерация случайного графа со степенным распределением вершин Выполнил: Никомаров Сергей Евгеньевич группа 075 Научные руководители: Пастухов Роман Константинович К.ф.-м.н.Турдаков

Практическая работа 1. Тема: Графическое изображение графов.

Практическая работа Тема: Графическое изображение графов. Цель: изучить основы теоретико-множественного и графического представлений графов, простейших свойств графов, получить практический навык задания

ИСПОЛЬЗОВАНИЕ АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ШТЕЙНЕРА А.И. Ольшевский, М.Ю. Лефаров

УДК 519.173 ИСПОЛЬЗОВАНИЕ АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ШТЕЙНЕРА А.И. Ольшевский, М.Ю. Лефаров Донецкий национальный технический университет кафедра программного обеспечения интеллектуальных

Лекция по алгоритмам #10 Тема: DFS

Лекция по алгоритмам #10 Тема: DFS 11 ноября Собрано 1 января 2015 г. в 19:55 1 Компоненты рёберной двусвязности и мосты 1.1 Основные понятия Рассматриваем связный неориентированный граф G. Определение.

Лекция 6: Деревья. Б.М.Верников, А.М.Шур

Уральский федеральный университет, Институт математики и компьютерных наук, кафедра алгебры и дискретной математики Определение и примеры Определение Деревом называется связный граф без циклов. Примеры

Замкнутые маршруты и алгоритмы сегментации изображений

Замкнутые маршруты и алгоритмы сегментации изображений А. Малистов, И. Иванов-Погодаев, А. Я. Канель-Белов A. Алгоритмы Пусть у нас в распоряжении имеется книга из n страниц. На каждой странице книги написано

Построение репертуара антител

Построение репертуара антител Андрей Слабодкин Руководители: Яна Сафонова Александр Шлемов Центр алгоритмической биотехнологии, СПбГУ IgRepertoireConstructor pipeline На данных секвенирования строится

«Институт менеджмента, маркетинга и финансов»

Автономная образовательная некоммерческая организация высшего образования «Институт менеджмента, маркетинга и финансов» УТВЕРЖДАЮ Ректор О.А. Зайцева 01.10.2015 РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ ЕН.03

План лекции. Алгоритмы и структуры данных Лекция 5: Пути в графах. План лекции. Поиск в ширину. А. Куликов. Поиск в ширину

План лекции Алгоритмы и структуры данных Лекция : Пути в графах А. Куликов Академия современного программирования Поиск в ширину Алгоритм Дейкстры Кратчайшие пути при наличии рёбер отрицательного веса

КОРШУНОВ АНТОН ВИКТОРОВИЧ ИССЛЕДОВАНИЕ СТРУКТУРЫ СООБЩЕСТВ ПОЛЬЗОВАТЕЛЕЙ В ГРАФАХ ОНЛАЙНОВЫХ СОЦИАЛЬНЫХ СЕТЕЙ

Федеральное государственное бюджетное учреждение науки Институт системного программирования Российской академии наук На правах рукописи КОРШУНОВ АНТОН ВИКТОРОВИЧ ИССЛЕДОВАНИЕ СТРУКТУРЫ СООБЩЕСТВ ПОЛЬЗОВАТЕЛЕЙ

Национальный исследовательский университет «МИЭТ» Кафедра ПКИМС. Теория алгоритмов. Лекция 7. Алгоритмы решения сложных задач.

Национальный исследовательский университет «МИЭТ» Кафедра ПКИМС Теория алгоритмов Лекция 7 Алгоритмы решения сложных задач. Нейронные сети: структура нейрона Слайд 2 из 20 x1 w1 x2 w2 S F y wn xn Входы

Мультиагентное диспетчирование ресурсов в гетерогенной облачной среде. И.А. Каляев, А.И. Каляев, Я.С. Коровин

Мультиагентное диспетчирование ресурсов в гетерогенной облачной среде И.А. Каляев, А.И. Каляев, Я.С. Коровин Общая постановка проблемы ОВС должна решать некоторое множество (поток различных крупномасштабных

Лабораторная работа Применение сети Хопфилда для решения задачи коммивояжера

Лабораторная работа Применение сети Хопфилда для решения задачи коммивояжера Цель работы решение задачи коммивояжера с помощью нейронной сети Хопфилда. Содержание: 1. Описать постановку задачи поиска кратчайшего

Математико-механический факультет, учебный год, первый курс Алгоритмы и структуры данных: взвешенные графы, четверг, 13 декабря 2018 года

Задача A. Столица Страна Фландия представляет собой n городов, соединённых дорогами с односторонним движением. Президент Фландии хочет разместить свою резиденцию в центре страны для удобства совершения

Национальный исследовательский университет «МИЭТ» МИЭТ. Кафедра ПКИМС. Теория алгоритмов. Лекция 4. Графы. Способы представления и основные алгоритмы.

МИЭТ Национальный исследовательский университет «МИЭТ» Кафедра ПКИМС Теория алгоритмов Лекция Графы. Способы представления и основные алгоритмы. Кафедра ПКИМС, МИЭТ. Осень 07. Что такое граф? Слайд из

ТЕОРИЯ ГРАФОВ Екатерина Юрьевна Титаренко старший преподаватель Институт кибернетики

Екатерина Юрьевна Титаренко старший преподаватель Институт кибернетики Содержание курса Введение. Определения. Основные понятия. Способы задания графов. Основные типы графов. Операции над графами. Маршруты,

М.Ю. МОНАХОВ М.М. МОНАХОВА Д.В. МИШИН ГРАФОВАЯ МОДЕЛЬ СЕТИ ПЕРЕДАЧИ ДАННЫХ. ОБОБЩЕНИЕ РЕЗУЛЬТАТОВ

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

Лекция 11: Раскраска графа

Уральский федеральный университет, Институт математики и компьютерных наук, кафедра алгебры и дискретной математики Происхождение понятия раскраски графа В приложениях теории графов нередко возникают задачи,

Граничные классы относительно класса планарных графов для задачи о независимом множестве.

Граничные классы относительно класса планарных графов для задачи о независимом множестве. Д.С. Малышев Нижегородский госуниверситет им. Н.И. Лобачевского 1 Введение. Независимым множеством в обыкновенном

📎📎📎📎📎📎📎📎📎📎