Quais são as diferenças entre os algoritmos de detecção da comunidade no igraph?

Eu tenho uma lista de cerca de 100 objects igraph com um object típico com cerca de 700 vértices e 3500 arestas.

Eu gostaria de identificar grupos de vértices dentro dos quais os laços são mais prováveis. Meu plano é, então, usar um modelo misto para prever quantos vértices dentro dos grupos têm vértices e atributos de grupo.

Algumas pessoas podem querer responder a outros aspectos do meu projeto, o que seria ótimo, mas a coisa na qual estou mais interessado é a informação sobre funções no igraph para agrupar vértices. Eu me deparei com esses algoritmos de detecção da comunidade, mas não tenho certeza de suas vantagens e desvantagens, ou se alguma outra function seria melhor para o meu caso. Eu vi os links aqui também, mas eles não são específicos para o igraph. Obrigada pelo Conselho.

Aqui está um breve resumo sobre os algoritmos de detecção da comunidade atualmente implementados no igraph:

  • edge.betweenness.community é um processo de decomposição hierárquica em que as bordas são removidas na ordem decrescente de suas pontuações de interferência de borda (ou seja, o número de caminhos mais curtos que passam por uma determinada borda). Isso é motivado pelo fato de que as arestas que conectam diferentes grupos têm maior probabilidade de estar contidas em vários caminhos mais curtos, simplesmente porque, em muitos casos, elas são a única opção para ir de um grupo para outro. Este método produz bons resultados, mas é muito lento devido à complexidade computacional dos cálculos de distância entre bordas e porque os valores de interbinding precisam ser recalculados após cada remoção de borda. Seus charts com ~ 700 vértices e ~ 3500 arestas estão em torno do limite superior de tamanho dos charts que são possíveis de serem analisados ​​com essa abordagem. Outra desvantagem é que edge.betweenness.community constrói um dendrograma completo e não lhe dá nenhuma orientação sobre onde cortar o dendrograma para obter os grupos finais, então você terá que usar alguma outra medida para decidir isso (por exemplo, a modularidade pontuação das partições em cada nível do dendrograma).

  • fastgreedy.community é outra abordagem hierárquica, mas é bottom-up em vez de top-down. Ele tenta otimizar uma function de qualidade chamada modularidade de maneira gananciosa. Inicialmente, cada vértice pertence a uma comunidade separada e as comunidades são mescladas iterativamente, de forma que cada fusão é localmente ótima (ou seja, produz o maior aumento no valor atual da modularidade). O algoritmo pára quando não é mais possível aumentar a modularidade, por isso ele fornece um agrupamento e um dendrograma. O método é rápido e é o método que geralmente é tentado como uma primeira aproximação porque não possui parâmetros para ajustar. No entanto, sabe-se que sofre com um limite de resolução, ou seja, comunidades abaixo de um determinado limite de tamanho (dependendo do número de nós e bordas, se bem me lembro) sempre serão mescladas com as comunidades vizinhas.

  • walktrap.community é uma abordagem baseada em passeios randoms. A idéia geral é que, se você fizer caminhadas aleatórias no gráfico, é mais provável que as caminhadas fiquem dentro da mesma comunidade, pois há apenas algumas arestas que levam para fora de uma determinada comunidade. O Walktrap executa caminhadas aleatórias curtas de 3-4-5 etapas (dependendo de um dos seus parâmetros) e usa os resultados dessas caminhadas aleatórias para mesclar comunidades separadas de maneira bottom-up, como fastgreedy.community . Novamente, você pode usar a pontuação de modularidade para selecionar onde cortar o dendrograma. É um pouco mais lento que a rápida abordagem gananciosa, mas também um pouco mais precisa (de acordo com a publicação original).

  • spinglass.community é uma abordagem da física estatística, baseada no chamado modelo de Potts. Neste modelo, cada partícula (ou seja, vértice) pode estar em um dos c estados de spin, e as interações entre as partículas (ou seja, as arestas do grafo) especificam quais pares de vértices prefeririam permanecer no mesmo estado de spin e quais prefere ter estados de spin diferentes. O modelo é então simulado para um determinado número de etapas, e os estados de spin das partículas no final definem as comunidades. As consequências são as seguintes: 1) Nunca haverá mais de c comunidades no final, embora você possa definir c para até 200, o que provavelmente será suficiente para seus propósitos. 2) Pode haver menos de c comunidades no final, como alguns dos estados de spin podem ficar vazios. 3) Não é garantido que os nós em partes completamente remotas (ou descon- contadas) das redes tenham diferentes estados de rotação. É mais provável que isso seja um problema apenas para charts desconectados, então eu não me preocuparia com isso. O método não é particularmente rápido e não determinístico (devido à simulação em si), mas possui um parâmetro de resolução ajustável que determina os tamanhos dos clusters. Uma variante do método spinglass também pode levar em consideração links negativos (ou seja, links cujos endpoints preferem estar em comunidades diferentes).

  • leading.eigenvector.community é uma abordagem hierárquica de cima para baixo que otimiza a function de modularidade novamente. Em cada etapa, o gráfico é dividido em duas partes, de modo que a própria separação produz um aumento significativo na modularidade. A divisão é determinada pela avaliação do principal autovetor da chamada matriz de modularidade, e há também uma condição de parada que impede que grupos fortemente conectados sejam divididos ainda mais. Devido aos cálculos do autovetor envolvido, ele pode não funcionar em charts degenerados onde o solucionador de autovetores ARPACK é instável. Em charts não degenerados, é provável que resulte em um maior escore de modularidade do que o método fast greedy, embora seja um pouco mais lento.

  • label.propagation.community é uma abordagem simples na qual cada nó recebe um dos k labels. O método então procede iterativamente e reatribui labels aos nós de forma que cada nó receba o label mais frequente de seus vizinhos de maneira síncrona. O método pára quando o label de cada nó é um dos labels mais freqüentes em sua vizinhança. É muito rápido, mas produz resultados diferentes com base na configuração inicial (que é decidida aleatoriamente), portanto deve-se executar o método um grande número de vezes (digamos, 1000 vezes para um gráfico) e então criar uma rotulação de consenso, que poderia ser tedioso.

O igraph 0.6 também includeá o algoritmo de detecção da comunidade Infomap, que é baseado em princípios teóricos de informação; ele tenta construir um agrupamento que fornece o menor comprimento de descrição para um passeio random no gráfico, onde o comprimento da descrição é medido pelo número esperado de bits por vértice necessário para codificar o caminho de um passeio random.

De qualquer forma, eu provavelmente fastgreedy.community a fastgreedy.community ou a walktrap.community como uma primeira aproximação e, em seguida, avaliaria outros methods quando, por alguma razão, esses dois não fossem adequados para um problema específico.

Um resumo dos diferentes algoritmos de detecção da comunidade pode ser encontrado aqui: http://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/

Notavelmente, o algoritmo InfoMAP é um recém-chegado recente que pode ser útil (ele também suporta charts direcionados).

Intereting Posts