Sesión AnálisisConcentración de grafos con métricas y atributos aleatorios alrededor del grafo medio
Exequiel Arias
Facultad de Ciencias Exactas y Naturales, Catamarca, UNCa, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un grafo no dirigido, ponderado en las aristas y con atributos en los vértices es una 4-upla $\mathcal{G}=(\mathcal{V},\mathcal{E},\bar{a},W)$ donde $\mathcal{V}=\{1,...,n\}$ son los vértices, $\mathcal{E}=\{\{i,j\}: i\neq j \in \mathcal{V}\}$ son las aristas, $\bar{a}=(a_1,...,a_n)$ son los pesos en los vértices con $\sum_{i=1}^{n}a_i=1$ y $a_i \gt 0$ para todo $i\in \mathcal{V}$ y $W=(w_{ij})_{i,j=1,...,n}$, $w_{ij}=w_{ji}$, $w_{ii}=0$ y $w_{ij}\geq 0$ son ponderaciones de las aristas que pueden representar una métrica entre los vértices $i$ y $j$. Esta métrica depende de la elección inicial de atributos $\bar{a}$ de los vértices y ponderaciones $W$ de las aristas. Por otra parte la elección inicial suele ser intrínsecamente aleatoria. Por consiguiente, en vez de un grafo $\mathcal{G}$ tenemos variables aleatorias valuadas en grafos, $\mathcal{G}_\omega$. En este trabajo, usando la teoría de Cramér-Chernoff [1] y el Lema de Hoeffding [2], estudiamos la convergencia a cero cuando $t$ tiende a infinito de las probabilidades de ``lejanía'' entre $\mathcal{G}_\omega$ y $\mathbb{E}(\mathcal{G})$ definido por las medias de $\bar{a}(\omega)$ y $W(\omega)$, precisamente $$\mathcal{P}(\{\omega\in \Omega: \textbf{d}(\mathcal{G}_\omega, \mathbb{E}(\mathcal{G})) \gt t\}).$$ Resulta claro que una buena definición de distancia entre grafos ponderados con atributos se hace necesaria. Para esta definición, que va a resultar ser una casi-métrica, primero consideramos la distancia entre espacios métricos desde el enfoque de Gromov-Lipschitz [3] y las distancias entre medidas probabilísticas de Kantorovich-Rubinstein [4].
Sean $(X,d,\mu)$ e $(Y,\delta,\nu)$ dos espacios métricos con $\mu$ y $\nu$ probabilidades borelianas. Sea $\Lambda=\{f:(X,d)\rightarrow (Y,\delta) \,\, bi-Lipschitz\}$ y, si $\Lambda \neq \emptyset$, para cada $f \in \Lambda$ definimos las medidas probabilísticas $\tilde{\mu}_f=\nu \circ f$ y $\tilde{\nu}_f=\mu \circ f^{-1}$. Sea $\rho_X$ una distancia entre medidas probabilísticas en $X$ y $\rho_Y$ una distancia entre medidas probabilísticas en $Y$. Definimos la distancia de \textbf{Gromov-Lipschitz} con $\rho_X$ y $\rho_Y$ entre $(X,d,\mu)$ e $(Y,\delta,\nu)$ como $$d_{GL}^{\rho_X \rho_Y}((X,d,\mu),(Y,\delta,\nu))=\inf\limits_{f\in \Lambda}\{|\log dil(f)|+|\log dil(f^{-1})|+\rho_X (\mu,\tilde{\mu}_f)+\rho_Y(\nu,\tilde{\nu}_f)\}$$ donde $dil(f)= \sup_{x_1\neq x_2} \frac{\delta(f(x_1),f(x_2))}{d(x_1,x_2)}$ es el coeficiente de dilatación de $f$.
Para esta cantidad $d_{GL}^{\rho_X \rho_Y}$, probamos propiedades métricas básicas. Luego restringimos la familia de espacios y consideramos que $\rho_X$ y $\rho_Y$ son métricas de Kantorovich-Rubinstein en cada espacio, obtenemos una definición de casi-métrica $d_{GL}^{KR}((X,d,\mu),(Y,\delta,\nu))$.
Trabajo en conjunto con: Hugo Aimar (IMAL, CONICET, UNL, CCT CONICET Santa Fe, Argentina) e Ivana Gómez (IMAL, CONICET, UNL, CCT CONICET Santa Fe, Argentina)..
Referencias
[1] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, ``Concentration inequalities'', Oxford University Press, Oxford, 2013, A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
[2] Wassily Hoeffding. ``Probability inequalities for sums of bounded random variables.''J. Amer. Statist. Assoc., 58:13--30, 1963.
[3] Misha Gromov, ``Metric structures for Riemannian and non-Riemannian spaces'', Progress in Mathematics, vol. 152, Birkhäuser Boston, Inc., Boston, MA, 1999, Based on the 1981 French original.
[4] Cédric Villani. ``Optimal transport. Old and new.'' Grundlehren Math. Wiss., 338[Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 2009.