Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
265 lines (215 sloc) 21.6 KB

РОСГРАФ

Аналитическая система повышения прозрачности закупочной деятельности

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

Проблема

Потеря смысла и контекстов

  • Контекст отношений
  • Новые формы деструктивных отношений

Данные не систематизированны

  • Субъективные структуры
  • Смешение понятий

Объем данных для анализа

  • 60 000 обновлений данных компаний ежедневно
  • 6 040 000 компаний в России

Используемые наборы данных

Министерства

Алгоритм поиска связанности

Пользователи системы

Оператор

Поддерживает работоспособность платформы, управляет процессом развития функционала

Регулятор

Орган, осуществляющий мониторинг за соблюдением норм правового поля

Сервисные поставщики

Создают функциональные модули, представляющие ценность для поставщиков и/или потребителей

Поставщики

Предоставляют товары и услуги, рекламируемые и/или продаваемые через платформу

Потребители

Покупатели товаров и услуг

Представление гиперграфа

Команда

  • Борис Черепанов
  • Анна Александрова
  • Роман Иноземцев
  • Валентин Сергеев

Контакты

github.com/mir-one/leadersofdigital

Содержание

Граф и социальный граф Что такое сообщества в графах Зачем производить поиск сообществ Метрики графов Критерии качества разбиения на сообщества Основные методы выделения сообществ Модели социальных графов Примеры разбиений Литература

Что такое социальный граф Социальный граф (далее граф) – набор лиц и отношений:

• сущности (вершины) – социальные объекты (книги, статьи, люди); • вершины обладают специфическими свойствами; • ребра – методы социального взаимодействия • типы отношений: список использованной литературы, цитирование, круги общения и т.п. • В зависимости от выбора связей для рассмотрения, получаются разные графы Граф – совокупность непустого множества вершин и наборов пар вершин (связей).

Особенности социального графа

• Динамический – меняется под действием многих вершин • Натуральный – имеет естественную природу образования • Пример: корпорация, взаимоотношения внутри отдела и между отделами

Типы социального графа

• Цельные сети - отношения в пределах определённо очерченных границ • Электронная почта • Социальная сеть • Эго-сети – каждый элемент выборки в подобном анализе обозначается как «эго», а узлы, связанные с эго, обозначаются как «другие» • Список друзей одного человека • Неполные сети – выборка из относительных данных, созданная методом снежного кома • Выборка + друзья выборки + друзья друзей выборки • Сообщество + другие сообщества подписчиков

###Что такое сообщества в графах Сообщество – группа вершин в графе такая что: • состоит из одной компоненты связности (всегда есть связь между вершинами); • имеет более плотные связи внутри, чем снаружи; • может пересекаться с другими сообществами.

Зачем поиск сообществ

Что можно представить в виде графа • Люди и их социальные взаимоотношения • Люди и их интересы • Интернет-ресурсы и ссылки • Научная литература и цитаты • Бизнес процессы и связи между ними • Протеины и их взаимодействия • Блуждания пользователей по сайтам Важную роль играет тип связей – из одного источника мы можем получить разные графы. Пример: три типа связей – коллеги по работе, собутыльники, друзья по игровому клубу.

Зачем производить поиск сообществ

• Маштабирование графов (Рост размера и сложности) • Поиск определенной группы вершин (людей, связанных научных работ) • Поиск смежных тематик (смежный контент, совместимые научные работы) • Определение альфа-точек (влиятельные вершины) • Предсказание действий вершин из одного сообщества и рекомендации • Идентификация пользователей (поиск одного пользователя в разных сетях) • Выявление «настоящих связей»

Метрики графов - связи

• Гомогенность – степень, с которой схожие по какому-то признаку участники формируют связи между собой в сравнении с несхожими. • Множественность – количество форм, содержащихся в связи (прочность отношений). Пример: коллега по работе и друг, множественность = 2. • Обоюдность/Взаимность – степень, с которой двое участников отвечают друг другу взаимностью в сфере дружеских или других взаимодействий. • Закрытость сети – степень, в которой друзья пользователя являются друзьями друг другу. • Соседство – склонность участников иметь больше связей с теми, кто находится ближе.

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

• Структурные дыры – отсутствие связи между двумя частями сети • Мост – вершины, заполнители структурных дыр • Центральность – степень важности вершин • Расстояние – минимальное количество связей (рёбер) между вершинами • Сила связи – количество путей между вершинами • Плотность – отношение прямых связей в сети к общему возможному количеству связей

Метрики графов - сегментация

• Коэффициент кластеризации – мера вероятности, с которой два партнёра одного узла являются приятелями. • Сплоченность – степень, с которой участники связаны напрямую друг с другом при помощи социальных связей. • Структурная сплочёность – минимальное количество участников, которые, будучи удаленными из группы, развалят группу. • Клика – группа, в которой все пользователи имеют «прямые» связи.

Метрики графов - центральность

• Центральность по степени - количество связей у вершины • Центральность по посредничеству – число кратчайших путей от всех до всех, проходящих через данную вершину • Центральность по близости – сумма расстояний от вершины до всех вершин • Центральность собственного вектора – зависимость между центральностью вершины и центральностями её соседей (сумма центральностей соседних вершин, поделенных на const) • Альфа центральность – распределение влияния вершины между своих соседей • Центральность Каца – количество всех вершин связанных с вершиной, умноженное на коэффициент в зависимости от удаленности этих вершин

Критерии качества разбиения

• Модулярность • Редакторское расстояние для разбиений • Нормализованная взаимная информация Модулярность Описывает, насколько при заданном разбиении графа на группы плотность внутригрупповых связей больше плотности межгрупповых связей. Плюсы: • Модулярность возможно эффективно пересчитывать при небольших изменениях в кластерах. Минусы: • Функционал не непрерывный, задача его оптимизации — дискретная. • Функционал не видит маленькие сообщества.

Модулярность

Редакторское расстояние для разбиений split-join distance = минимальному количеству операций необходимых для преобразования одного разбиения в другое: • Добавить вершину в существующее сообщество. • Удалить вершину из существующего сообщества. • Создать новое сообщество с 1 вершиной. • Удалить сообщество с 1 вершиной. Т.е. чем больше значение, тем более непохожи сообщества

Нормализованная взаимная информация H(X) H(Y) I(X;Y)H(X|Y) H(Y|X) H(X;Y)

Методы выделения

Основные методы выделения сообществ • Betweenness — количество кратчайших путей между всеми парами вершин, проходящих через данное ребро. • Fastgreedy — метод, основанный на жадной оптимизации функции модулярности. • Multilevel — метод, основанный на многоуровневой оптимизации функции модулярности, c использованием эвристики. • LabelPropogation — метод, основанный на присвоении меток к каждой вершине и максимальной встречаемости. • Walktrap — подход, основанный на случайном блуждании. • Infomap — метод случайного блуждания, основанный на понятии информационных потоков в сетях, кодирования и сжатия информации. • Eigenvector — метод, основанный на собственных векторах матрицы модулярности, которая получается из матрицы смежности.

Betweenness

• Подсчет коэффициентов “центральности по посредничеству” на всех ребрах графа. • Поочередное удаление ребер с самым большим коэффициентом. • Сообществами считаются оставшиеся компоненты связности. • Процедура удаления связей завершается, когда достигает максимума модулярность результирующего разбиения. Число кратчайших путей, проходящих через данное ребро

Fastgreedy

• Инициализация сообществ в каждой вершине. • Объединение сообществ, в результате которого максимальным образом увеличивается модулярность. • Выход, если дальнейшее увеличение значения функционала модулярности невозможно. Жадная оптимизация модулярности.

Multilevel

Инициализация сообществ в каждой вершине Первый Этап a. Жадно максимизируем модулярность путем перемещения вершины в сообщество вершины-соседа b. Нет перемещений – Выход. торой этап a. Создать метаграф из полученных сообществ с суммарным весом всех ребер b. Перезапустить алгоритм на метаграфе Многоуровневая оптимизация модулярности.

Multilevel

LabelPropogation • Каждую вершину определяем в своё сообщество. • Определяем в случайном порядке каждую вершину в то сообщество, в которое входит большинство соседей данной вершины. • Повторяем, пока происходят изменения. Для нейтрализации зависимости от порядка, на каждой итерации алгоритма выбирается новый случайный порядок перебора. Результаты нескольких разметок можно агрегировать пересечением. Вершина относится к тому сообществу, что и большинство ее соседей.

Walktrap

• Инициализация сообществ в каждой вершине. • Вычисление расстояния между всеми смежными вершинами. • На каждом шаге: • Выбрать два сообщества C1 и C2, объединение которых минимизирует изменение среднего квадратов расстояний между каждой вершиной графа и их совместным сообществом. • Объединить эти сообщества в одно новое, C3. Обновить расстояния между сообществами. • На n−1 шаге мы получим одно сообщество. Таким образом, выводится дендрограмма (дерево группировки) для вершин графа. • Выбираем наилучшее разбиение, максимизирующее модулярность.

Walktrap

Infomap

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

Infomap

Eigenvector

Методы агрегирования результатов

• Агрегирование кластеризацией (любым из методов) • Агрегирование базовыми методами • Пересечением • Выделением метаграфа и применением к нему метода выделения сообщества Агрегирование нужно для усреднения полученных результатов работы нескольких методов

Методы агрегирования результатов - кластеризация

• Номер сообщества из каждого разбиения – признак • Запустить любой метод кластеризации с категориальными признаками Особенности: • Чувствителен к методу • Чувствителен к метрике • Не гарантирует локальность оптимума • Не гарантирует улучшение результата

Модели социальных графов Потенциально могут заменить «реальные» социальный графы.

• Функционально-управляемые модели – нацелены на воспроизведение статистических характеристик графа (степенное распределение и динамические изменения плотности). • Модель Барабаши — Альберт • Модель «Горящий лес» • Намеренно-управляемые модели – сфокусированы на эмуляцию процесса создания оригинального графа. • Случайный обход/случайные блуждания • Ближайший сосед • Структурно-управляемые модели – на основе статистических данных из структуры графа, воспроизводить случайные графы с теми же структурными ограничениями. • Графы Кронекера • dK-графы

Примеры выделения сообществ – digg.com

Кластеризация сайтов в интернете За 2015 год 18 кластеров Ссылка Кластеризация сайтов в интернете За 2015 год 18 кластеров Без прореживания Ссылка Кластеризация сайтов в интернете За 2014 год 12 кластеров Ссылка Примеры выделения сообществ – ВК 45

Литература

  1. http://igraph.org/c/#docs – описание методов
  2. http://www.dialog-21.ru/digests/dialog2010/materials/html/78.htm?
  3. http://habrahabr.ru/company/darudar/blog/139911/
  4. http://postnauka.ru/longreads/20259http://www.machinelearning.ru/wiki/imag es/6/60/2015_417_SlavnovKA.pdf
  5. http://www.hse.ru/edu/vkr/?id=125365020
  6. http://www.hse.ru/edu/vkr/?id=153012854
  7. http://dix.ontos.ru/dix/bookmarklet.jsp
  8. http://habrahabr.ru/company/dca/blog/264811/
  9. http://modis.ispras.ru/wp-content/uploads/2010/10/comdet16.pdf 10.http://www.machinelearning.ru/wiki/images/7/76/Pres_for_IPPI_report.pdf 11.https://en.wikipedia.org/wiki/Centrality 12.http://modis.ispras.ru/wp-content/uploads/2010/10/comdet16.pdf 13.http://habrahabr.ru/company/dca/blog/264811/

Инструменты • Ant Design of React • Apache Giraph • graph-tool • Gephi • GraphLab Create • networkX • Алгоритм марковскойкластеризации (MCL) http://micans.org/mcl/index.html • igraph

You can’t perform that action at this time.