Методы машинного обучения

 Шестаков Андрей (avshestakov@hse.ru)


Введение в анализ сетевых структур: (Social) Network Analysis

Сети везде

Социальные сети

Блого сфера

Обмен ресурсами

Обмен ресурсами

Дороги

Анализ социальные сетей

Мем: 6 рукопожатий

Почему сети интересно изучать?

  • Неслучайные и нерегулярные
  • Безмасштабность (scale-free)
  • Общие свойства в разных дисциплинах

Графы

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

Графом $\mathcal{G}$ называется пара множеств $\mathcal{G} = (V, E)$, где $V$ содержит в себе множество вершин (узлов, vertices, nodes), а $E$ содержит множество ребер (связей, edges, links).
Величины $n = |V|$ и $m = |E|$ называют порядком (order of graph) и размером (size of graph) графа.

Ребра, ориентированность, соседи

  • Ребро между вершинами $(v_i, v_j)$ обозначают $e_{ij}$. В нериентированном графе $e_{ij} = e_{ji}$ $\forall i,j$.
  • В ориенированном графе ребро $e_{ij} = (v_i, v_j)$ показывает направление связи от $v_i$ к $v_j$.
  • Иногда ребрам в графе ставится в соответствие некоторое числовое значение $w_{ij} \in \mathbb{R}$, которое выражает силу связи между вершинами. Эти значения называют весами ребер, а графы с весами называют взвешенными.
  • Вершины $v_i$ и $v_j$ называют соседями если ребро $(v_i, v_j) \in E$. Множество смежных с $v_i$ вершин образуют множество соседей $N(v_i)$. Степень вершины - количество соседей $k_i = |N(v_i)|$

Граф сверху:

  • Неориентированный
  • Невзвешенный
  • Cвязный
  • Подграф $\mathcal{G'}$ состоящий из вершин $v_1, \dots, v_5$ - полный подграф графа $\mathcal{G}$
  • $V = \{v_1, \dots, v_{10} \}, |V| = 10$
  • $E = \{(v_1, v_2), (v_1, v_3), \dots, (v_9, v_{10}) \}, |E| = ?$
  • $N(v_2) = \{v_1, v_3, v_4, v_5, v_6, v_8\}$
  • Степень вершины $v_2$: $k_2 = |N(v_2)| = 6$
  • Расстояние между $v_5$ и $v_{7} = ?$

Расстояние на графах

  • Маршрутом из вершины $v$ в вершину $u$ называется конечная последовательность $(v, v_1), (v_1, v_2), \dots , (v_k, u)$. Если в последовательности нет повторяющихся ребер, то это путь (цепь).
  • Если между $v$ и $u$ существует путь то эти вершины называются связанными. Граф называется связным, если для любой пары вершин найдется путь, иначе граф является несвязным.
  • Длинной пути называется число ребер, из которых он состоит, а расстоянием называется длина кратчайшего пути между ними. Диаметр графа равен максимальному расстоянию в нем.

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

Форматов представления графов довольно много. Все форматы определяют топологию сети (т.е. её структуру), но некоторые могут не сохранять в себе все данные связанные с элементами сети (множество атрибутов ребер и вершин, динамические характеристики, рекоментованную прорисовку и тп).

Ниже мы рассмотрим наиболее распространенные форматы.

Матрица смежности

Матрица связанности, Incidence matrix, Association matrix.

Матрица связанности - это квадратная матрица размера $n \times n$. Обозначим ее буквой $\mathbf{A}$

В невзвешенном графе:
$\mathbf{A_{ij}} = 1$, если в графе есть ребро между вершинами $v_i$ и $v_j$
$\mathbf{A_{ij}} = 0$, иначе

Во взвешенном графе:
$\mathbf{A_{ij}} = w_{ij}$, если в графе есть ребро между вершинами $v_i$ и $v_j$
$\mathbf{A_{ij}} = 0$, иначе

Для графа выше матрица смежности имеет следующий вид:

Преимущества:

  • Наглядность
  • Удобно производить математические операции

Недостатки:

  • Передает только структурную информацию (+ веса)
  • При неправильном хранении может занимать много места в памяти и на жестком диске

Список ребер

Edge list

Другой очевидный и популярный формат.

На каждой строчке указываются идентификаторы смежных вершин (числовые признаки этих связей - веса)

1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6 7 8 7 9 8 9 8 10 9 10 3 7 2 8 6 10

Преимущества:

  • Достаточно легкий формат

Недостатки:

  • Передает структурную информацию
  • Может передавать несколько признаков связей (несколько весов)

Список смежности

Adjacency list

Один из самых экономичных форматов.

Каждая строчке соответствует вершине. Через запятую указываются идентификаторы смежных с ней вершин

2, 3, 4, 5, 6 1, 3, 4, 5, 6, 8 1, 2, 4, 5, 6, 7 1, 2, 3, 5, 6 1, 2, 3, 4, 6 1, 2, 3, 4, 5, 10 3, 8, 9 2, 7, 9, 10 7, 8, 10 6, 8, 9

Преимущества:

  • Достаточно легкий формат

Недостатки:

  • Передает только структурную информацию

Pajek формат

Данный формат используется в программе для анализа больших сетей - Pajek. По сути это немного расширенный формат списка ребер (или списка смежности).

*Vertices 10 1 "v_1" 2 "v_2" 3 "v_3" 4 "v_4" 5 "v_5" 6 "v_6" 7 "v_7" 8 "v_8" 9 "v_9" 10 "v_10" *Edges 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6 7 8 7 9 8 9 8 10 9 10 3 7 2 8 6 10

Преимущества:

  • Поддерживаются комментарии
  • Оптимальный формат хранения информации о ребрах и вершинах

Недостатки:

  • ...

GraphML

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

v_1 v_2 v_3 v_4 v_5 v_6 .... ...

Преимущества:

  • Возможно передать всю информацию о графе, его структуре и характеристиках элементов

Недостатки:

  • Много весит...

GML

GML (Graph Modelling Language) - так же гибкий формат представления графов. Однако он является чуть более "читабельным", чем GraphML

Creator "igraph version 0.7.1 YYYY-MM-DD" Version 1 graph [ directed 0 node [ id 0 label "v_1" ] node [ id 1 label "v_2" ] node [ id 2 label "v_3" ] ... edge [ source 1 target 0 ] edge [ source 2 target 0 ] ... ]

Преимущества:

  • Возможно передать всю информацию о графе, его структуре и характеристиках элементов

Недостатки:

  • Много весит...

Инструменты и библиотеки по работе с сетями

Gephi

Gephi - это очень крутой, недавно возрожденный, кнопочный, написанный на Java, open-source проект для анализа и визуализации сетей.
Вместо тысячи слов:

In [3]:
from IPython.display import VimeoVideo
VimeoVideo('9726202')
Out[3]:

Библиотеки для работы с сетями на Python

В языке python чаще всего используются следующие библиотеки:

  • NetworkX - подходит для работы с небольшими сетями
  • graph-tool - Библиотека для работы с большими сетями при поддержке OpenMP и Boost c API для python
  • SNAP - Библиотека от Stanford для работы с большими сетями с API для python
  • igraph - Библиотека для работы с большими сетями c API для python и R