¿Un contraejemplo para refutar que no todas las matrices de adyacencia pueden hacerse diagonales en bloque?

Question

Tengo un montón de grupos de proteínas (un gráfico desconectado) y quería presentar estos datos como una matriz de adyacencia por varias razones y he estado buscando una manera de hacer que estas matrices de adyacencia sean diagonales en bloque para que las relaciones sean más evidentes, pero no tuve suerte. He probado El sistema SciPy's invertir Cuthill-McKee , svd, alguien ha recomendado Dulmage-Mendehlson y un montón de otras descomposiciones, pero en vano. En este punto, alguien me dijo que esto podría no ser posible en todos los casos.

¿Por casualidad alguien tiene un ejemplo o una formulación concreta de por qué exactamente? No consigo convencerme de que no es posible con sólo mirar mis datos, que por cierto tienen este aspecto... Claramente, las estructuras que estoy tratando de presentar están ahí (el grande y pequeño subunidades ribosómicas) y probablemente se hará más evidente cuando vierta más datos allí, pero me hubiera gustado tanto diferenciar también los clusters dentro de las dos subunidades porque sé que están ahí. ¿Debería utilizar simplemente una matriz de covarianza?

A propósito, esto es lo que arroja la búsqueda "breadth-first". Todavía no estoy seguro de lo que significa, pero definitivamente puedo ver ahora que permutar de este estado de minimización de la banda rompe la estructura en lugar de construirla, así que tal vez sea lo más lejos que llegue hoy.

Answer 1

Siempre se pueden permutar las filas y columnas de la matriz de adyacencia para que cada bloque corresponda a un componente conectado. Sólo tienes que encontrar los componentes conectados y luego reordenarlos con todos los nodos del componente 1 primero, el componente 2 después, y así sucesivamente.

Answer 2

Algunas preguntas:

1. ¿Qué representan los colores de sus parcelas?
2. ¿Cómo puedes estar seguro de que tu gráfico está desconectado si no has diagonalizado en bloque su matriz de adyacencia? ¿Hay algo en la naturaleza de los datos que lo garantice?

Ahora algunos comentarios:

Si su gráfico realmente tiene $n$ componentes desconectados, entonces su matriz de adyacencia puede escribirse ciertamente en forma de bloque diagonal con $n$ bloques, independientemente de lo que digan los demás.

Algo como lo siguiente debería funcionar. Que A ser un m por m matriz de adyacencia. Crear una matriz componentIdentifier de longitud m con cada elemento inicializado a 0. También crea un array permutation de longitud m .

numberComponents = 0
numberVerticesPermuted = 0
for i from 1 to m:
   if componentIdentifier[i] == 0:
      /* vertex i is in a new component */
      numberComponents = numberComponents + 1
      componentIdentifier[i] = numberComponents
      numberVerticesPermuted = numberVerticesPermuted + 1
      permutation[numberVerticesPermuted] = i

      /* find all vertices connected to i */
      k = numberVerticesPermuted
      while k <= numberVerticesPermuted:
         r = permutation[k]
         for c from 1 to m:
            if A[r,c] == 1 and componentIdentifier[c] == 0:
               componentIdentifier[c] = numberComponents
               numberVerticesPermuted = numberVerticesPermuted + 1
               permutation[numberVerticesPermuted] = c
         k = k + 1

Cuando esto concluya, numberComponents contendrá el número de componentes desconectados y permutation tendrá la permutación de índices necesaria para poner la matriz de adyacencia en forma diagonal de bloque.