HitSim: Un algoritmo eficiente para la computación de SimRank de fuente única y Top-k
Autores: Bai, Jing; Zhou, Junfeng; Chen, Shuotong; Du, Ming; Chen, Ziyang; Min, Mengtao
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
HitSim: Un algoritmo eficiente para la computación de SimRank de fuente única y Top-k
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Simrank
Topología de grafos
Hitsim
Algoritmo
Vértices
Eficiencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
SimRank es una métrica ampliamente utilizada para evaluar la similitud de vértices basada en la topología de grafos, con diversas aplicaciones como la minería de grafos a gran escala y el procesamiento del lenguaje natural. El objetivo del problema de consulta de SimRank de origen único y top-k es recuperar los k vértices con el mayor SimRank en relación con el vértice de origen. Sin embargo, los algoritmos existentes sufren de ineficiencia ya que requieren calcular SimRank para todos los vértices para recuperar los resultados top-k. Para abordar este problema, proponemos un algoritmo llamado HitSim que utiliza una estrategia de ramificación y acotación para la consulta de origen único y top-k. HitSim inicialmente partitiona los vértices en conjuntos distintos basados en sus longitudes de encuentro más cortas con el vértice de origen. Posteriormente, calcula un límite superior de SimRank para cada conjunto. Si el límite superior de un conjunto no es mayor que el valor mínimo de los resultados actuales top-k, HitSim poda de manera eficiente los vértices poco prometedores dentro del conjunto. Sin embargo, en escenarios donde el grafo se vuelve denso, ciertos conjuntos con grandes límites superiores pueden contener numerosos vértices con pequeño SimRank, lo que lleva a una sobrecarga redundante al procesar estos vértices. Para abordar este problema, proponemos un algoritmo optimizado llamado HitSim-OPT que calcula el límite superior de SimRank para cada vértice en lugar de cada conjunto, lo que resulta en un proceso de poda más detallado y eficiente. Los resultados experimentales realizados en seis conjuntos de datos del mundo real demuestran el rendimiento de nuestros algoritmos en la resolución eficiente del problema de consulta de origen único y top-k.
Descripción
SimRank es una métrica ampliamente utilizada para evaluar la similitud de vértices basada en la topología de grafos, con diversas aplicaciones como la minería de grafos a gran escala y el procesamiento del lenguaje natural. El objetivo del problema de consulta de SimRank de origen único y top-k es recuperar los k vértices con el mayor SimRank en relación con el vértice de origen. Sin embargo, los algoritmos existentes sufren de ineficiencia ya que requieren calcular SimRank para todos los vértices para recuperar los resultados top-k. Para abordar este problema, proponemos un algoritmo llamado HitSim que utiliza una estrategia de ramificación y acotación para la consulta de origen único y top-k. HitSim inicialmente partitiona los vértices en conjuntos distintos basados en sus longitudes de encuentro más cortas con el vértice de origen. Posteriormente, calcula un límite superior de SimRank para cada conjunto. Si el límite superior de un conjunto no es mayor que el valor mínimo de los resultados actuales top-k, HitSim poda de manera eficiente los vértices poco prometedores dentro del conjunto. Sin embargo, en escenarios donde el grafo se vuelve denso, ciertos conjuntos con grandes límites superiores pueden contener numerosos vértices con pequeño SimRank, lo que lleva a una sobrecarga redundante al procesar estos vértices. Para abordar este problema, proponemos un algoritmo optimizado llamado HitSim-OPT que calcula el límite superior de SimRank para cada vértice en lugar de cada conjunto, lo que resulta en un proceso de poda más detallado y eficiente. Los resultados experimentales realizados en seis conjuntos de datos del mundo real demuestran el rendimiento de nuestros algoritmos en la resolución eficiente del problema de consulta de origen único y top-k.