Modelos exponenciales para grafos aleatorios (II): modelo probabilístico

Ayer dejamos abierto el problema de la inferencia en grafos. La idea fundamental es la de suponer que un grafo determinado no es tanto un grafo en sí como una realización de un proceso aleatorio de generación de aristas entre un determinado número de nodos.

El planteamiento es análogo al que se hace con las series temporales: no es tan importante la serie en sí como el hecho de que pueda probarse que obedece a un modelo autorregresivo, ARIMA, etc.

Una serie amplia de modelos de grafos aleatorios caen dentro de los llamados modelos exponenciales. Fijado el número de vértices, la probabilidad de observar el grafo y (puede suponerse que) es

P(Y = y) = c \exp \left( \sum_A \eta_A g_A(y) \right)

donde c es una constante normalizadora, \eta_A es un parámetro (similar al de las regresiones) y g_A(y) \in \{0,1\} indica si la configuración A está o no presente en el grafo.

Una configuración es… un patrón. El concepto se comprende mejor a través de ejemplos. Y el más simple es el de una arista (que podría representar un vínculo de amistad entre Juan y Pedro). O un triángulo (Juan, Pedro y Tomás son mutuamente amigos). O cualquiera de los que aparecen en el siguiente gráfico:

El modelo probabilístico para un grafo en el que cada arista y_{ij} tiene una probabilidad dada de ocurrir sería, por lo tanto,

P(Y = y) = c \exp \left( \sum_{ij} \eta_{ij} I_{ij} \right)

donde I_{ij} indica si existe o no la arista entre los nodos i y j. Si cada arista tiene la misma probabilidad, quedaría, todavía de manera más simple,

P(Y = y) = c \exp \left( \eta L(y) \right)

donde L(y) es el número de aristas. Si se quiere estudiar si el grafo tiene tendencia a organizarse creando triángulos (es decir, que el amigo de mi amigo tiene cierta propensión a ser también mi amigo), pueden plantearse modelos del tipo

P(Y = y) = c \exp \left( \eta L(y) + \theta T(y) \right)

donde T(y) es el número de triángulos que aparecen en el grafo.

Una vez planteado el marco probabilístico, queda plantearse la estimación de los parámetros y la inferencia, que permite encontrar resupuestas a preguntas del tipo:

  • ¿muestra mi grafo una tendencia significativa a las relaciones recíprocas?
  • ¿tiende mi grafo de una manera significativa a crear triángulos, i.e., relaciones transitivas?

Queda pendiente para una futura entrada.

Un comentario sobre “Modelos exponenciales para grafos aleatorios (II): modelo probabilístico

Los comentarios están desabilitados.