---
title: Анализ сетей
date: 2012-06-03T10:00
tags: [университет]
---

Графы это математическая формализация сетей. Поскольку я до дипломной работы перерыл много материалов, то тут буду собирать интересные доклады по этой общей теме. Эта статья составлена на основе курсов лекций [Networked Life](https://class.coursera.org/networks-2012-001/class/index) (Michael Kearns, Pennsylvania) и [Social Network Analysis](https://class.coursera.org/sna-2012-001/lecture/index) (Lada Adamic, Michigan) в Coursera.

Интереснейшие проблемы анализа сетей это **поиск кратчайшего пути**, **визуализация** и **заражение**

## Терминология

Наука изучения сетей междисциплинарная, поэтому и термины могут применяться разные.

|   |   |   |
|---|---|---|
|Точки|Линии|Область применения|
|Vertices (вершины)|Edges, arcs (рёбра)|Математика|
|Nodes (узлы)|Links (связи)|Инфотехнологии|
|Sites|Bonds|Физика|
|Actors|Ties, relations|Социология|

## Программные инструменты 

[Gephi](https://gephi.org/), [Netlogo](http://ccl.northwestern.edu/netlogo/index.shtml), [iGraph](http://igraph.sourceforge.net/), [Pajek](http://vlado.fmf.uni-lj.si/pub/networks/pajek/), [UCINet](https://sites.google.com/site/ucinetsoftware/home), [NodeXL](http://nodexl.codeplex.com/), [NetworkX](http://networkx.lanl.gov/), [SoNIA](http://www.stanford.edu/group/sonia/).

## Компоненты

В зависимости от того, как моделируется сеть (направленно или нет), зависят и некоторые её характеристики. Можно говорить о **сильно связанном** компоненте направленной сети, если из каждой его вершины можно попасть в любую другую. Большие естественные сети рано или поздно образуют **гигантский компонент**

![](../img/Pasted%20image%2020241020180840.png)

![](../img/Pasted%20image%2020241020180852.png)

## Особенности естественных сетей

Кратчайший путь определяется только если сеть не имеет изолированных узлов (disconnected component). Проблема выражается в ограниченности видимости конкретного узла. Так, в социальных сетях человек ограничен знанием о своём окружении, поэтому он не видит всей картины, связывающей его с произвольным узлом остальной сети (**small world effect**).

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

Естественные сети (в отличие от скажем случайных сетей),  стремятся к минимизации кратчайшего пути и по мере роста числа узлов, среднее кратчайшее расстояние (**диаметра сети**) асимптотически **уменьшается**. Социальные сети на основе эмпирических исследований Траверса и Милграма (1969 г.), Лешковеца и Горвица (2008 г.) и Бэкстрома и др. (2012 г.) показывает что значение диаметра в районе 5.

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

Наконец третье свойство - длинный хвост в **распределении степеней вершин** (heavy tailed degree distribution, степенной закон, принцип Парето 20/80). Это проявляется в том, что в обществе есть редкие вершины, число связей у которых очень велико, а в среднем по сети "популярность" падает довольно резко и нелинейно

Заражение (перколяция, диффузия) в сетях может происходить необычайно быстро из-за **пограничного свойства** как структуры сети, так и свойств заражения (tipping point, threshold). Если взять случайно сгенерированный граф у которого средняя степень узла равна 4, то легко увидеть что при 100% степени заражения, порядка 90% узлов будет покрыто.

`\[e=d*N/2\]`

e - число рёбер  
d - средняя степень узла  
N - число узлов в сети

Число рёбер для ненаправленного графа

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

## Скопления  

Для любой вершины можно определить _степень скопления_ (clustering coefficient) как показатель взаимосвязанности её соседей. Если все вершины связаны, то такой подграф называется клик (clique) и имеет коэффицент 1. Теперь для расчёта коэффициента среднего скопления, достаточно просчитать коэффициент для всех вершин и взять среднее значение

`\[C(u) = \frac{k+m}{k(k-1) /2 }\]`

C(u) - коэффициент кластеризации вершины u  
k - степень вершины  
m - число связей "между друзьями"

Коэффициент кластеризации вершины

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

`\[p = \frac{E}{N(N-1)/2}\]`

p - плотность рёбер в графе  
E - число рёбер в графе  
N - число вершин

Плотность рёбер

Для естественных сетей C(u) значительно больше p

### Моделирование скоплений

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

`\[y \sim p + (\frac{x}{N})^a\]`

y - вероятность создания новой связи между двумя вершинами  
p - вероятность случайной связи  
x - число общих друзей между вершинами  
N - размер всей сети

alpha-модель

![](../img/Pasted%20image%2020241020180906.png)

![](../img/Pasted%20image%2020241020180911.png)

![](../img/Pasted%20image%2020241020180915.png)

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

### Предпочтительное связывание

Описанные модели формирование скоплений тем не менее не объясняют почему распределение степеней вершин подчиняется степенному закону. 

`\[p(k) = Сk^{-\alpha}\]`

p(k) - вероятность вершины иметь степень k  
α, C - константы

Распределение со степенным законом

Предпочтительное связывание (_preferrential attachment, cumulative advantage_) объясняет неравенства возникающие в сетях, в том числе почему богатые становятся богаче, почему у поп-звёзд так много поклонников. В целом это сводится к тому, что чем больше у вершины есть ресурсов, тем легче ей получить ещё - через дополнительную рекомендацию друзей, предубеждение, славу и тп.

![](../img/Pasted%20image%2020241020180925.png)
![](../img/Pasted%20image%2020241020180930.png)

![](../img/Pasted%20image%2020241020180934.png)

### Навигация

Для понимания естественных сетей, стоит поговорить о процессах навигации и распространении сигналов. Они должы учитывать как структурные особенности сети, так и алгоритм выбора оптимального пути.

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

`\[p(d) \propto (1/d)^r\]`

p - вероятность новой связи между двумя вершинами  
d - расстояние между вершинами  
r>=0 - степень, влияющая на поведение

При очень больших r, передача сообщений происходит только локально и кратчайшие расстояния до дальних вершин могут даже не существовать.  

Приуменьшении r, падает сопротивление от расстояния, но увеличивается _алгоритмическая_ сложность поиска кратчайшего расстояния

## Важные вершины

До этого всё что касалось характеристик, описывало всю сеть целиком, но единичные вершины также критично важны.

### Pagerank

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

```
\[R(p) = \sum_{q \in POINTS(p)} \frac {R(q)}{out(q)}\]
```

R(p) - pagerank вершины p  
R(q) - pagerank вершины q которая ссылается на p (принадлежит множеству POINTS)  
out(q) - число исходящих ссылок из q  

page rank

Вот например как выглядит расчёт для некоторых вершин..

![](../img/Pasted%20image%2020241020180945.png)

## Рациональные процессы в сетях

### Модель сегрегации Шеллинга

Шеллинг показал, что если вершины могут выступать как люди и изменять своё местоположение в матричной сети, переезжая в ближаюшую не занятую ячейку, то при случайном начальном расположении и при требовании вершины к своим соседям в 40% похожести, возникают сегрегированные области, подобно гетто-районам расовой сегрегации.

См. [эмулятор](http://ccl.northwestern.edu/netlogo/models/run.cgi?Segregation.734.460).

![](../img/Pasted%20image%2020241020180954.png)
Начальное случайное положение

![](../img/Pasted%20image%2020241020181002.png)
Сегрегация при 40 процентах требований достигает 80 процентов похожести

## Related

- [Web-службы и архитектуры приложений для интернета](/ru/blog/универ/web-sluzhby-i-arhitektury-prilozheniy-dlya-interneta/)
- [Алгоритмы и структуры данных](/ru/blog/универ/algoritmy-i-struktury-dannyh/)
- [Введение в инфосистемы и UML](/ru/blog/универ/vvedenie-v-infosistemy-i-uml/)