Generando grafos aleatorios etiquetados y ponderados realistas
Autores: Davis, Michael Charles; Ma, Zhanyu; Liu, Weiru; Miller, Paul; Hunter, Ruth; Kee, Frank
Idioma: Inglés
Editor: MDPI
Año: 2015
Acceso abierto
Artículo científico
2015
Generando grafos aleatorios etiquetados y ponderados realistas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmos generativos
Grafos aleatorios
Redes del mundo real
Etiquetas de vértices
Pesos de aristas
Inferencia Variacional Bayesiana
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
Los algoritmos generativos para grafos aleatorios han proporcionado información sobre la estructura y evolución de las redes del mundo real. La mayoría de las redes exhiben un conjunto de propiedades bien conocidas, como distribuciones de grado con colas pesadas, agrupamiento y formación de comunidades. Por lo general, los modelos de grafos aleatorios solo consideran información estructural, pero muchas redes del mundo real también tienen vértices etiquetados y aristas ponderadas. En este artículo, presentamos un modelo generativo para grafos aleatorios con etiquetas de vértices discretas y pesos de aristas numéricos. Los pesos se representan como un conjunto de Modelos de Mezcla Beta (BMMs) con un número arbitrario de mezclas, que se aprenden de redes del mundo real. Proponemos un enfoque de Inferencia Variacional Bayesiana (VI), que proporciona una estimación precisa manteniendo tiempos de cálculo manejables. Comparamos nuestro enfoque con generadores de grafos etiquetados aleatorios de vanguardia y un enfoque anterior basado en Modelos de Mezcla Gaussiana (GMMs). Nuestros resultados nos permiten sacar conclusiones sobre la contribución de las etiquetas de vértices y los pesos de las aristas a la estructura del grafo.
Descripción
Los algoritmos generativos para grafos aleatorios han proporcionado información sobre la estructura y evolución de las redes del mundo real. La mayoría de las redes exhiben un conjunto de propiedades bien conocidas, como distribuciones de grado con colas pesadas, agrupamiento y formación de comunidades. Por lo general, los modelos de grafos aleatorios solo consideran información estructural, pero muchas redes del mundo real también tienen vértices etiquetados y aristas ponderadas. En este artículo, presentamos un modelo generativo para grafos aleatorios con etiquetas de vértices discretas y pesos de aristas numéricos. Los pesos se representan como un conjunto de Modelos de Mezcla Beta (BMMs) con un número arbitrario de mezclas, que se aprenden de redes del mundo real. Proponemos un enfoque de Inferencia Variacional Bayesiana (VI), que proporciona una estimación precisa manteniendo tiempos de cálculo manejables. Comparamos nuestro enfoque con generadores de grafos etiquetados aleatorios de vanguardia y un enfoque anterior basado en Modelos de Mezcla Gaussiana (GMMs). Nuestros resultados nos permiten sacar conclusiones sobre la contribución de las etiquetas de vértices y los pesos de las aristas a la estructura del grafo.