Este artículo fue publicado como parte del Blogatón de ciencia de datos.
Introducción
La detección de comunidad en una red identifica y agrupa los nodos más densamente interconectados en un grafo dado. Este gráfico puede tomar la forma de un gráfico de red social, una red biológica o una representación de una red local de computadoras, por ejemplo. Los grupos de nodos relacionados se pueden agrupar utilizando varios algoritmos. En este artículo, ocho algoritmos de este tipo se prueban con tres conjuntos de datos y se evalúa su rendimiento.
Nota: Puede acceder al artículo completo que escribí sobre este tema y el código utilizado esta página.
Gráficos
A gráfica es una estructura de datos no lineal que modela relaciones por pares entre objetos. Un gráfico comprende nodos o vértices que están conectados por aristas o enlaces.
Un grafo no dirigido consta de enlaces simétricos, mientras que un grafo dirigido incluye enlaces asimétricos "hacia y desde" entre vértices. Los enlaces no dirigidos se pueden atravesar en cualquier dirección, mientras que los enlaces dirigidos solo se pueden atravesar en la dirección del enlace, desde el nodo de origen hasta el de destino. Un gráfico ponderado es un gráfico en el que a los enlaces se les asignan ciertos valores numéricos conocidos como pesos. Según el gráfico, estos pesos pueden representar costos, longitudes u otras cantidades.
Un ejemplo de un gráfico no dirigido son las carreteras que interconectan ciudades que se pueden atravesar en cualquier dirección. El gráfico dirigido relevante serían las rutas aéreas que conectan el mismo fijo en una dirección particular.
Los gráficos pueden modelar muchos tipos de relaciones y procesos en los sistemas de información científica. Los gráficos se pueden usar para modelar y resolver muchos problemas prácticos.
Teoría de Redes y Gráficos
Los gráficos son, por lo tanto, herramientas versátiles para representar varios modelos y, en particular, redes. La teoría de redes estudia los gráficos como una representación de relaciones simétricas o asimétricas entre objetos discretos. Una red se puede definir como un gráfico en el que los nodos y enlaces tienen atributos como nombres y donde el atributo de peso opcional representa un mundo real.
cantidad. El análisis de redes se presta a varios campos científicos como la biología, la física, la estadística, la informática, la sociología y la estadística, para derivar inferencias significativas de un almacén de datos.
El análisis de redes sociales, en particular, ha surgido como una aplicación general de los algoritmos de detección de comunidades. Con el auge de la red mundial y los sitios de redes sociales, la caracterización de las comunidades resultantes genera una gran cantidad de información sobre los patrones de comportamiento humano. Por lo tanto, existe la necesidad de algoritmos que detecten tales comunidades para que se puedan hacer más inferencias significativas a partir de ellas.
Comunidad
Una comunidad se define como un subconjunto de nodos dentro de un gráfico donde las conexiones o vínculos son más densos que el resto de la red. Se dice que una red tiene una estructura de comunidad si los nodos de la red se pueden agrupar fácilmente en conjuntos de nodos potencialmente superpuestos, de modo que
cada conjunto de nodos está densamente conectado internamente.
Las comunidades tienen importancia en una red porque brindan información sobre su entidad general. Tomando el ejemplo de una aplicación biológica, en las redes metabólicas, las comunidades corresponden a ciclos o vías. En cambio, en las redes de interacción de proteínas, las comunidades corresponden a proteínas con funcionalidad similar dentro de una célula biológica.
En las redes sociales, la existencia de comunidades generalmente afecta a varios procesos como las noticias falsas o la propagación de epidemias. Para comprender completamente y realizar estudios sobre estos procesos, las técnicas de detección comunitaria son de suma importancia.
importancia.
Algoritmos de detección de la comunidad
La detección de comunidades en una red es el proceso de identificar y agrupar los nodos más densamente interconectados en un grafo dado.
Coeficiente de agrupamiento como métrica de gráfico
El coeficiente de agrupamiento de un gráfico es una medida del grado en que los nodos de un gráfico tienden a agruparse. La evidencia sugiere que en la mayoría de los casos del mundo real
En las redes, y en particular en las redes sociales, los nodos tienden a crear comunidades muy unidas caracterizadas por una densidad de enlaces relativamente alta. Esta probabilidad tiende a ser mayor que la probabilidad media de un enlace establecido aleatoriamente entre dos nodos. Por lo tanto, el coeficiente de agrupamiento se ha utilizado en cada red que se ha probado en este artículo como un medio para tener una idea sobre su interconectividad relativa.
Modularidad como métrica CDA
La modularidad mide la estructura de una determinada red o gráfico cuando se lleva a cabo la detección de comunidades. Mide la fuerza de la división de una red en módulos (comunidades). Las redes con alta modularidad tienen conexiones densas entre los nodos dentro de los módulos pero conexiones escasas entre los nodos en diferentes módulos. El concepto de modularidad se utiliza para evaluar la partición de una red en comunidades basándose en la intuición de que las estructuras de grafos aleatorios no deben seguir una estructura de comunidad.
Punto de referencia LFR para la evaluación CDA
Cuando se trata de detectar comunidades, todavía no existe un acuerdo universal sobre cómo se ve un resultado ideal del proceso de detección de comunidades y, por extensión, la confiabilidad de los algoritmos de detección de comunidades. Aquí es donde entra en juego un modelo de red simple, el modelo de partición ℓ plantada. En este modelo, uno 'planta' una partición en un gráfico, que consta de un cierto número de grupos de nodos.
El punto de referencia LFR es un ejemplo de un modelo de partición ℓ plantado. Mejora el punto de referencia GN anterior al introducir distribuciones de ley de potencia de grado y tamaño de la comunidad. Tampoco hay restricciones sobre los grados esperados o el tamaño de la comunidad. Los gráficos de referencia LFR se pueden generar con relativa rapidez, incluso para redes extensas. Por lo tanto, tiene una ventaja sobre el punto de referencia GN y es una mejor prueba para el rendimiento de cualquier algoritmo dado. En este artículo, una red generada por el punto de referencia LFR se ha utilizado para comparar los algoritmos.
Redes utilizadas
La elección de los conjuntos de datos se ha hecho para mostrar el impacto variable de los parámetros de entrada en la salida. Se ha utilizado una red normal del mundo real, una red artificial utilizada como punto de referencia y un gráfico aleatorio para probar el funcionamiento de todos los algoritmos utilizados de manera justa.
(i) La red del Club de Karate de Zachary
En 1977, Wayne Zachary recopiló datos sobre los miembros de un club universitario de kárate. Cada nodo representa un miembro del club y cada borde representa un empate entre dos miembros. Esta es una red no dirigida del mundo real con 34 nodos (miembros) y 78 bordes. Durante este estudio, surgió una pelea entre los miembros del club, lo que llevó a su división en dos grupos. Un problema interesante que surgió fue descifrar estos dos grupos examinando la naturaleza de los enlaces con la ayuda de algoritmos de detección de la comunidad. Por lo tanto, esta es una red apta para realizar
análisis y los resultados serían notables.
(ii) red generada por LFR
Se generó una red artificial de 150 nodos y 1209 aristas siguiendo los principios del benchmark LFR. La entrada fue el número de nodos y ciertos parámetros preestablecidos; el resultado fue la lista de bordes y nodos de la red generada artificialmente. El gráfico es no dirigido y ponderado. Esta red artificial se generó específicamente para probar y comparar el rendimiento de todos los algoritmos entre sí, de ahí el nombre de referencia. Es una herramienta útil para detectar el comportamiento atípico de los algoritmos e identificar si no son confiables en comparación con los alternativos.
(iii) Gráfico aleatorio
Se generó un gráfico aleatorio no dirigido con 150 nodos y 1000 aristas usando el igrafo paquete en R. Para el mismo se utilizó el modelo de red aleatoria desarrollado por Erdős-Rényi. Las pruebas en gráficos aleatorios serían un indicador útil para medir la eficacia de los algoritmos de detección de la comunidad. Esto se debe a que la presencia de comunidades dentro de un grafo aleatorio debe ser mínima.
Esta tendencia debería reflejarse en la salida de los algoritmos. Esto es
un paso que a menudo se omite en tales análisis de algoritmos. Un buen algoritmo de detección de comunidades debería ser capaz de diferenciar entre una pseudocomunidad y una comunidad producida por una red significativa. Por lo tanto, este gráfico aleatorio se utiliza para probar los ocho algoritmos utilizados en este artículo.
Algoritmos utilizados
- Algoritmo de Girvan-Newman
- Algoritmo de propagación de etiquetas
- Algoritmo codicioso rápido
- Algoritmo Spinglass
- Algoritmo de trampa
- Algoritmo de Lovaina
- Algoritmo de mapa de información
- Algoritmo de vector propio líder
Cada uno de estos algoritmos ha sido probado contra los tres conjuntos de datos utilizados.
Implementación:
Las visualizaciones de las redes se han realizado en el lenguaje de programación R en conjunto con su IDE compañero, RStudio. La red de referencia LFR se generó con código en lenguaje C++ escrito por sus desarrolladores, Andrea Lancichinetti y Santo Fortunato.
Código
Para cargar las gráficas en la variable deseada se utilizó el siguiente código:
Red Zachary
biblioteca(igraph) net <- graph.famous("Zachary") pal2 <- rainbow(5, alpha=.5) #main graph view plot(net, vertex.color=pal2, main="Karate Club Graph")
gráfico artificial
biblioteca(igraph) nodos <- read.csv("nodes.csv", header=T, as.is=T) links <- read.csv("edges.csv", header=T, as.is=T) head(nodos) head(enlaces) net <- graph_from_data_frame(d=enlaces, vértices=nodos, dirigido=F) plot(net, vertex.color=pal2, main="LFR Graph")
Gráfico aleatorio
biblioteca(igraph) net <- erdos.renyi.game(150, 1000, type = "gnm") plot(net, vertex.color=pal2, main="Random Graph")
El siguiente código traza el algoritmo de detección de la comunidad para cada gráfico.
#Girvan Newman ceb <- cluster_edge_betweenness(net) #Community plot plot(ceb, net, main="Algoritmo Girvan-Newman") #modularidad modularidad(ceb) #sin longitud(ceb)
Resultados
Las comunidades detectadas en los tres conjuntos de datos por los diferentes algoritmos son las siguientes:
1. La red del Club de Karate de Zachary
Algoritmo de Girvan Newman
2. Gráfico LFR
3. Gráfico aleatorio
Inferencias
Al graficar los resultados del número de comunidades arrojadas y las puntuaciones de modularidad de cada algoritmo, las inferencias que se pueden hacer son interesantes.
Que sirva de referencia el número de comunidades detectadas en la Red de Karate Club. El punto de referencia LFR funciona de manera bastante consistente en la mayoría de los algoritmos, como se esperaba. Se obtiene el resultado común de 3 comunidades detectadas a excepción del algoritmo Spinglass que detecta 10 comunidades. Se detectan más comunidades en la red aleatoria que en las otras dos redes. Esto puede deberse a grupos aleatorios de nodos densamente interconectados en la red que son reconocidos por los algoritmos.
Se ve que los algoritmos de propagación de etiquetas e Infomap fallan cuando se trata de la red aleatoria, es decir, ven toda la red como una comunidad única en lugar de detectar subcomunidades discretas dentro de ella. En consecuencia, el puntaje de modularidad es 0 para estas dos instancias. Comparando los puntajes de modularidad, el benchmark LFR produce un resultado consistente. La puntuación de modularidad de 0.5509484 se obtiene para la mayoría de los algoritmos, excepto los algoritmos de propagación de etiquetas y Spinglass.
Las puntuaciones obtenidas en el benchmark LFR son más altas que las de la red Karate Club. Las puntuaciones de los algoritmos con la red aleatoria son significativamente más bajas, lo que refuerza el punto de que las comunidades detectadas en las otras redes son significativas y tienen importancia. El algoritmo Spinglass, sin embargo, es una excepción a esto. Su puntaje de modularidad en la red aleatoria es más alto que en el punto de referencia LFR.
C
Así, se han implementado los siguientes, y el rendimiento es el siguiente:
- Se probaron ocho algoritmos de detección de comunidades contra un mundo real, uno artificial y un rark.
- La red artificial se utiliza como punto de referencia para el rendimiento de los algoritmos. La red aleatoria pone a prueba si los resultados de los algoritmos son significativos o no.
- La mayoría de los algoritmos se desempeñaron consistentemente en comparación con el punto de referencia y su rendimiento fue más bajo en la red aleatoria como se esperaba.
- El algoritmo de Louvain se desempeñó mejor con la salida más consistente, mientras que el algoritmo Spinglass produjo valores atípicos y resultados poco confiables.
