Caminantes aleatorios difusos con límites de segundo orden: un análisis asimétrico
Autores: Drakopoulos, Georgios; Kanavos, Andreas; Tsakalidis, Konstantinos
Idioma: Inglés
Editor: MDPI
Año: 2017
Acceso abierto
Artículo científico
2017
Caminantes aleatorios difusos con límites de segundo orden: un análisis asimétrico
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Grafos de borde difuso
Términos probabilísticos
Caminante aleatorio
Análisis de grafos difusos
Propiedades globales de grafos
Algoritmo de descubrimiento de comunidades
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 23
Citaciones: Sin citaciones
Los grafos borrosos de borde constituyen un paradigma de modelado esencial en un amplio espectro de dominios que van desde la inteligencia artificial hasta la neurociencia computacional y el análisis de redes sociales. Bajo este modelo, propiedades fundamentales del grafo como la longitud del borde y el diámetro del grafo se vuelven estocásticas y, como tal, se expresan en términos probabilísticos. Por lo tanto, los algoritmos para el análisis de grafos borrosos deben basarse en principios de diseño no deterministas. Uno de estos principios es Random Walker, que se basa en una entidad virtual y selecciona ya sea bordes o, como en este caso, vértices de un grafo borroso para visitar. Esto permite la estimación de propiedades globales del grafo a través de una larga secuencia de decisiones locales, convirtiéndolo en un candidato estratégico viable para el software de procesamiento de grafos que depende de bases de datos de grafos nativas como Neo4j. Como ejemplo concreto, se propone Chebyshev Walktrap, un algoritmo heurístico de descubrimiento de comunidades borrosas que se basa en estadísticas de segundo orden y en la teleportación del Random Walker, y se compara su rendimiento, expresado en términos de coherencia de la comunidad y número de visitas de vértices, con los algoritmos previamente propuestos de Markov Walktrap, Fuzzy Walktrap y Fuzzy Newman-Girvan. Para facilitar esta comparación, se utiliza una métrica basada en las métricas asimétricas del índice de Tversky y la divergencia de Kullback-Leibler.
Descripción
Los grafos borrosos de borde constituyen un paradigma de modelado esencial en un amplio espectro de dominios que van desde la inteligencia artificial hasta la neurociencia computacional y el análisis de redes sociales. Bajo este modelo, propiedades fundamentales del grafo como la longitud del borde y el diámetro del grafo se vuelven estocásticas y, como tal, se expresan en términos probabilísticos. Por lo tanto, los algoritmos para el análisis de grafos borrosos deben basarse en principios de diseño no deterministas. Uno de estos principios es Random Walker, que se basa en una entidad virtual y selecciona ya sea bordes o, como en este caso, vértices de un grafo borroso para visitar. Esto permite la estimación de propiedades globales del grafo a través de una larga secuencia de decisiones locales, convirtiéndolo en un candidato estratégico viable para el software de procesamiento de grafos que depende de bases de datos de grafos nativas como Neo4j. Como ejemplo concreto, se propone Chebyshev Walktrap, un algoritmo heurístico de descubrimiento de comunidades borrosas que se basa en estadísticas de segundo orden y en la teleportación del Random Walker, y se compara su rendimiento, expresado en términos de coherencia de la comunidad y número de visitas de vértices, con los algoritmos previamente propuestos de Markov Walktrap, Fuzzy Walktrap y Fuzzy Newman-Girvan. Para facilitar esta comparación, se utiliza una métrica basada en las métricas asimétricas del índice de Tversky y la divergencia de Kullback-Leibler.