Ayuda con la conexión entre valores propios y triángulos

Question

¿Qué es un "triángulo" en un grafo y cuál es la fórmula para calcular el número de triángulos de un grafo utilizando los valores propios de la matriz de adyacencia?

Cualquier ayuda será muy apreciada,

Answer 1

Para un gráfico $G=(V,E)$ , a triángulo es un camino de longitud 3, es decir, un ciclo con 3 nodos (si dibujamos el grafo, gráficamente forma un triángulo). Sea $A$ sea la matriz de adyacencia, donde $[A]_{ij} = a_{ij} = \mathbb{I}[e_{ij}\in E]$ . Supongamos que no hay bordes propios.

En primer lugar, tenga en cuenta que $A^k=\prod_{i=1}^k A$ cuenta el número de longitudes $n$ caminos entre cada par de nodos. Es decir $a_{ij}^k = \#_k(i\rightarrow j)$ es el número de caminos para llegar desde el vértice $i$ a $j$ en $k$ pasos. ¿Por qué? Pues por inducción, $A$ lo cumple, ya que las aristas son la única longitud $1$ caminos. Suponiendo que la propiedad sea cierta para algún $k$ Obsérvese que la multiplicación de $A^k$ por $A$ tiene componentes: $$[A^k]_{ij} = a^k_{ij} = \sum_{v\in V} \#_k(i\rightarrow v) \#_1(v\rightarrow j)$$ Tenga en cuenta que una vez que llegue a $v$ de $i$ todos los caminos posibles desde $v$ a $j$ forman las rutas completas desde $i$ y $j$ a través de $v$ . Así que multiplicamos los recuentos. Todos estos recorridos tienen una longitud $k+1$ porque $i$ a $v$ requiere un paso y la suma de todos los $v$ cubre toda la longitud $k+1$ (y sólo la longitud $k+1$ caminos). Esto nos da todos los caminos de $i$ a $j$ a través de cada $v$ que significa $a_{ij}^k = \#_{k+1}(v\rightarrow j)$ . Otra forma de verlo es considerando normalizarlo y tratarlo como la matriz de transición de la cadena de Markov. Véase aquí también.

Teniendo esto en cuenta, considere que $a^3_{ii}$ cuenta el número de rutas de longitud 3 desde $i$ a $i$ Cada uno de ellos es un triángulo. Así que podemos obtener un recuento de todos los triángulos a través de: $$C_a(G) = \sum_i a^k_{ii} = \text{tr}(A^3)$$ Pero esto cuenta demasiado los triángulos, porque cada triángulo aparecerá $6$ veces ( $v_i\rightarrow v_j \rightarrow v_\ell$ pueden reordenarse/permutarse en $3\cdot 2\cdot 1=6$ formas). Así que deberíamos utilizar $$C(G) = \frac{1}{6}\text{tr}(A^3)$$

Por último, recuerde que la traza de una matriz es igual a la suma de sus valores propios . Así que $\lambda_\alpha$ sea el $\alpha$ eigenvalor de $A$ . A continuación, recordemos que $A$ que sea simétrica significa que tiene una composición propia y que los valores propios de $A^k$ son los $k$ potencias de los valores propios de $A$ ( aquí y aquí ). Así que $\lambda_i^3$ es el $i$ eigenvalor de $A^3$ .

Así, podemos escribir la solución en términos de los valores propios de la matriz de adyacencia mediante $$C(G) = \frac{1}{6}\sum_i \lambda_i^3$$ donde utilizamos el hecho de que $\text{tr}(A^3) = \sum_i \lambda^3_i$ .

---

Ver también esta entrada como señala el comentarista anterior.