Solución:
Cómo entender el Graph Laplacian (receta de 3 pasos para impacientes)
-
lea la respuesta aquí por Muni Pydi. Esto es esencialmente un concentrado de un artículo completo, que es muy agradable y está bien escrito (ver aquí).
-
trabajar con el ejemplo de Muni. En particular, olvídese temporalmente de la matriz de adyacencia y utilice en su lugar la matriz de incidencia.
¿Por qué? Porque la matriz de incidencia muestra la relación nodos-aristas, y que a su vez se puede reinterpretar como un acoplamiento entre vectores (el valor en los nodos) y vectores duales (los valores en las aristas). Consulte el punto 3 a continuación.
- ahora, después de 1 y 2, piense en esto:
conoces al laplaciano en $ R ^ n $ o más generalmente en geometría diferencial.
El primer paso es discretizar: piense en colocar una cuadrícula regular en su colector y discretice todas las operaciones ( las derivadas se convierten en diferencias entre puntos adyacentes). Ahora ya estás en el ámbito de los laplacianos gráficos. Pero no del todo: la cuadrícula es un tipo de gráfico muy especial, por ejemplo, el grado de un nodo es siempre el mismo.
Por lo tanto, necesita generalizar un poco más: olvídese de la variedad subyacente y DEFINE LAS DERIVADAS y el LAPLACIAN directamente en el gráfico.
Si hace lo anterior, verá que el Laplaciano en el Gráfico es exactamente lo que imagina que es, el Divergencia del gradiente. Excepto que aquí los mapas de gradiente funcionan en los nodos a funciones en los bordes (a través de la derivada discreta, donde cada borde es una dirección …) y la divergencia asigna el gradiente de nuevo a una función de nodos: la que mide el valor en un nodo con respecto a sus vecinos. Entonces, nodos-bordes-nodos, esa es la forma (es por eso que dije enfocarse en la matriz de incidencia)
Espero eso ayude
Este es solo un comentario largo, que se suma a las excelentes respuestas anteriores.
Hay un gran artículo de László Lovász “Discreto y continuo: ¿dos caras de lo mismo?”, Escrito alrededor del año 2000 (https://web.cs.elte.hu/~lovasz/telaviv.pdf) que podría ser de interés para usted. En el capítulo 5 de este artículo, Lovász cubre el gráfico laplaciano. Explica la relación con los paseos aleatorios en los gráficos y también el enlace al invariante gráfico de Colin de Vérdière que despertó su interés (su enlace en el OP).
En su OP, se pregunta cómo puede el gráfico Laplaciano ser tan poderoso cuando se aplica a gráficos. Creo que dos citas de este artículo podrían ser de especial interés para usted, porque la cita (1) se relaciona con el “poder” y la cita (2) se relaciona con las “limitaciones” en la aplicación del gráfico Laplaciano.
Sobre el “poder”:
Cotización (1)
“El laplaciano tiene sentido en la teoría de grafos, y de hecho es una herramienta básica. Además, el estudio de las versiones discretas y continuas interactúan de diversas formas, por lo que el uso de una u otra es casi una cuestión de conveniencia en algunos casos. (…) El invariante de Colin de Verdière generó mucho interés entre los teóricos de grafos, debido a sus propiedades sorprendentemente agradables de la teoría de grafos. (…) Además, la planaridad de los gráficos se puede caracterizar por este invariante: $ mu (G) leq 3 $ si y solo si G es plano. La prueba original de Colin de Verdière de la parte “si” de este hecho era muy inusual en la teoría de grafos: básicamente, invirtiendo el procedimiento anterior, mostró cómo reconstruir una esfera y un operador diferencial parcial elíptico positivo. $ P $ en eso para que $ mu (G) $ está delimitado por la dimensión del espacio nulo de $ P $, y luego invocó un teorema de Cheng (…) afirmando que esta dimensión es como mucho $ 3 $.
Acerca de las “limitaciones”:
Cotización (2)
“Más tarde Van der Holst (…) encontró una prueba combinatoria de este hecho [$mu(G) leq 3$ if and only if G is planar]. Si bien esto puede parecer un paso atrás (después de todo, eliminó la necesidad de la única aplicación de ecuaciones diferenciales parciales en la teoría de grafos que conozco), abrió la posibilidad de caracterizar el siguiente caso. Verificando una conjetura de Robertson, Seymour y Thomas, Lovász y Schrijver demostraron (…) que $ mu (G) leq 4 $ si y solo si G es insertable sin enlaces en $ mathbb R ^ 3 $. “
No se trata realmente de la conexión con la teoría de grafos, un tema del que soy bastante ignorante, sino de la conexión con las nociones de continuo, todo lo cual aprendí de este artículo.
Considere un complejo simple en 3 dimensiones para simplificar la visualización. Los 0-simplex son vértices $ (i) $, los 1-simplex son enlaces $ (ij) $, 2-simplex son triángulos $ (ijk) $, 3-simplex son tetraedros $ (ijkl) $. Cada símplex tiene una orientación y la subpermutación de vértices adquiere un cambio de signo de +1 o -1 si la permutación es par o impar respectivamente.
Ahora podemos definir funciones ($ p $-cadenas) en nuestro complejo simplicial,
$$ phi = sum_i phi_i (i) $$
$$ alpha = sum_ {[ij]} alpha_ {ij} (ij) $$
$$ beta = sum_ {[ijk]} beta_ {ijk} (ijk) $$
$$ gamma = sum_ {[ijkl]} gamma_ {ijkl} (ijkl) $$
donde el $ alpha_ {ij} $ etc. son completamente antisimétricos y la suma está por encima de las clases de equivalencia de símplex (es decir, elegimos un representante para cada simplex de sus posibles permutaciones).
Ahora definimos un operador de límite $ parcial_p $ sobre $ p $-simplejos. En un 0-simplex, tenemos $ parcial_0 (i) = 0 $. Para un 1-simplex tenemos
$$ parcial_1 (ij) = (j) – (i) $$
y generalizamos esto,
$$ part_p (i_0 cdots i_ {p-1}) = sum_n (-1) ^ n (i_0 cdots hat {i} _n cdots i_ {p-1}) $$
donde el sombrero significa que se elimina el vértice. Esto equivale a decir que el límite de un $ p $-simplex es la suma de los $ p-1 $-simplices que lo delimitan, cada uno orientado de tal manera que sus “bordes” están orientados de manera opuesta. Así, para un triángulo encontramos
$$ parcial_2 (ijk) = (jk) + (ki) + (ij) $$
mientras que para un tetraedro tenemos
$$ parcial_3 (ijkl) = (jkl) + (kli) + (lij) + (ijk) $$
Esta construcción satisface automáticamente $ parcial_ {p-1} parcial_ {p} = 0 $ debido a la condición anterior de “bordes opuestos”.
A continuación, defina el operador co-límite $ parcial_p ^ daga $ el cual toma $ p $-cadenas para $ p + 1 $-cadenas. La definición dice
$$ part_p ^ dagger (i_1 cdots i_ {p}) = sum_ {[email protected][i_1 cdots i_{p}]} (i_0 cdots i_ {p}) $$
dónde [email protected]PS significa “adyacente a”. Por lo tanto, para un 0-simplex,
$$ parcial_0 ^ daga (j) = sum_ {[email protected]} (ij) $$
Tenga en cuenta que la suma está sobreorientada en 1-simples que “apuntan hacia $ (j) $“. Para un 1-simplex $ (ij) $, $ parcial_1 ^ daga (ij) $ es la suma sobre todos los triángulos $ (i_0 i_1 i_2) $ tal que $ parcial_2 (i_0 i_1 i_2) $ contiene $ + (ij) $, etcétera. Este operador también satisface $ parcial_ {p + 1} ^ daga parcial_p ^ daga = 0 $ por construcción.
Los operadores de límites y co-límites actúan sobre $ p $-cadenas linealmente. Podemos establecer una analogía con la geometría diferencial; en particular, el operador co-límite es análogo a la derivada exterior, y $ p $-las cadenas son similares al exterior $ p $-formas. Como se muestra en el documento vinculado anteriormente, podemos pensar en $ 0 $-cadenas como campos escalares, $ 1 $-cadenas como campos vectoriales, $ 2 $-cadenas como campos pseudo-vectoriales, y $ 3 $-cadenas como campos pseudoescalares. Las propiedades de los operadores de frontera se resumen luego en esta figura (su $ d $ es mi $ parcial ^ daga $):
Tenga en cuenta que la correspondencia no es una aproximación (consulte el texto para obtener más detalles), aunque se puede hacer una conexión con los operadores diferenciales del continuo mediante una aproximación de expansión de Taylor en el límite del continuo a medida que el espaciado de celosía llega a cero.
Ahora se pueden definir ciertas operaciones de productos vectoriales, demostrar el teorema de Stoke, etc. utilizando esta construcción. En particular, podemos definir el laplaciano para $ p $-cadenas como
$$ Delta_p = – ( parcial_ {p + 1} parcial_ {p} ^ daga + parcial_ {p-1} ^ daga parcial_p) $$
luego de la figura encontramos la correspondencia
$$ Delta_0 sim mathrm {div} , mathrm {grad} $$
$$ Delta_1 sim mathrm {grad} , mathrm {div} – mathrm {curl} , mathrm {curl} $$
$$ Delta_2 sim mathrm {grad} , mathrm {div} – mathrm {curl} , mathrm {curl} $$
$$ Delta_3 sim mathrm {div} , mathrm {grad} $$
En particular, $ Delta_0 = – parcial_1 parcial_0 ^ daga $ es el gráfico laplaciano habitual, y se puede mostrar (con la elección adecuada de representantes en las sumas anteriores), que
$$ Delta_0 = A – D $$
dónde $ A $ es la matriz de adyacencia y $ D $ es la matriz de incidencia del gráfico (ver aquí). En notación de coordenadas, parece
$$ Delta_0 phi = – parcial_1 parcial_0 ^ daga sum_i phi_i (i) $$
$$ = – parcial_1 sum_ {i} phi_i sum_ {[email protected]} (ji) $$
$$ = – sum_ {i} phi_i sum_ {[email protected]} [(i) – (j)]$$
$$ = – sum_ {i} (i) sum_ {[email protected]} ( phi_i – phi_j) $$
por lo que es fácil ver que la expresión anterior es correcta:
$$ Delta_0 phi = sum_ {i} (i) sum_ {[email protected]} phi_j – sum_ {i} (i) sum_ {[email protected]} phi_i \ = sum_i (i) sum_j (A_ {ij} – D_ {ij}) phi_j $$
dónde $ D_ {ij} = delta_ {ij} z_i $ con $ z_i $ siendo el número de coordinación del vértice $ i $ y $ A_ {ij} = delta_ {[email protected]PS. Los operadores laplacianos de orden superior se relacionan luego con la estructura del gráfico de ciertos duales vínculo / cara / cuerpo del gráfico original.
Existe una conexión adicional con varios temas como la cohomología de De Rham, la descomposición de Hodge y las formas armónicas. En particular, podemos descomponer cualquier $ p $-cadena en
$$ sigma ^ p = partial_ {p-1} ^ dagger alpha ^ {p-1} + partial_ {p + 1} beta ^ {p + 1} + gamma ^ {p} $$
dónde $ gamma ^ {p} $ es una “cadena armónica” y satisface $ Delta_p gamma ^ {p} = 0 $, y corresponde a una contribución que “enrolla” el enrejado topológicamente, es decir $ gamma ^ {p} en H_p $, los $ p $‘th grupo de homología del complejo. No he visto que eso se haga más explícito en ninguna parte todavía y no sé lo suficiente sobre los temas por mí mismo para realmente comentar más.