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

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

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

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

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

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

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

Основное достоинство такой матрицы смежностей заключается в ее простоте и наглядности. Легко производить матричные вычисления. Практически все программы и пакеты по сетевому анализу и визуализации поддерживают загрузку данных в виде матрицы смежностей.

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

Матрицы смежностей используются в UCINET и ORA. 

2.   Список ребер

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

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

Если есть данные о весе связей, то в матрицу можно добавить еще один столбец и занести туда данные о весе связи. Если вернемся к сети наших банков, то запись "Банк А – Банк Б – 100" означает, что связь между банками А и Б весит 100, то есть Банк А взял 100 условных единиц у Банка Б. 

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

Список ребер используется в Gephi, одной из самый популярных программ для анализа сетей. Список ребер также можно подгрузить в Pajek. 

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

Список смежности – это таблица из 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.