Algoritmos de agrupamento de gráficos que consideram pesos negativos

8

Eu tenho uma instância de gráfico com arestas direcionadas ponderadas cujos valores podem estar no intervalo [-1,1]. Eu preciso fazer cluster neste gráfico, a fim de descobrir grupos nos quais os vértices estão mais correlacionados.

Procurei vários algoritmos baseados em gráficos de cluster ou de detecção de comunidade, mas a maioria deles não funciona devido aos pesos negativos. Até agora, apliquei o algoritmo spinglass (é chamado na biblioteca igraph , é um algoritmo baseado no modelo de Potts) que parece funcionar com pesos positivos e negativos.

Existem outros algoritmos para fazer cluster ou detecção da comunidade em gráficos com pesos de borda negativos e positivos?

Atualização: os pesos das arestas representam correlações, 1 significa que dois vértices estão fortemente correlacionados, -1 que são inversamente correlacionados e 0 significa que são independentes.

correlation clustering graph-theory networks igraph Ewybe
fonte
O que os pesos representam?
Eliasah 18/10/2015
@eliasah eu fiz uma atualização, a fim de explicar que
Ewybe
Você tentou usar outra balança? Essa pode ser uma boa solução usando um método regular de clustering baseado no algoritmo de centralidade de intermediação, por exemplo.
Eliasah 18/10/2015
@eliasah Escala estes dados imay não ser tão fácil, porque eu estou interessado em preservar o significado da correlação
Ewybe
1
Para o agrupamento, o sinal da correlação é realmente necessário? A correlação inversa também é um relacionamento bastante forte . Veja minha resposta abaixo.
QuIT - Anony-Mousse

Respostas:

2

Você já tentou mapear os valores para [0; 2]?

Então, muitos algoritmos podem funcionar.

Considere, por exemplo, Dijkstra: ele requer pesos de borda não negativos, mas se você souber o mínimo adas bordas, poderá executá-lo x-ae obter o caminho mais curto sem ciclo.

Atualização: para valores de correlação, você pode estar interessado nos valores absolutos abs(x)(que é a força da correlação!) Ou pode dividir o gráfico em dois temporariamente: primeiro cluster apenas nas correlações positivas, depois nas correlações negativas somente se o sinal for importante para o cluster e as abordagens anteriores não funcionarem.

Possui QUIT - Anony-Mousse
fonte
Foi de alguma forma o que sugeri, ele disse que "perderá o significado da correlação". O que você acha disso?
Eliasah 18/10/2015
Com sua descrição atualizada, abs (x) pode funcionar ainda melhor.
Quit - Anony-Mousse
No entanto, acredito que [0,2] é mais representativo. Gráficos Ponderadas geralmente têm importância muito grande sobre estes assuntos para centralidade de computação, distância, diâmetro, etc.
eliasah
1
Isso não significa que você não pode discriminar depois. Você já tentou , os resultados ainda podem ser úteis?
Quit - Anony-Mousse
1
Em seguida, tente a outra abordagem - encontrar cluster positivo e negativo separadamente.
Quit - Anony-Mousse
1

Sim, existe um algoritmo chamado 'Propagação de afinidade' que funciona com pesos negativos; Acredito que isso seja implementado no sklearn (veja a documentação aqui ). Uma referência para o que está acontecendo nos bastidores pode ser encontrada aqui .

Espero que seja isso que você está procurando!

squattyroo
fonte
Eu não conhecia esse algoritmo, parece ser uma boa solução. Eu certamente vou tentar. Obrigado.
Ewybe
Até onde eu sei, o agrupamento por Propagação por Afinidade não será capaz de considerar simultaneamente correlações positivas e negativas enquanto também as separa. A propósito, acho que a tarefa é contraditória.
micans
0

Parece-me que o problema que você descreve é ​​conhecido como o problema de cluster de correlação . Esta informação deve ajudá-lo a encontrar algumas implementações, como:

Nota alguns algoritmos de detecção de comunidade também foram modificados a fim de processar redes assinados, por exemplo Amelio'13 , Sharma'12 , Anchuri'12 , etc. No entanto, eu não poderia encontrar qualquer implementação publicamente disponível.

Vincent Labatut
fonte
0

Dê uma olhada neste código , é bastante escalável, trabalha com arestas positivas e negativas e resolve o Correlation Clustering (CC) como um caso especial (r = 0). No entanto, no caso do CC (maximização de links positivos e minimização de links negativos dentro de clusters), eu sugeriria outros métodos especializados em resolver esse objetivo.

Para ilustrar, o Correlation Clustering (ao contrário do que a literatura de Detecção da Comunidade busca) não leva em consideração a densidade positiva dos clusters; portanto, quando uma rede não tem ou tem poucos vínculos negativos (na maioria dos casos do mundo real), toda a rede é colocada em um único grupo.

Esmailiano
fonte