Algoritmos para la detección comunitaria para gráficos bipartitos?

11

¿Hay algún algoritmo para la detección comunitaria de gráficos bipartitos (redes de 2 modos) implementados en igraph, networkX, R o Python, etc.? En particular, ¿existe tal implementación en la cual uno podría restringir la detección de comunidades solo en uno de los dos modos?

python graph-theory adamo
fuente
2
¿Cómo se "restringiría la detección de comunidades solo en uno de los dos modos" sin saber de antemano qué nodos componen los modos? Parece circular
hardmath
En una red bipartita ya conoces los dos modos. Entonces, por ejemplo, si la mitad de los nodos que pertenecen al modo "A" se vinculan con un nodo que pertenece al modo "B", entonces tiene una comunidad allí.
adamo
Si sabe de antemano qué nodos pertenecen a cada modo, entonces eso responde a mi pregunta sobre cómo restringir la detección. Sin embargo, su ejemplo y su noción implícita de "comunidad" no está clara. Si un vértice en un gráfico bipartito no se vincula a ningún vértice del modo opuesto, entonces no se vincula a ningún vértice (estaría aislado). En un gráfico bipartito conectado, cada vértice de modo "A" se vincula a algún vértice de modo "B" y viceversa. "Comunidad" normalmente significaría algo más que un subgráfico conectado.
2012
Al reflexionar, sospecho que su "vínculo con un nodo" significaba vincularse con un solo nodo común, dando una camarilla en el gráfico proyectado (ver Respuesta) y, por lo tanto, "una comunidad allí". Disculpas por no entender su punto en la primera lectura.
hardmath
No se necesitan disculpas. Mi inglés no era tan claro de todos modos.
adamo

Respuestas:

5

La frase "detección de comunidad" se define libremente como la división de los vértices de un gráfico en "comunidades" de manera que cada uno tiene miembros más densamente vinculados entre sí que a los miembros de otras "comunidades".

Nuestra primera tarea es determinar lo que esto debería significar en el caso de un gráfico bipartito, que por definición consiste en dos "modos" de modo que los miembros de un modo estén vinculados solo a los miembros del otro modo. Puede expresarse, al menos para gráficos simples, como una matriz de adyacencia de estructura de bloque especial:

A=(0BBT0)

A2BBTBTBA

Somos igualmente afortunados porque los algoritmos de detección de la comunidad igraph y los relacionados se han "actualizado para manejar gráficos ponderados" (como los gráficos múltiples).

S. Fortunato (2010) encuesta los criterios de detección de la comunidad ( detección de la comunidad 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 documentos se puede extraer una red de científicos solamente, que están relacionados por coautoría.

hardmath
fuente