logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro