R, OpenOffice, языки описания графов и социальные сети

В последнее время у нас накопилось много данных о структуре социальных сетей. Во всех случаях эти массивы достаточно велики и требуют машинной обработки. В этом посте я хочу поделиться сугубо технологическими приёмами работы с массивами сетевых данных.



1. Предварительные сведения
1.1. Для статистического анализа социальных сетей есть много разных программ. Мы пользуемся, в основном, R и — на подготовительном этапе — Open Office’ом. В R эти вычисления реализованы в пакете sna (Social Network Analysis), подробнее о котором можно почитать здесь. После того, как он загружен и установлен, подключение его в командной строке R выполняется рутинной командой

> library('sna')

1.2. Одной из красивостей, из предоставляемых пакетом sna, является возможность нарисовать свою сеть. Предположим, что наши данные содержатся в матрице network (о том, как её создать, см. ниже).

> gplot(network)

Если нужно сохранить эту картинку, то процедура такова

> png('network.png')
> gplot(network)
> dev.off()

Подробнее о команде png() см. во встроенной помощи R

> help('png')

1.3. Ввод готовой матрицы смежности (adjacency matrix) или социоматрицы из табличного редактора (напр. Calc’a или Excel’я) в R не отличается от рутинных процедур

а) сначала нужно выделить и скопировать в буфер саму матрицу;
б) ввести в командной строке R

> network=read.table('clipboard')

(важно, чтобы в заголовках строк и столбцов не было кириллицы).

2. Формирование массива сетевых данных.
2.1. Существует, по крайней мере, два способа описания сетевых данных: матрица смежности и текстовое описание (его разновидностями являются языки gdl и dgl).

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

В связи с этим я попросил нашего программиста Сашу Остапенко написать макрос, который бы переводил описание сети с gdl в матрицу смежности.

*************************
REM ***** BASIC *****

Sub Main

Dim i As Integer, j As Integer, k As Integer, l As Integer, n As Integer, m As Integer
Dim nodes(1) As String, edges(1,1) As Integer
Dim r As Integer, t As Integer
Dim Doc As Object, Sheet As Object, Cell As Object
Dim str As String, strn(1) As String

Doc=StarDesktop.CurrentComponent
Sheet=Doc.Sheets(0)
Cell=Sheet.getCellByPosition(0,0)
str=Cell.getString

i=0 : r=0

Do While Left(str,1)<>"}"
If Left(str,5)="node:" Then
r=r+1
End If
i=i+1
Cell=Sheet.getCellByPosition(0,i)
str=Cell.getString
Loop

t=i

ReDim nodes(r-1)
ReDim edges(r-1,r-1)

For i=0 to r-1
For j=0 to r-1
edges(i,j)=0
Next j
Next i

j=0

For i=0 To t
Cell=Sheet.getCellByPosition(0,i)
str=Cell.getString
If Left(str,5)="node:" Then
k=InStr(str,chr(34))
l=InStr(k+1,str,chr(34))
nodes(j)=Mid(str,k+1,l-k-1)
j=j+1
End If
Next i

j=0

For i=0 To t
Cell=Sheet.getCellByPosition(0,i)
str=Cell.getString
If Left(str,5)="edge:" Then
k=InStr(str,"source: ")
l=InStr(str,"target: ")
strn(0)=Mid(str,k+9,InStr(k+9,str,chr(34))-k-9)
strn(1)=Mid(str,l+9,InStr(l+9,str,chr(34))-l-9)
For j=0 to r-1
Select Case nodes(j)
Case strn(0): m=j
Case strn(1): n=j
End Select
Next j

edges(m,n)=1
' edges(n,m)=1
End If

Next i

k=0 : l=0
Sheet = Doc.createInstance("com.sun.star.sheet.Spreadsheet")
Doc.Sheets.insertByName("Матрица смежности", Sheet)
Sheet = Doc.Sheets.getByName("Матрица смежности")

For i=0 to r-1
Cell=Sheet.getCellByPosition(i+1,0)
Cell.String = nodes(i)
Cell=Sheet.getCellByPosition(0,i+1)
Cell.String = nodes(i)
Next i

For i=0 to r-1
For j=0 to r-1
Cell=Sheet.getCellByPosition(i+1,j+1)
Cell.Value=edges(i,j)
Next j
Next i

MsgBox "Готово! Автор макроса Александр Остапенко, 2009"
End Sub
*************************

Примечание: этот макрос даёт на выходе матрицу смежности ориентированного графа. Если же требуется граф неориентированный, то нужно раскомментировать строчку

edges(n,m)=1

2.2. В отличие от коммерческого языка gdl, описание графа на языке dgl (т. е. файл с расширением .dot) можно напрямую экспортировать в R, для чего в составе пакета sna предусмотрена команда read.dot

>network=read.dot('~/network.dot')