четверг, 22 февраля 2018 г.

В чем хранить сети? Немного о форматах сетевых данных

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

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

Матрица смежности -- один их самых распространенных форматов для  представления сетей, это классика жанра. Сети из n узлов - это матрица из n рядов и n столбцов (матрица n x n). Каждая из клеток матрицы соответствует связи. Например, клетка матрицы [1, 5] соответствует связи от вершины 1 к вершине 5. Диагонали матриц ([1,1]; [2,2]; и так далее) почти всегда нули, потому что нельзя дружить самому с собой. 


Матрица смежностей. Источник

Для невзвешенных графов значения в клетках могут быть 0 или 1. 0 – когда связи нет и 1 – когда есть.  Например, если мы собираем информацию о том, знакомы люди или нет (невзвешенная сеть), то факт того, что два человека знают друг друга, будет кодироваться как 1.  Если же граф взвешенный, то в клетку будет указываться вес ребра. А вот если социальная сеть отражает то, сколько один банк должен другому, то можно проявить фантазию и использовать объем долга как вес ребра.
Основное достоинство такой матрицы смежностей заключается в ее простоте и наглядности. Легко производить матричные вычисления. Практически все программы и пакеты по сетевому анализу и визуализации поддерживают загрузку данных в виде матрицы смежностей.
Недостаток в том, что если кодируются большие данные и огромное количество связей, то матрицы могут занимать много памяти.
Матрицы смежностей используются в UCINET и ORA

Еще один очень распространенный формат сетевых данных - это список ребер. Это матрица размера e x 2, где e – это количество ребер. Ребро кодируется следующим образом – указывается отправитель связи и ее получатель. Например, "Вася – Петя" – это указание, что Петя и Вася знают друг друга.


Список ребер. Источник

Если есть данные о весе связей, то в матрицу можно добавить еще один столбец и занести туда данные о весе связи. Если вернемся к сети наших банков, то запись "Банк А – Банк Б – 100" означает, что связь между банками А и Б весит 100, то есть Банк А взял 100 условных единиц у Банка Б. 
Как и в случае с матрицей смежностей, ключевым достоинством списка ребер является его простота и легкость. Из недостатков – возможность хранения исключительно данных о структуре сети, но не о характеристиках вершин. Для кодирования вершин понадобится еще одна табличка. И еще, сохраняя данные в формате списка ребер можно очень легко потерять изолированные вершины, которые ни с кем не связаны.
Список ребер используется в Gephi, одной из самый популярных программ для анализа сетей. Список ребер также можно подгрузить в Pajek

Список смежности – это таблица из n строк (для каждой из вершин), и в строке перечисляются соседи данной вершины. Например, если Катя дружит с Васей, Наташей и Петей, то строка будет выглядеть следующим образом – "Катя – Вася, Наташа, Петя".


Список смежности. Источник

Список смежности позволяет кодировать изолированные вершины, но вот кодировать данные о весе связей в нем нельзя. Поэтому указать, сколько какой банк кому должен, не получится.

4.   GML
Graph Modeling Language – значительно более сложный формат представления данных, чем все предыдущие. Основан на языке разметки XML и позволяет кодировать тэгами характеристики и узлов и ребер в одном файле.


Пример записи в GML формате. Перечислены все вершины и связи между ними с указанием характеристик. Источник

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

Вполне вероятно, что с постепенным, но неизбежным переходом социологов-количественников в R и Python, "простые форматы" будут постепенно уходить в прошлое, ведь в сетевых пакетах для Python и R (igraph, graphtool, networkx для Python; igraph, sna, networks и другие для R) можно прочитать графы в любом из форматов. Ну, а пока популярными и востребованными инструментами для анализа сетей остаются  Gephi, ORA и Pajek, приходится разбираться. 

***

Что еще можно почитать на связанные темы:
- О том, как начать работать с сетями
- Что и как делать с сетями в Питоне
- Как анализировать данные в R.

2 комментария:

  1. а Data Language формат?

    ОтветитьУдалить
  2. Большое спасибо за Ваш блог и просветительские усилия! Меня он сподвиг взяться за изучение языка R, а в качестве первого учебника я взял книгу "Анализ сетей в среде R" Д.Люка
    И позвольте мне, с позиции новичка, подметить, что про информацию про форматы хранения и меры анализа легко найти. Также, не представляет труда открыть книгу с примерами и опробовать функции из пакетов, но все примеры построены на готовых модельных данных. Поэтому 15 минут изучаешь параметры функции на модельных данных, а оставшийся день уходит на то, чтобы подготовить свои данные (то вершины без имени, то веса теряются).

    Вот, например, есть 3х1000 таблица {документы, авторы, гранты}, это 1000 статей и в каждой разное количество авторов (total = 1200). Как из такой таблицы сделать матрицу смежности для авторов или лучше, конечно, список ребер с весами? Это ж самая необходимая задача... вот таких рецептов очень не хватает.
    Сможете мне любезно порекомендовать источник?

    ОтветитьУдалить