Tipo de cálculo discreto
En matemáticas , el cálculo en grafos ponderados finitos es un cálculo discreto para funciones cuyo dominio es el conjunto de vértices de un grafo con un número finito de vértices y pesos asociados a las aristas . Esto implica formular operadores discretos en grafos que son análogos a los operadores diferenciales en cálculo , como los laplacianos de grafos (u operadores de Laplace discretos ) como versiones discretas del laplaciano , y usar estos operadores para formular ecuaciones diferenciales , ecuaciones de diferencia o modelos variacionales en grafos que pueden interpretarse como versiones discretas de ecuaciones diferenciales parciales o modelos variacionales continuos. Dichas 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. Las ecuaciones diferenciales o ecuaciones de diferencia en dichos gráficos se pueden emplear 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), la agrupación de datos , la clasificación de datos o la detección de comunidades en una red social (donde los vértices representan usuarios de la red, los bordes representan vínculos entre usuarios y la función de peso indica la fuerza de las interacciones entre usuarios).
La principal ventaja de los gráficos ponderados finitos es que, al no estar restringidos a estructuras altamente regulares como cuadrículas regulares discretas , gráficos reticulares 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 puede interpretarse como una aproximación discreta de un operador no local relacionado en el entorno continuo.
Definiciones básicas
Un gráfico ponderado finito se define como un triple para el cual![{\estilo de visualización G}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle G=(V,E,w)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
, es un conjunto finito de índices denotados como vértices o nodos del gráfico ,
es un conjunto finito de aristas 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 grafo dirigido , cada arista tiene un nodo inicial y un nodo final . En un grafo no dirigido , para cada arista existe una arista 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 grafos 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 los grafos dirigidos. [1]
![{\displaystyle x_{j}\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{i},x_{j})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{j},x_{i})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle w(x_{i},x_{j})=w(x_{j},x_{i})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La función de peso de arista asocia a cada arista un valor real . Por razones matemáticas y específicas de la aplicación, a menudo se requiere que la función de peso de las aristas 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 aristas con ponderación negativa. A veces se considera una extensión del dominio de la función de peso de arista a (con la función resultante aún llamándose función de peso de arista ) estableciendo siempre que .![{\estilo de visualización w}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{i},x_{j})\en E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle w(x_{i},x_{j})>0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle V\veces V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle w(x_{i},x_{j})=0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{i},x_{j})\no \en E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
En las aplicaciones, cada vértice del gráfico suele representar una sola entidad en los datos dados, por ejemplo, elementos de un conjunto finito de datos, píxeles en una imagen o usuarios en una red social. Un borde del 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, donde el peso del borde codifica la fuerza de esta relación. Las funciones de peso más utilizadas se normalizan para asignarse a valores entre 0 y 1, es decir, .![{\displaystyle x\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle w:E\rightarrow (0,1]}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
En lo que sigue se supone que los grafos considerados están conectados sin bucles propios ni aristas múltiples entre los vértices. Estas suposiciones son en su mayoría inofensivas, ya que en muchas aplicaciones cada componente conectado de un grafo desconectado puede tratarse como un grafo por derecho propio, cada aparición de (que sería distinta de cero en presencia de bucles propios) aparece en presencia de otro factor que desaparece cuando (consulte la sección sobre operadores de grafos diferenciales a continuación), y los pesos de las aristas pueden codificar información similar a la que podrían codificar las aristas múltiples.![{\displaystyle w(x_{i},x_{i})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle i=j}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Vecindario
Un nodo es vecino del nodo si existe una arista . 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, se escribe . La vecindad de un vértice es simplemente el conjunto de vecinos . El grado de un vértice es el tamaño ponderado de su vecindad: ![{\displaystyle x_{j}\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{i}\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{i},x_{j})\en E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{j}\sim x_{i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![estilo de visualización x_{j}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![Estilo de visualización x_{i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![estilo de visualización x_{j}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![Estilo de visualización x_{i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {N}}(x_{i})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{i}\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {N}}(x_{i}):=\{x_{j}\in V\colon x_{j}\sim x_{i}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{i}\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \deg(x_{i}):=\sum _{j\,:\,x_{j}\sim x_{i}}w(x_{i},x_{j}).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Tenga en cuenta que en el caso especial donde en (es decir, el gráfico no está ponderado ) tenemos .![{\displaystyle w\equiv 1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \deg(x_{i}):=|{\mathcal {N}}(x_{i})|}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Espacio de funciones de vértice reales
Sea el espacio de funciones de vértice (reales) . Como es un conjunto finito, cualquier función de vértice se puede representar como un vector de dimensión 1 (donde ) y, por lo tanto, el espacio de funciones de vértice se puede identificar con un espacio de Hilbert de dimensión 2: . El producto interno de se define como:![{\displaystyle {\mathcal {H}}(V):=\{f:V\rightarrow \mathbb {R} \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f\in {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f\in \mathbb {R} ^{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n:=|V|}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(V)\cong \mathbb {R} ^{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \langle f,g\rangle _{{\mathcal {H}}(V)}:=\sum _{x_{i}\in V}f(x_{i})g(x_{i}),\quad \forall f,g\in {\mathcal {H}}(V).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Además, para cualquier función de vértice la -norma y la -norma de se definen como:![{\displaystyle f\in {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \ell_{p}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \ell _{\infty }}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización f}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \|f\|_{p}={\begin{cases}\left(\sum _{x_{i}\in V}|f(x_{i})|^{p}\right)^{\frac {1}{p}},&{\text{ para }}1\leqslant p<\infty \ ,\\\max _{x_{i}\in V}|f(x_{i})|,&{\text{ para }}p=\infty \ .\end{cases}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La -norma es inducida por el producto interno.![{\displaystyle \ell _{2}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
En las 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 un grupo de los nodos.
Espacio de funciones de arista reales
De manera análoga a las funciones de vértice reales, se puede introducir el espacio de funciones de arista reales . Como cualquier función de arista se define en un conjunto finito de aristas , se puede representar como un vector -dimensional , donde . Por lo tanto, el espacio de funciones de arista se puede identificar como un espacio de Hilbert -dimensional, es decir, .![{\displaystyle {\mathcal {H}}(E):=\{F:E\rightarrow \mathbb {R} \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización F}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F\in \mathbb {R} ^{m}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle m:=|E|}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(E)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(E)\cong \mathbb {R} ^{m}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Un caso especial de una función de borde es la función de peso de borde normalizada presentada anteriormente en la sección sobre definiciones básicas. De manera similar a esa función, cualquier función de borde se puede extender de manera trivial a estableciendo si . El espacio de esas funciones de borde extendidas todavía se denota por y se puede identificar con , donde ahora .![{\displaystyle w\dos puntos E\rightarrow (0,1]}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización F}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle V\veces V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F(x_{i},x_{j}):=0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{i},x_{j})\no \en E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(E)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {R} ^{m}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle m:=|V|^{2}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
El producto interno de se define como:![{\displaystyle {\mathcal {H}}(E)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \langle F,G\rangle _{{\mathcal {H}}(E)}:=\sum _{(x_{i},x_{j})\in E}F(x_{i},x_{j})G(x_{i},x_{j}),\quad \forall F,G\in {\mathcal {H}}(E).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Además, para cualquier función de borde, la -norma y la -norma de se definen como:![{\displaystyle F\in {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \ell_{p}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \ell _{\infty }}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización F}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \|F\|_{p}={\begin{cases}\left(\sum _{(x_{i},x_{j})\in E}|F(x_{i},x_{j})|^{p}\right)^{\frac {1}{p}}&{\text{ para }}1\leqslant p<\infty \ ,\\\max _{(x_{i},x_{j})\in E}|F(x_{i},x_{j})|,&{\text{ para }}p=\infty \ .\end{cases}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La -norma es inducida por el producto interno.![{\displaystyle \ell _{2}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Si se extiende el conjunto de aristas de tal manera que entonces queda claro que debido a que . Esto significa que cada función de arista se puede identificar con un operador de matriz lineal.![{\estilo de visualización E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle E=V\veces V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(E)\cong \mathbb {R} ^{n\times n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(V)\cong \mathbb {R} ^{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Operadores de gráficos diferenciales
Un ingrediente importante en el cálculo de grafos finitos ponderados es la imitación de los operadores diferenciales estándar del entorno continuo en el entorno discreto de grafos finitos ponderados. Esto permite traducir herramientas bien estudiadas de las matemáticas, como las ecuaciones diferenciales parciales y los métodos variacionales, y hacerlas utilizables en aplicaciones que se pueden modelar mejor mediante un grafo. El concepto fundamental que hace posible esta traducción es el gradiente del grafo, un operador de diferencia de primer orden en grafos. Con base en esto, se pueden derivar operadores de diferencia de orden superior, por ejemplo, el laplaciano del grafo.
Operadores diferenciales de primer orden
Diferencias ponderadas
Sea un grafo ponderado finito y sea una función de vértice. Entonces la diferencia ponderada (o derivada ponderada del grafo ) de a lo largo de una arista dirigida es![{\displaystyle G=(V,E,w)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f\in {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización f}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{i},x_{j})\en E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \partial_{x_{j}}f(x_{i})\ :=\ {\sqrt {w(x_{i},x_{j})}}\left(f(x_{j})-f(x_{i})\right).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Para cualquier diferencia ponderada se cumplen las siguientes propiedades:
![{\displaystyle \parcial_{x_{i}}f(x_{j})=-\parcial_{x_{j}}f(x_{i}),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \parcial_{x_{i}}f(x_{i})=0,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f(x_{i})=f(x_{j})\Rightarrow \partial _{x_{j}}f(x_{i})=0.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Gradiente ponderado
Basándose en la noción de diferencias ponderadas, se define el operador de gradiente ponderado en gráficos como![{\displaystyle \nabla _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(E)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (\nabla _{w}f)(x_{i},x_{j})\ =\ \partial _{x_{j}}f(x_{i}).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Este es un operador lineal .
Para medir la variación local de una función de vértice en un vértice se puede restringir el gradiente de a todos los bordes dirigidos comenzando en y usando la -norma de esta función de borde, es decir,![{\estilo de visualización f}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{i}\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \nabla _{w}f}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización f}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![Estilo de visualización x_{i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \ell_{p}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \|(\nabla _{w}f)(x_{i},\cdot )\|_{\ell _{p}}={\begin{cases}\left(\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p}\right)^{\frac {1}{p}}&{\text{ para }}1\leq p<\infty ,\\\max _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}|f(x_{j})-f(x_{i})|&{\text{ para }}p=\infty .\end{cases}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Divergencia ponderada
El operador adjunto del operador de gradiente ponderado es un operador lineal definido por ![{\displaystyle \nabla _{w}^{*}\colon {\mathcal {H}}(E)\rightarrow {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \langle \nabla _{w}f,G\rangle _{{\mathcal {H}}(E)}=\langle f,\nabla _{w}^{*}G\rangle _{{ \mathcal {H}}(V)}\quad {\text{ para todos }}f\in {\mathcal {H}}(V),G\in {\mathcal {H}}(E).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Para gráficos no dirigidos con una función de peso simétrica, el operador adjunto de una función en un vértice tiene la siguiente forma:![{\displaystyle w\in {\mathcal {H}}(E)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \nabla _{w}^{*}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F\in {\mathcal {H}}(E)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{i}\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \left(\nabla _{w}^{*}F\right)(x_{i})\ =\ {\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{{\sqrt {w(x_{i},x_{j})}}(F(x_{j},x_{i})-F(x_{i},x_{j}))}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Se puede entonces definir el operador de divergencia ponderada en los gráficos a través del operador adjunto como . La divergencia en un gráfico mide el flujo neto de salida de una función de borde en cada vértice del gráfico.![{\displaystyle \operatorname {div} _{w}:=-\nabla _{w}^{*}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Operadores diferenciales de segundo orden
Operador gráfico de Laplace
El laplaciano de grafos ponderados es un operador muy estudiado en el entorno de grafos. Imitando la relación del operador de Laplace en el entorno continuo, el laplaciano de grafos ponderados se puede derivar para cualquier vértice como:![{\displaystyle \Delta _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \operatorname {div} (\nabla f)=\Delta f}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{i}\en V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\begin{aligned}(\operatorname {div} _{w}(\nabla _{w}f))(x_{i})&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}(\nabla _{w}f(x_{j},x_{i})-\nabla _{w}f(x_{i},x_{j}))\\&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}\left({\sqrt {w(x_{i},x_{j})}}(f(x_{j})-f(x_{i}))-{\sqrt {w(x_{j},x_{i})}}(f(x_{i})-f(x_{j}))\right)\\&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(2f(x_{j})-2f(x_{i}))\\&=\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i}))\ =:\ (\Delta _{w}f)(x_{i}).\end{alineado}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Tenga en cuenta que se debe asumir que el gráfico no está dirigido y tiene una función de peso simétrica para esta representación.![{\estilo de visualización G}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle w(x_{i},x_{j})=w(x_{j},x_{i})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Operadores gráficos p-Laplace
El operador -Laplace continuo es un operador diferencial de segundo orden que se puede traducir fácilmente a gráficos ponderados finitos. Permite traducir varias ecuaciones diferenciales parciales, por ejemplo, la ecuación del calor, a la configuración gráfica.![{\estilo de visualización p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Con base en los operadores de diferencias parciales de primer orden en grafos, se puede derivar formalmente una familia de operadores de grafos ponderados
de Laplace para minimizar la funcional de energía discreta de Dirichlet.![{\displaystyle \Delta _{w,p}\colon {\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 1\leq p<\infty}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle E(f)\ :=\ {\frac {1}{p}}\sum _{x_{i}\in V}\|\nabla _{w}f(x_{i},\cdot )\|_{\ell _{p}}^{p}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Las condiciones de optimalidad necesarias para un minimizador del funcional energético conducen a la siguiente definición del grafo -Laplaciano:![{\estilo de visualización E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (\Delta _{w,p}f)(x_{i})\ :=\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p-2}(f(x_{j})-f(x_{i})).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Nótese que el operador gráfico de Laplace es un caso especial del operador gráfico -Laplace para , es decir, ![{\estilo de visualización p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización p=2}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (\Delta _{w,2}f)(x_{i})\ =\ (\Delta _{w}f)(x_{i})\ =\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i})).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Aplicaciones
El cálculo sobre grafos 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. A continuación, se incluye una lista no exhaustiva de tareas en las que se han empleado grafos ponderados finitos:
Véase también
Notas
- 1. ^ Nótese que también se utiliza una definición ligeramente diferente de grafo no dirigido , que considera que una arista no dirigida es un conjunto de dos elementos (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 que las funciones de arista en (ver la sección sobre el espacio de funciones de arista) tomen valores diferentes en y .
![{\displaystyle (x_{i},x_{j})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{j},x_{i})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {H}}(E)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{i},x_{j})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x_{j},x_{i})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Referencias
- ^ Luxburg, Ulrike von; Audibert, Jean-Yves; Hein, Matthias (2007). "Grafos laplacianos y su convergencia en grafos de vecindad aleatoria". Journal of Machine Learning Research . 8 (junio): 1325–1368. ISSN 1533-7928.
- ^ ab 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.
- ^ ab 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 variedades". IEEE Transactions on Image Processing . 17 (7): 1047–1060. Bibcode :2008ITIP...17.1047E. CiteSeerX 10.1.1.491.1516 . doi :10.1109/TIP.2008.924284. ISSN 1057-7149. PMID 18586614. S2CID 9687337.
- ^ Desquesnes, Xavier; Elmoataz, Abderrahim; Lézoray, Olivier (2013). "Adaptación de la ecuación eikonal en gráficos ponderados: proceso de difusión geométrica rápida para procesamiento de imágenes y datos locales y no locales" (PDF) . Revista de imágenes y visión matemática . 46 (2): 238–257. doi :10.1007/s10851-012-0380-9. ISSN 0924-9907. S2CID 254643702.
- ^ Elmoataz, Abderrahim; Toutain, Matthieu; Tenbrinck, Daniel (2015). "Sobre el $p$-Laplaciano y el $\infty$-Laplaciano en grafos con aplicaciones en procesamiento de imágenes y datos". Revista SIAM sobre 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 basada en gráficos adaptativos para reconstrucciones tomográficas". IEEE Signal Processing Letters . 25 (5): 700–704. arXiv : 1610.00893 . Bibcode :2018ISPL...25..700M. doi :10.1109/LSP.2018.2816582. ISSN 1070-9908. S2CID 3833453.
- ^ Peyré, Gabriel; Bougleux, Sébastien; Cohen, Laurent (2008). "Regularización no local de problemas inversos". En Forsyth, David; Torr, Philip; Zisserman, Andrew (eds.). Visión artificial – ECCV 2008. Apuntes de clase en informática. Vol. 5304. Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 57–68. doi :10.1007/978-3-540-88690-7_5. ISBN 9783540886891.S2CID1044368 .
- ^ Bühler, Thomas; Hein, Matthias (2009). "Agrupamiento espectral basado en el gráfico p-Laplaciano". Actas de la 26.ª Conferencia Internacional Anual sobre Aprendizaje Automático . Montreal, Quebec, Canadá: ACM Press. págs. 81–88. doi :10.1145/1553374.1553385. ISBN. 9781605585161.S2CID858868 .
- ^ Lozes, Francois; Elmoataz, Abderrahim; Lezoray, Olivier (2014). "Operadores de diferencias parciales en gráficos ponderados para el procesamiento de imágenes en superficies y nubes de puntos" (PDF) . IEEE Transactions on Image Processing . 23 (9): 3896–3909. Bibcode :2014ITIP...23.3896L. doi :10.1109/TIP.2014.2336548. ISSN 1057-7149. PMID 25020095. S2CID 6838641.