Como calcular medidas de centralidade em uma rede de 4 milhões de bordas usando R?

9

Eu tenho um arquivo CSV com 4 milhões de bordas de uma rede direcionada representando pessoas se comunicando (por exemplo, John envia uma mensagem para Mary, Mary envia uma mensagem para Ann, John envia outra mensagem para Mary etc.). Eu gostaria de fazer duas coisas:

  1. Encontre medidas de centralidade de grau, entre e (talvez) autovetor para cada pessoa.

  2. Obtenha uma visualização da rede.

Eu gostaria de fazer isso na linha de comando em um servidor Linux, pois meu laptop não tem muita energia. Eu tenho R instalado nesse servidor e na biblioteca statnet. Encontrei este post de 2009 de alguém mais competente do que eu tentando fazer a mesma coisa e tendo problemas com ela. Então, eu queria saber se mais alguém tem alguma dica sobre como fazer isso, de preferência me dando um passo a passo, pois só sei carregar o arquivo CSV e nada mais.

Só para você ter uma idéia, é assim que meu arquivo CSV se parece:

$ head comments.csv
    "src","dest"
    "6493","139"
    "406705","369798"
$ wc -l comments.csv 
4210369 comments.csv
amh
fonte
para algumas dessas medidas, se o R pode lidar com isso ou observar depende de quantas pessoas separadas (nós) a rede possui. R pode não ser necessariamente a melhor ferramenta para os aspectos computacionais. Há um cara com o sobrenome Leskovec que costumava estar na Carnegie Mellon - eu acho que quando estudante - que fazia muitas coisas com estatísticas descritivas em grandes gráficos. Existem muitos utilitários por aí para "visualizar" gráficos, mas principalmente descobri que são muito difíceis de interpretar ou fazer muito sentido. Representar graficamente apenas as distribuições de graus pode ser o primeiro começo.
cardeal
Mesmo traçando 4 milhões de pontos pode demorar um pouco ...
Wok
@wok, nah. Pedaço de bolo nos computadores de hoje. De qualquer forma, você sempre pode despejar em um PNG primeiro e isso provavelmente será bom o suficiente para a distribuição de graus. O gráfico do OP realmente não é tão grande assim.
cardeal

Respostas:

7

O que você tem é uma lista de borda, que pode ser convertida em um objeto de rede usando a biblioteca de rede. Aqui está um exemplo usando dados fictícios.

library(network)

src <- c("A", "B", "C", "D", "E", "B", "A", "F")
dst <- c("B", "E", "A", "B", "B", "A", "F", "A")

edges <- cbind(src, dst)
Net <- as.network(edges, matrix.type = "edgelist")

summary(Net)
plot(Net)

No entanto, é necessário um aviso: você tem uma rede muito grande e não tenho certeza de que uma trama seja tão informativa. Provavelmente parecerá um grande novelo de lã. Também não tenho certeza de como essas bibliotecas lidam com conjuntos de dados tão grandes. Sugiro que você dê uma olhada na documentação das bibliotecas de rede, statnet e ergm. O Journal of Statistical Software (v24 / 3) oferece vários artigos que cobrem essas bibliotecas. O problema pode ser encontrado aqui:

http://www.jstatsoft.org/v24

Jason Morgan
fonte
11
Lembro-me vagamente do mapa-múndi da rede do Facebook, feito em R. Acho que o autor descreveu seu processo com mais detalhes em seu blog. Suponho que o uso dessa abordagem geraria um mapa informativo, mesmo com 4 milhões de nós.
dever-Jessen
Desculpas pela pergunta ingênua, mas como faço para converter uma tabela no que você tem como srce dst. Isto é o que eu normalmente faço para carregar o arquivo (agora um arquivo delimitado por tabulação): el <- read.csv("comment-net/comments-ouids.tsv",header=T,sep="\t")
AMH
O read.csv () deve produzir um data.frame. o as.network () pode ler isso diretamente ou você pode precisar fazer o as.matrix (el).
Jason Morgan
Sou bastante cético quanto a essas bibliotecas poderem fazer muito com um gráfico de milhões de nós. Você realmente os usou com conjuntos de dados comparáveis?
Szabolcs
O pôster estava se referindo a uma rede com 4 milhões de bordas , não nós. Eu usei a statnetfamília de bibliotecas em uma rede não direcionada de mais de 3500 nós (~ 8 milhões de arestas possíveis). Isso foi possível, principalmente quando o objetivo era apenas calcular as estatísticas da rede. Até estimei ERGMs em redes desse tamanho. Mas seu ponto de vista é bem aceito; Duvido que redes de milhões de nós possam ser facilmente analisadas.
Jason Morgan
3

Eu não acho que R seja a primeira escolha aqui (talvez eu esteja errado). Você precisará de grandes matrizes aqui para indexar e preparar seus arquivos de rede no formato de dados apropriado. Primeiramente, tentarei usar a biblioteca SNAP de Jure (Rob o mencionou no post acima) ; está escrito em C ++ e funciona muito bem em grandes redes.

Andrej
fonte
Obrigado por mencionar o SNAP. Eu estou olhando para isso. Você já usou? A amostra de centralidade que a acompanha parece próxima do que eu quero. Eu tentei modificá-lo para que ele funcionasse com meus dados de gráficos multi-direcionados, mas não conseguiu compilar. Eu não tenho certeza se ele é apropriado para fazer uma pergunta sobre isso aqui, para que eu possa criar uma nova Q.
AMH
11
@andresmh, você pode tentar reduzir seu gráfico para ter uma única observação por par direcionado primeiro. Para o material de autovalor, seus dados provavelmente são semelhantes ou equivalentes a uma caminhada aleatória ponderada no gráfico. Não tenho certeza se o SNAP suporta isso, mas é provável que sim. Se tudo mais falhar, você pode enviar um e-mail muito específico para Jure. Ele é um cara muito legal, então eu não ficaria surpreso se ele desse alguma orientação rápida.
cardeal
@ cardinal: Encontrei um código de amostra no SNAP que faz exatamente o que eu quero, mas para um gráfico não direcionado. Eu acho que meu gráfico é o que os documentos SNAP chamam de "multi-gráfico direcionado". Então mudei apenas uma linha centrality.cppde TUNGraphpara TNEGraph(consulte a linha 24 do pastebin.com/GHUquJvT ). Não está mais compilando. Eu suspeito que requer um tipo diferente de nó? O erro que eu recebo é: centrality.cpp:24: error: conversion from ‘TUNGraph::TNodeI’ to non-scalar type ‘TNEGraph::TNodeI’ requested(ver erro completo em pastebin.com/86mCbByG )
AMH
3

Gephi ( http://gephi.org/ ) pode ser uma maneira fácil de explorar os dados. Você quase certamente pode visualizá-lo e executar alguns cálculos (embora eu não o tenha usado há algum tempo, não lembro de todas as funções).

celenius
fonte
3

De experiências anteriores com uma rede de 7 milhões de nós, acho que visualizar sua rede completa fornecerá uma imagem incompreensível. Eu poderia sugerir visualizações diferentes usando subconjuntos de seus dados, como usar apenas os 10 nós principais com mais links de entrada ou saída. A segunda sugestão de Celenius sobre o uso de gephi.

Zubin
fonte
@andresmh, Maslov e Sneppen ( Science , 2002) têm uma visualização que pode ser útil nesse contexto. Pesquisando por meio de citações recentes relacionadas a estatísticas / comp-sci deste trabalho, encontrei isso também. Aqui pode estar outro trabalho relacionado.
cardeal
1

Se você está preocupado com o tamanho da rede, pode tentar o igraphpacote em R. Ou até o networkxpacote para Python

fioghual
fonte
1

Você suspeita que a rede tenha um pequeno número de componentes conectados muito grandes? Caso contrário, você pode decompor em componentes distintos, o que tornará muito mais fácil calcular medidas de centralidade.

Michael Bishop
fonte
+1 a isso - se é um componente totalmente conectado, isso é uma coisa, mas se você pode decompor a rede, você tem dados menores e, na verdade, várias redes independentes que podem ser analisadas em paralelo.
Fomite 9/10/11
1

Existem vários pacotes de software R que se pode usar, incluindo "sna" e "network". Uma coisa em que eu não necessariamente confiaria se você estivesse tendo problemas de desempenho com o sna é o NetworkX. Eu amo o NetworkX até a morte, e o uso durante a maior parte da minha análise, mas o NetworkX tem muito orgulho de ser uma implementação principalmente puramente pitônica. Ele não explora bem o código pré-compilado rapidamente, e o sna geralmente ultrapassa o NetworkX por uma margem considerável.

Fomite
fonte