En matemáticas , el cálculo en gráficas ponderadas finitas es un cálculo discreto para funciones cuyo dominio es el conjunto de vértices de una gráfica con un número finito de vértices y pesos asociados a las aristas . Esto implica formular operadores discretos en gráficos que son análogos a los operadores diferenciales en cálculo , como los laplacianos de gráficos (u operadores de Laplace discretos ) como versiones discretas del laplaciano , y usar estos operadores para formular ecuaciones diferenciales , ecuaciones en diferencias., o modelos variacionales en gráficos que pueden interpretarse como versiones discretas de ecuaciones diferenciales parciales o modelos variacionales continuos. Tales ecuaciones y modelos son herramientas importantes para modelar, analizar y procesar matemáticamente información discreta en muchos campos de investigación diferentes, por ejemplo, procesamiento de imágenes , aprendizaje automático y análisis de redes .
En las aplicaciones, los gráficos ponderados finitos representan un número finito de entidades por los vértices del gráfico, cualquier relación por pares entre estas entidades por los bordes del gráfico y la importancia de una relación por una función de peso del borde. Se pueden emplear ecuaciones diferenciales o ecuaciones en diferencias en dichos gráficos para aprovechar la estructura del gráfico para tareas como la segmentación de imágenes (donde los vértices representan píxeles y los bordes ponderados codifican la similitud de píxeles en función de comparaciones de vecindarios de Moore o ventanas más grandes), agrupación de datos , datos clasificación o detección de comunidad en una red social (donde los vértices representan a los usuarios de la red, los bordes representan los vínculos entre los usuarios y la función de peso indica la fuerza de las interacciones entre los usuarios).
La principal ventaja de los gráficos ponderados finitos es que al no estar restringidos a estructuras muy regulares como cuadrículas regulares discretas , gráficos de celosía o mallas , se pueden aplicar para representar datos abstractos con interrelaciones irregulares.
Si un gráfico ponderado finito está incrustado geométricamente en un espacio euclidiano, es decir, los vértices del gráfico representan puntos de este espacio, entonces se puede interpretar como una aproximación discreta de un operador no local relacionado en la configuración del continuo.
Definiciones basicas
Un gráfico ponderado finito se define como un triple para cual
- , es un conjunto finito de índices denotados como vértices o nodos de grafos ,
- es un conjunto finito de bordes de grafos (dirigidos) que conectan un subconjunto de vértices,
- es una función de peso de borde definida en los bordes del gráfico.
En un gráfico dirigido , cada bordetiene un nodo de inicio y un nodo final . En un gráfico no dirigido para cada borde existe una ventaja y se requiere que la función de peso sea simétrica, es decir, . [1] En el resto de esta página, se asumirá que los gráficos no están dirigidos, a menos que se indique específicamente lo contrario. Muchas de las ideas presentadas en esta página se pueden generalizar a gráficos dirigidos. [1]
La función de peso del borde asociados a cada borde un valor real . Por razones tanto matemáticas como específicas de la aplicación, a menudo se requiere que la función de peso en los bordes sea estrictamente positiva y en esta página se asumirá que lo es a menos que se indique específicamente lo contrario. Es posible generalizar muchas de las ideas presentadas en esta página para incluir bordes ponderados negativamente. A veces, una extensión del dominio de la función de peso del borde parase considera (con la función resultante aún siendo llamada la función de peso de borde ) configurando cuando sea .
En las aplicaciones, cada vértice del gráfico generalmente representa una sola entidad en los datos dados, por ejemplo, elementos de un conjunto de datos finito, píxeles en una imagen o usuarios en una red social. Un borde de gráfico representa una relación entre dos entidades, por ejemplo, interacciones por pares o similitudes basadas en comparaciones de vecindades geométricas (por ejemplo, píxeles en imágenes) o de otra característica, con el peso del borde codificando la fuerza de esta relación. Las funciones de ponderación más utilizadas se normalizan para mapear valores entre 0 y 1, es decir,.
A continuación, se asume que los gráficos considerados están conectados sin auto-bucles o múltiples aristas entre vértices. Estas suposiciones son en su mayoría inofensivas, ya que en muchas aplicaciones cada componente conectado de un gráfico desconectado puede tratarse como un gráfico por derecho propio, cada aparición de (que sería distinto de cero en presencia de bucles propios) aparece en presencia de otro factor que desaparece cuando (consulte la sección sobre operadores de gráficos diferenciales a continuación), y los pesos de los bordes pueden codificar información similar a la de varios bordes.
Vecindario
Un nodo es vecino del nodo si existe una ventaja . En términos de notación, esta relación se puede abreviar por, que debe leerse como " es vecino de ". De lo contrario, si no es vecino de uno escribe . El barrio de un vértice es simplemente el conjunto de vecinos . El grado de un vértice es el tamaño ponderado de su vecindario:
Tenga en cuenta que en el caso especial donde en (es decir, el gráfico no está ponderado ) tenemos.
Espacio de funciones de vértice reales
Dejar ser el espacio de funciones de vértice (reales) . Desde es un conjunto finito, cualquier función de vértice se puede representar como un -vector dimensional (dónde ) y por lo tanto el espacio de las funciones de vértice puede identificarse con un -espacio de Hilbert dimensional: . El producto interno de Se define como:
Además, para cualquier función de vértice la -norm y -norm de se definen como:
La -norm es inducida por el producto interno.
En aplicaciones, las funciones de vértice son útiles para etiquetar los vértices de los nodos. Por ejemplo, en la agrupación de datos basada en gráficos, cada nodo representa un punto de datos y se utiliza una función de vértice para identificar la pertenencia a la agrupación de los nodos.
Espacio de funciones de borde reales
De manera análoga a las funciones de vértice reales, se puede introducir el espacio de funciones de borde reales . Como cualquier función de borde se define en un conjunto finito de aristas , se puede representar como -vector dimensional , dónde . Por lo tanto, el espacio de las funciones de borde se puede identificar como un -espacio de Hilbert dimensional, es decir, .
Un caso especial de una función de borde es la función de peso de borde normalizado introducido anteriormente en la sección de definiciones básicas . Similar a esa función, cualquier función de borde puede extenderse trivialmente a configurando Si . El espacio de esas funciones de borde extendidas todavía se denota por y se puede identificar con , donde ahora .
El producto interno de Se define como:
Además, para cualquier función de borde la -norm y -norm de se definen como:
La -norm es inducida por el producto interno.
Si uno extiende el conjunto de bordes de una manera tal que de lo que queda claro que porque . Esto significa que cada función de borde se puede identificar con un operador de matriz lineal.
Operadores de grafos diferenciales
Un ingrediente importante en el cálculo de gráficos ponderados finitos es la imitación de operadores diferenciales estándar de la configuración del continuo en la configuración discreta de gráficos ponderados finitos. Esto permite traducir herramientas bien estudiadas de las matemáticas, como ecuaciones diferenciales parciales y métodos variacionales, y hacerlas utilizables en aplicaciones que se pueden modelar mejor mediante un gráfico. El concepto fundamental que hace posible esta traducción es el gradiente de gráfico, un operador de diferencia de primer orden en los gráficos. Con base en esto, se pueden derivar operadores de diferencias de orden superior, por ejemplo, el gráfico Laplaciano.
Operadores diferenciales de primer orden
Diferencias ponderadas
Dejar ser un gráfico ponderado finito y dejar ser una función de vértice. Luego, la diferencia ponderada (o derivada del gráfico ponderado ) de a lo largo de un borde dirigido es
Para cualquier diferencia ponderada, se mantienen las siguientes propiedades:
Gradiente ponderado
Basado en la noción de diferencias ponderadas, se define el operador de gradiente ponderado en los gráficos. como
Este es un operador lineal .
Para medir la variación local de una función de vértice en un vértice uno puede restringir el gradiente de a todos los bordes dirigidos comenzando en y usando el -norm de esta función de borde, es decir,
Divergencia ponderada
El operador adjunto del operador de gradiente ponderado es un operador lineal definido por
Para gráficos no dirigidos con función de ponderación simétrica el operador adjunto de una función en un vértice tiene la siguiente forma:
A continuación, se puede definir el operador de divergencia ponderada en los gráficos mediante el operador adjunto como. La divergencia en un gráfico mide la salida neta de una función de borde en cada vértice del gráfico.
Operadores diferenciales de segundo orden
Operador Graph Laplace
El grafo ponderado Laplaciano es un operador bien estudiado en la configuración de gráficos. Imitando la relación del operador de Laplace en la configuración del continuo, el gráfico ponderado Laplacian se puede derivar para cualquier vértice como:
Tenga en cuenta que hay que asumir que la gráfica no está dirigido y tiene una función de peso simétrica para esta representación.
Graficar operadores de p-Laplace
El continuo -El operador de Laplace es un operador diferencial de segundo orden que se puede traducir bien a gráficos ponderados finitos. Permite la traducción de varias ecuaciones diferenciales parciales, por ejemplo, la ecuación de calor, a la configuración del gráfico.
Con base en los operadores de diferencias parciales de primer orden en los gráficos, se puede derivar formalmente una familia de gráficos ponderados.-Operadores de Laplace por por minimización de lo discreto -Dirichlet energético funcional
Las condiciones de optimalidad necesarias para un minimizador de la energía funcional conducen a la siguiente definición del gráfico -Laplaciano:
Tenga en cuenta que el operador gráfico de Laplace es un caso especial del gráfico -Operador de Laplace para , es decir,
Aplicaciones
El cálculo en gráficos ponderados finitos se utiliza en una amplia gama de aplicaciones de diferentes campos, como el procesamiento de imágenes, el aprendizaje automático y el análisis de redes. Una lista no exhaustiva de tareas en las que se han empleado gráficos ponderados finitos es:
- eliminación de ruido de imágenes [2] [3]
- segmentación de imágenes [4]
- imagen en pintura [2] [5]
- reconstrucción tomográfica [6]
- problemas inversos [7]
- agrupación de datos [8]
- compresión de nube de puntos [9]
- reconocimiento de dígitos escritos a mano [3]
Ver también
- Modelos de campo de fase en gráficos
Notas
- 1. ^ Tenga en cuenta que también se utiliza una definición ligeramente diferente de gráfico no dirigido , que considera que un borde no dirigido es un conjunto de dos (conjunto con dos elementos distintos) en lugar de un par de pares ordenados y . Aquí se necesita la última descripción, ya que se requiere para permitir funciones de borde en (ver la sección sobre el espacio de las funciones de borde ) para tomar diferentes valores en y .
Referencias
- ↑ Luxburg, Ulrike von; Audibert, Jean-Yves; Hein, Matthias (2007). "Grafique a los laplacianos y su convergencia en gráficos de vecindad aleatorios" . Revista de investigación sobre aprendizaje automático . 8 (junio): 1325-1368. ISSN 1533-7928 .
- ^ a b Gilboa, Guy; Osher, Stanley (2009). "Operadores no locales con aplicaciones al procesamiento de imágenes". Modelado y simulación multiescala . 7 (3): 1005–1028. doi : 10.1137 / 070698592 . ISSN 1540-3459 . S2CID 7153727 .
- ^ a b Elmoataz, A .; Lezoray, O .; Bougleux, S. (2008). "Regularización discreta no local en gráficos ponderados: un marco para el procesamiento de imágenes y múltiples". Transacciones IEEE sobre procesamiento de imágenes . 17 (7): 1047–1060. doi : 10.1109 / TIP.2008.924284 . ISSN 1057-7149 . PMID 18586614 .
- ^ Desquesnes, Xavier; Elmoataz, Abderrahim; Lézoray, Olivier (2013). "Adaptación de ecuaciones de Eikonal en gráficos ponderados: proceso de difusión geométrica rápida para procesamiento de datos e imágenes locales y no locales" (PDF) . Revista de Visión y Imágenes Matemáticas . 46 (2): 238-257. doi : 10.1007 / s10851-012-0380-9 . ISSN 0924-9907 .
- ^ Elmoataz, Abderrahim; Toutain, Matthieu; Tenbrinck, Daniel (2015). "Sobre el $ p $ -Laplacian y $ \ infty $ -Laplacian en Gráficos con Aplicaciones en Procesamiento de Imagen y Datos". Revista SIAM de Ciencias de la Imagen . 8 (4): 2412–2451. doi : 10.1137 / 15M1022793 . ISSN 1936-4954 . S2CID 40848152 .
- ^ Mahmood, Faisal; Shahid, Nauman; Skoglund, Ulf; Vandergheynst, Pierre (2018). "Variación total adaptativa basada en gráficos para reconstrucciones tomográficas". Cartas de procesamiento de señales IEEE . 25 (5): 700–704. arXiv : 1610.00893 . doi : 10.1109 / LSP.2018.2816582 . ISSN 1070-9908 .
- ^ Peyré, Gabriel; Bougleux, Sébastien; Cohen, Laurent (2008). Forsyth, David; Torr, Philip; Zisserman, Andrew (eds.). Regularización no local de problemas inversos . 5304 . Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 57–68. doi : 10.1007 / 978-3-540-88690-7_5 . ISBN 9783540886891. S2CID 1044368 .
- ^ Bühler, Thomas; Hein, Matthias (2009). "Agrupación espectral basada en el gráfico p -Laplaciano" . Actas de la 26a Conferencia Internacional Anual sobre Aprendizaje Automático - ICML '09 . Montreal, Quebec, Canadá: ACM Press: 1–8. doi : 10.1145 / 1553374.1553385 . ISBN 9781605585161.
- ^ Lozes, Francois; Elmoataz, Abderrahim; Lezoray, Olivier (2014). "Operadores de diferencia parcial en gráficos ponderados para el procesamiento de imágenes en superficies y nubes de puntos" (PDF) . Transacciones IEEE sobre procesamiento de imágenes . 23 (9): 3896–3909. doi : 10.1109 / TIP.2014.2336548 . ISSN 1057-7149 . PMID 25020095 .