Gostaria de saber se alguém poderia sugerir quais são os bons pontos de partida quando se trata de realizar a detecção / particionamento / agrupamento / agrupamento de gráficos da comunidade em um gráfico que tenha arestas ponderadas e não direcionadas . O gráfico em questão possui aproximadamente 3 milhões de arestas e cada aresta expressa o grau de semelhança entre os dois vértices que ele conecta. Em particular, neste conjunto de dados, as arestas são indivíduos e os vértices são uma medida da semelhança de seu comportamento observado.
No passado, segui uma sugestão que cheguei aqui no stats.stackexchange.com e usei a implementação da igraph do cluster de modularidade de Newman e fiquei satisfeito com os resultados, mas isso ocorreu em um conjunto de dados não ponderado.
Há algum algoritmo específico que eu deveria estar olhando?
fonte
Eu sei que o Gephi pode processar gráficos ponderados não direcionados, mas me lembro que ele deve ser armazenado no GDF , que é bem próximo do CSV, ou do Ucinet DL . Esteja ciente de que ainda é uma versão alfa. Agora, sobre como agrupar seu gráfico, o Gephi parece não ter pipelines de cluster, exceto o algoritmo MCL que agora está disponível na versão mais recente. Havia um Google Code Project em 2009, o Gephi Network Statistics (apresentando, por exemplo, a métrica de modularidade de Newman), mas não sei se algo foi lançado nessa direção. De qualquer forma, parece permitir algum tipo de cálculo de modularidade / agrupamento, mas veja também a Análise de redes sociais usando R e Gephi ePreparação de dados para análise de redes sociais usando R e Gephi (Muito obrigado a @Tal).
Se você está acostumado a Python, vale a pena tentar o NetworkX (aqui está um exemplo de um gráfico ponderado com o código correspondente). Então você tem muitas maneiras de realizar sua análise.
Você também deve consultar o INSNA - Software de Análise de Rede Social ou a página de Tim Evans sobre Redes e Complexidade Complexas .
fonte
O Gephi implementa o método da Louvain Modularity: http://wiki.gephi.org/index.php/Modularity
Felicidades
fonte
O algoritmo de modularidade de Louvain está disponível em C ++: https://sites.google.com/site/findcommunities/
Ele lida com redes ponderadas de milhões de nós e bordas e demonstrou ser muito mais rápido que o algoritmo de Newman.
fonte
Se você estiver usando python e tiver criado um gráfico ponderado usando o NetworkX , poderá usar python-louvain para clustering. Onde G é um gráfico ponderado:
fonte
Acabei de encontrar o pacote tnet para R. O criador parece estar pesquisando sobre a descoberta da comunidade em gráficos ponderados e bipartidos (dois modos).
http://opsahl.co.uk/tnet/content/view/15/27/
Ainda não o uso.
fonte
O SLPA (agora chamado GANXiS) é um algoritmo rápido capaz de detectar comunidades disjuntas e sobrepostas em redes sociais (não direcionadas / direcionadas e não ponderadas / ponderadas). É mostrado que o algoritmo produz resultados significativos nas redes sociais e de genes do mundo real. É um dos mais avançados. Está disponível em
https://sites.google.com/site/communitydetectionslpa/
Veja uma boa revisão arxiv.org/abs/1110.5813 para obter mais informações
fonte
Eu tenho uma implementação java para uma rede não sobreposta, ponderada / não ponderada que provavelmente poderia lidar com 3 milhões de nós (eu testei para um conjunto de dados de um milhão de nós). No entanto, funciona como k-means e precisa que o número de partições seja detectado como entrada (k em kmeans). Você pode encontrar mais informações aqui , e aqui está o código , no github
Felicidades,
fonte