logo móvil
Contáctanos

Detección de comunidad lista para NISQ basada en identificación de nodos de separación

Autores: Stein, Jonas; Ott, Dominik; Nüßlein, Jonas; Bucher, David; Schönfeld, Mirco; Feld, Sebastian

Idioma: Inglés

Editor: MDPI

Año: 2023

Descargar PDF

Acceso abierto

Artículo científico
2023

Detección de comunidad lista para NISQ basada en identificación de nodos de separación


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Estructura de red
Detección de comunidades
Soluciones heurísticas
Computación cuántica
Enfoque basado en QUBO
Nodos de separación

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 53

Citaciones: Sin citaciones


Descripción
El análisis de la estructura de redes es esencial para muchas áreas científicas que van desde la biología hasta la sociología. Dado que la tarea computacional de agrupar estas redes en particiones, es decir, resolver el problema de detección de comunidades, suele ser NP-duro, las soluciones heurísticas son indispensables. La exploración de heurísticas expeditivas ha llevado al desarrollo de enfoques particularmente prometedores en la tecnología emergente de la computación cuántica. Motivados por las sustanciales demandas de hardware de todos los enfoques establecidos de detección de comunidades cuánticas, presentamos un enfoque novedoso basado en QUBO que solo necesita qubits de número de nodos y está representado por una matriz QUBO tan dispersa como la matriz de adyacencia del grafo de entrada. La mejora sustancial en la dispersión de la matriz QUBO, que suele ser muy densa en trabajos relacionados, se logra a través del novedoso concepto de nodos de separación. En lugar de asignar cada nodo a una comunidad directamente, este enfoque se basa en la identificación de un nodo de separación, que, al eliminarse del grafo, produce un conjunto de componentes conectados que representan los núcleos de las comunidades. Empleando una heurística codiciosa para asignar los nodos de los conjuntos de nodos de separación a los núcleos de comunidades identificados, los resultados experimentales subsecuentes demuestran un concepto al lograr una calidad de solución óptima de hasta el 95% en tres conjuntos de datos de referencia del mundo real establecidos. Este trabajo muestra un enfoque prometedor para la detección de comunidades cuánticas listas para NISQ, catalizando la aplicación de computadoras cuánticas para el análisis de la estructura de redes de instancias de problemas del mundo real a gran escala.

Otros recursos que podrían interesarte

Temas Virtualpro