Pregunta:
¿Existe algún algoritmo para la detección de comunidad para gráficos bipartitos (redes de 2 modos) implementados en igraph, networkX, R o Python, etc.? En particular, ¿existe una implementación en la que se pueda restringir la detección de comunidades solo en uno de los dos modos?
Respuesta:
La frase "detección de comunidad" se define vagamente como dividir los vértices de un gráfico en "comunidades" de modo que cada una tenga miembros más densamente vinculados entre sí que con miembros de otras "comunidades".
Nuestra primera tarea es determinar qué debería significar esto en el caso de un gráfico bipartito, que por definición consta de dos "modos" de modo que los miembros de un modo están vinculados sólo a los miembros del otro modo. Puede expresarse, al menos para gráficos simples, como si tuviera una matriz de adyacencia de estructura de bloques especial:
$$ A = \ begin {pmatrix} 0 & B \\ B ^ T & 0 \ end {pmatrix} $$
Me parece que la interpretación más pertinente de "restringir la detección de comunidades solo en uno de los dos modos" aplicaría dichos algoritmos a los gráficos "proyectados" correspondientes a bloques de $ A ^ 2 $, es decir, el primer modo con adyacencia matriz $ BB ^ T $ y el segundo modo con matriz de adyacencia $ B ^ TB $. Tenga en cuenta que incluso si el gráfico bipartito original es simple (de modo que $ A $ es binario), los gráficos proyectados generalmente serán gráficos múltiples. Afortunadamente, igraph tiene un método para construirlos por nosotros.
Somos igualmente afortunados porque los algoritmos de detección de la comunidad de igraph y otros relacionados se han "actualizado para manejar gráficos ponderados" (como los gráficos múltiples).
S. Fortunato (2010) analiza los criterios de detección de comunidades ( detección de comunidades en gráficos ) y su uso con redes bipartitas y multipartitas. La interpretación que sugiero arriba se articula en la página 8:
Los gráficos multipartitos generalmente se reducen a proyecciones unipartitas de cada clase de vértice. Por ejemplo, de la red bipartita de científicos y artículos se puede extraer solo una red de científicos, que están relacionados por coautoría.