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
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
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.
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.