Algoritmos para detecção de comunidade para gráficos bipartidos?

Existem algoritmos para detecção da comunidade para gráficos bipartidos (redes de dois modos) implementados no igraph, networkX, R ou Python etc.? Em particular, existe uma implementação em que alguém seria capaz de restringir a detecção de comunidades apenas em um dos dois modos?

python graph-theory adamo
fonte

Como alguém "restringiria a detecção de comunidades apenas em um dos dois modos" sem saber antecipadamente quais nós compõem os modos? Parece circular.

hardmath

Em uma rede bipartida , você já conhece os dois modos. Por exemplo, se metade dos nós pertencentes ao modo "A" se vincularem a um nó que pertence ao modo "B", você terá uma comunidade lá.

Adamo

Se você sabe com antecedência quais nós pertencem a cada modo, isso responde à minha pergunta sobre como restringir a detecção. No entanto, seu exemplo e sua noção implícita de "comunidade" não são claros. Se um vértice em um gráfico bipartido não vincular a nenhum vértice do modo oposto, ele não vinculará a nenhum vértice (seria isolado). Em um gráfico bipartido conectado, todos os vértices do modo "A" são vinculados a algum vértice do modo "B" e vice-versa. "Comunidade" normalmente significaria algo mais do que um subgráfico conectado.

hardmath

Refletindo, suspeito que o seu "link com um nó" pretendia vincular-se a um único nó comum, fornecendo um clique no gráfico projetado (consulte a Resposta) e, portanto, "uma comunidade lá". Desculpas por não ter entendido seu argumento em primeira leitura.

hardmath

Não são necessárias desculpas. Meu inglês não era tão claro assim mesmo.

Adamo

Respostas:

A frase "detecção de comunidade" é vagamente definida como particionando os vértices de um gráfico em "comunidades", de modo que cada um tenha membros mais densamente vinculados um ao outro do que aos membros de outras "comunidades".

Nossa primeira tarefa é verificar o que isso deve significar no caso de um gráfico bipartido, que por definição consiste em dois "modos", de modo que os membros de um modo sejam vinculados apenas aos membros do outro modo. Pode ser expresso, pelo menos para gráficos simples, como tendo uma matriz de adjacência de estrutura de bloco especial:

UMA = (\begin{matrix} 0 0 & B \\ B^{T} & 0 0 \end{matrix})

$A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$

$A^2$ $BB^T$ $B^TB$ $A$

Temos a mesma sorte de que os algoritmos de detecção da comunidade igraph e afins foram "atualizados para lidar com gráficos ponderados" (como multi-gráficos).

S. Fortunato (2010) pesquisa critérios de detecção da comunidade ( detecção da comunidade em gráficos ) e seu uso em redes bipartidas e multipartites. A interpretação que sugiro acima está articulada na página 8:

Gráficos multipartidos são geralmente reduzidos a projeções unipartidas de cada classe de vértice. Por exemplo, da rede bipartida de cientistas e documentos, pode-se extrair apenas uma rede de cientistas, que são relacionados por co-autoria.

hardmath
fonte