Exhaustiva explotación de algoritmos locales de siembra para detección de comunidades de manera unificada
Autores: Hu, Yanmei; Yang, Bo; Duo, Bin; Zhu, Xing
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Exhaustiva explotación de algoritmos locales de siembra para detección de comunidades de manera unificada
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Detección de comunidades
Análisis de redes
Algoritmos de siembra local
Métricas de centralidad
Resultados experimentales
Redes grandes
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
La detección de comunidades es una tarea esencial en el análisis de redes y es desafiante debido al rápido crecimiento de las escalas de red. Recientemente, descubrir comunidades desde la perspectiva local de algunos nodos especificados llamados semillas, en lugar de requerir la información global de toda la red, se ha convertido en un enfoque alternativo para abordar este desafío. Algunos algoritmos de siembra han sido propuestos en la literatura para encontrar semillas, pero muchos de ellos requieren una cantidad excesiva de esfuerzo debido a la información global o la intensa computación involucrada. En nuestro estudio, resumimos formalmente un marco unificado para la siembra local considerando solo la información local de cada nodo. En particular, tanto los algoritmos de siembra local populares como los nuevos se instancian a partir de este marco unificado mediante la adopción de diferentes métricas de centralidad. Categorizamos estos algoritmos de siembra local en tres clases y los comparamos experimentalmente en una serie de redes. Los experimentos demuestran que los algoritmos basados en el grado generalmente seleccionan menos semillas, mientras que los algoritmos basados en la densidad, excepto el que tiene la masa del nodo como métrica de centralidad, seleccionan más semillas; utilizando la conductancia del egonet como métrica de centralidad funciona mejor en descubrir comunidades de buena calidad; los algoritmos basados en el núcleo funcionan mejor en general considerando todas las métricas de evaluación; y entre los algoritmos basados en el núcleo, el que tiene el índice de Jaccard funciona mejor. Los resultados experimentales también revelan que todos los algoritmos de siembra funcionan mal en redes grandes, lo que indica que descubrir comunidades en redes grandes sigue siendo un problema abierto que necesita ser abordado con urgencia.
Descripción
La detección de comunidades es una tarea esencial en el análisis de redes y es desafiante debido al rápido crecimiento de las escalas de red. Recientemente, descubrir comunidades desde la perspectiva local de algunos nodos especificados llamados semillas, en lugar de requerir la información global de toda la red, se ha convertido en un enfoque alternativo para abordar este desafío. Algunos algoritmos de siembra han sido propuestos en la literatura para encontrar semillas, pero muchos de ellos requieren una cantidad excesiva de esfuerzo debido a la información global o la intensa computación involucrada. En nuestro estudio, resumimos formalmente un marco unificado para la siembra local considerando solo la información local de cada nodo. En particular, tanto los algoritmos de siembra local populares como los nuevos se instancian a partir de este marco unificado mediante la adopción de diferentes métricas de centralidad. Categorizamos estos algoritmos de siembra local en tres clases y los comparamos experimentalmente en una serie de redes. Los experimentos demuestran que los algoritmos basados en el grado generalmente seleccionan menos semillas, mientras que los algoritmos basados en la densidad, excepto el que tiene la masa del nodo como métrica de centralidad, seleccionan más semillas; utilizando la conductancia del egonet como métrica de centralidad funciona mejor en descubrir comunidades de buena calidad; los algoritmos basados en el núcleo funcionan mejor en general considerando todas las métricas de evaluación; y entre los algoritmos basados en el núcleo, el que tiene el índice de Jaccard funciona mejor. Los resultados experimentales también revelan que todos los algoritmos de siembra funcionan mal en redes grandes, lo que indica que descubrir comunidades en redes grandes sigue siendo un problema abierto que necesita ser abordado con urgencia.