Detectar la estructura sobrepuesta y jerárquica de comunidades en complejas redes
Andrea Lancichinetti, Santo Fortunato y János Kertész
Publicado el 10 de marzo de 2009 • IOP Publishing and Deutsche Physikalische Gesellschaft
New Journal of Physics
Resumen
Muchas redes en la naturaleza, la sociedad y la tecnología se caracterizan por un nivel de organización mesoscópico, con grupos de nodos que forman unidades estrechamente conectadas, llamadas comunidades o módulos, que están débilmente vinculadas entre sí. Descubrir esta estructura de comunidad es uno de los problemas más importantes en el campo de las redes complejas. Las redes a menudo muestran una organización jerárquica, con comunidades integradas en otras comunidades; además, los nodos se pueden compartir entre diferentes comunidades. Aquí, presentamos el primer algoritmo que encuentra comunidades superpuestas y la estructura jerárquica. El método se basa en la optimización local de una función de aptitud. La estructura de la comunidad se revela por los picos en el histograma de la aptitud física. La resolución puede ajustarse mediante un parámetro que permita investigar los diferentes niveles jerárquicos de la organización. Las pruebas en redes reales y artificiales dan excelentes resultados.
1. Introducción
El estudio de las redes como el 'andamio de la complejidad' ha demostrado ser muy exitoso para comprender tanto la estructura como la función de muchos sistemas naturales y artificiales [1] - [5]. Una característica común de las redes complejas es la estructura de la comunidad [6] - [9], es decir, la existencia de grupos de nodos tales que los nodos dentro de un grupo están mucho más conectados entre sí que con el resto de la red. Los módulos o las comunidades reflejan las relaciones topológicas entre los elementos del sistema subyacente y representan las entidades funcionales. Por ejemplo, las comunidades pueden ser grupos de personas relacionadas en las redes sociales [6, 10, 11], conjuntos de páginas web que tratan el mismo tema [12], categorías taxonómicas en redes tróficas [13, 14], rutas bioquímicas en redes metabólicas [15] - [17], etc. Por lo tanto, la identificación de las comunidades es de importancia central, pero sigue siendo una tarea formidable.
La solución se ve obstaculizada por el hecho de que la organización de redes en el nivel modular "mesoscópico" generalmente es altamente no trivial, por al menos dos razones. En primer lugar, a menudo existe toda una jerarquía de módulos, porque las comunidades están anidadas: las comunidades pequeñas construyen las más grandes, que a su vez se agrupan para formar otras aún más grandes, etc. Un ejemplo podría ser la organización de una empresa grande, y ha sido argumentó que la complejidad de la vida también se puede asignar a una jerarquía de redes [18]. La forma jerárquica de organización puede ser muy eficiente, y los módulos se encargan de las funciones específicas del sistema [19]. En presencia de una jerarquía, el concepto de estructura de la comunidad se vuelve más rico y exige un método que sea capaz de detectar todos los niveles modulares, no solo uno. La agrupación jerárquica es una técnica bien conocida en el análisis de redes sociales [20, 21], la biología [22] y las finanzas [23]. A partir de una partición en la que cada nodo es su propia comunidad, o todos los nodos están en la misma comunidad, se fusionan o dividen los clústeres según una medida topológica de similitud entre los nodos. De esta manera, uno construye un árbol jerárquico de particiones, llamado dendrograma. Aunque este método produce naturalmente una jerarquía de particiones, nada se conoce a priori sobre sus cualidades. La modularidad de Newman y Girvan [24] es una medida de la calidad de una partición, pero puede identificar una única partición, es decir, la que corresponde al valor más grande de la medida. Recientemente, los académicos comenzaron a enfocarse en el problema de identificar jerarquías significativas [19, 25].
Una segunda dificultad es causada por el hecho de que los nodos a menudo pertenecen a más de un módulo, lo que resulta en la superposición de comunidades [17], [26] - [29]. Por ejemplo, las personas pertenecen a diferentes comunidades sociales, dependiendo de sus familias, amigos, profesiones, pasatiempos, etc. Los nodos que pertenecen a más de una comunidad son un problema para los métodos estándar y reducen la calidad de los módulos detectados. Además, esto oculta información importante, y a menudo conduce a clasificaciones erróneas. El problema de la superposición de las comunidades se expuso en [17], donde también se ofreció una solución. El método propuesto se basa en la percolación de la camarilla: una k-clique (un subgrafo completo de k nodos) se extiende a través de la red a través de otras camarillas con k-1 nodos comunes. De esta forma, se puede llegar a un conjunto de nodos, que se identifica como una comunidad. Un nodo puede participar en más de una de esas unidades, por lo tanto, las superposiciones ocurren naturalmente. El método, sin embargo, no es adecuado para la detección de la estructura jerárquica, ya que una vez que se especifica el tamaño k de la camarilla, en su mayoría se puede recuperar una sola estructura modular. En la figura 1, mostramos distintas redes con estructura jerárquica y comunidades superpuestas, aunque debe enfatizarse que estas características a menudo ocurren simultáneamente.
Figura 1. Parte superior: una red con una estructura jerárquica. Cada uno de los cuatro grupos grandes está formado por 128 nodos y tiene una subdivisión interna en cuatro clústeres con 32 nodos. Abajo: comunidades superpuestas. Los nodos verdes están relacionados topológicamente con más grupos.
Con el fin de proporcionar la información más exhaustiva sobre la estructura modular de un grafo, un buen algoritmo debería ser capaz de detectar tanto comunidades superpuestas como jerarquías entre ellas. En este documento, presentamos un marco que cumple estas dos demandas. El método realiza una exploración local de la red, buscando la comunidad natural de cada nodo. Durante el procedimiento, los nodos se pueden visitar muchas veces, sin importar si se han asignado a una comunidad o no. De esta manera, las comunidades superpuestas se recuperan naturalmente. La variación de un parámetro de resolución, que determina el tamaño promedio de las comunidades, permite explorar todos los niveles jerárquicos de la red.
2. El método
La suposición básica detrás de nuestro algoritmo es que las comunidades son esencialmente estructuras locales, que involucran los nodos que pertenecen a los módulos mismos y como mucho un vecindario extendido de ellos. Esto es ciertamente plausible para redes grandes, donde cada nodo no depende de la mayoría de sus pares. En el grafo de enlace de la WWW, por ejemplo, uno ni siquiera tiene una percepción de qué tan grande es la red, y las comunidades temáticas se forman basándose solo en información parcial sobre el grafo. Del mismo modo, las comunidades sociales son estructuras locales sin ninguna referencia a la humanidad como un todo.
Aquí, una comunidad es un subgrafo identificado por la maximización de una propiedad o aptitud de sus nodos. Hemos probado varias opciones para la forma de la condición física y obtuvimos los mejores resultados con la expresión simple
dónde
y
son los grados totales internos y externos de los nodos del módulo
, y α es un parámetro positivo de valor real, que controla el tamaño de las comunidades. El grado interno de un módulo equivale al doble del número de enlaces internos del módulo. El grado externo es el número de enlaces que unen a cada miembro del módulo con el resto del grafo. El objetivo de este documento es determinar un subgrafo que comience en el nodo A de manera que la inclusión de un nuevo nodo o la eliminación de un nodo del subgrafo disminuya. Llamamos a este subgrafo la comunidad natural del nodo A. Esto equivale a determinar los máximos locales para la función de aptitud para un α determinado. El máximo verdadero para cada nodo corresponde trivialmente a toda la red, porque en este caso y el valor de es el más grande que la medida puede alcanzar para un α determinado. La idea de detectar comunidades mediante una optimización local de alguna métrica ya se aplicó anteriormente [26, 27, 30, 31].
Es útil introducir el concepto de aptitud del nodo. Dada una función de aptitud, la aptitud de un nodo A con respecto a un subgrafo
, se define como la variación de la aptitud del subgrafo
con y sin el nodo A, es decir.
En la ecuación (2), el símbolo (
) indica el subgrafo obtenido del módulo
con el nodo A dentro (afuera).
La comunidad natural del nodo A se identifica con el siguiente procedimiento. Supongamos que hemos cubierto un subgrafo
que incluye el nodo A. Inicialmente,
se identifica con el nodo A (
). Cada iteración del algoritmo consta de los siguientes pasos:
La comunidad natural del nodo A se identifica con el siguiente procedimiento. Supongamos que hemos cubierto un subgrafo que incluye el nodo A. Inicialmente, se identifica con el nodo A (). Cada iteración del algoritmo consta de los siguientes pasos:
1. un bucle se realiza sobre todos los nodos vecinos de
no incluidos en
;
2. se agrega el vecino con la aptitud más grande a
, produciendo un subgrafo
más grande;
3. la aptitud de cada nodo de
es recalculada;
4. si un nodo tiene una aptitud física negativa, se elimina de este
, produciendo un nuevo subgrafo
;
5. si ocurre 4, repita desde 3, de lo contrario repita desde 1 para el subgrafo
.
El proceso se detiene cuando los nodos examinados en el paso 1 tienen una aptitud física negativa (figura 2). Este procedimiento corresponde a una especie de optimización codiciosa de la función de aptitud, ya que en cada movimiento se busca el mayor aumento posible. Otras recetas pueden ser adoptadas también. Por ejemplo, uno podría retroceder los nodos con una aptitud física negativa solo cuando el clúster deja de crecer y / o incluir en el clúster el primer nodo vecino que produce un aumento de la aptitud. Dichas recetas pueden conducir a clústeres de acondicionamiento físico más altos en un tiempo más corto, y merecen investigaciones en profundidad, que dejamos para el trabajo futuro.
Figura 2. Ejemplo esquemático de comunidad natural para un nodo (punto azul celeste en la figura) según nuestra definición. Los nodos azules son los otros miembros del grupo y tienen una aptitud física positiva dentro del grupo, mientras que los nodos rojos tienen una aptitud física negativa con respecto al grupo.
Definimos una cubierta del grafo como un conjunto de clústeres de modo que cada nodo se asigna a al menos un clúster. Esta es una extensión del concepto tradicional de partición de grafos (en la cual cada nodo pertenece a un solo grupo), para tener en cuenta posibles comunidades superpuestas. En nuestro caso, detectar una cobertura equivale a descubrir la comunidad natural de cada nodo del grafo que se estudia. La forma directa de lograr esto es repetir el procedimiento anterior para cada nodo individual. Esto es, sin embargo, computacionalmente costoso. Las comunidades naturales de muchos nodos a menudo coinciden, por lo que la mayor parte del tiempo de la computadora se utiliza para redescubrir los mismos módulos una y otra vez. Una salida económica se puede resumir de la siguiente manera:
1. elige un nodo A al azar;
2. detectar la comunidad natural del nodo A;
3. elegir al azar un nodo B aún no asignado a ningún grupo;
4. detectar la comunidad natural del nodo B, explorando todos los nodos independientemente de su posible pertenencia a otros grupos;
5. repetir desde 3.
El algoritmo se detiene cuando todos los nodos han sido asignados a al menos un grupo. Nuestra receta está justificada por el siguiente argumento. Los nodos de cada comunidad se superponen con otras comunidades o no. La comunidad fue explorada alrededor de un nodo específico; si uno elige cualquiera de los otros nodos, uno recuperaría la misma comunidad o una de las posibles comunidades superpuestas. Pero este último también se puede encontrar si uno parte de nodos que se encuentran fuera de la comunidad y no se superponen con él. De esta forma, uno debería recuperar todos los módulos sin necesidad de comenzar desde cada nodo. Al mismo tiempo, se cubrirán nodos superpuestos durante la construcción de cada comunidad a la que pertenecen, ya que es posible incluir nodos ya asignados a otros módulos. Extensas pruebas numéricas muestran que la pérdida de precisión es mínima si se procede como sugerimos en lugar de encontrar la comunidad natural de todos los nodos. Observamos que el procedimiento tiene cierto grado de estocasticidad, debido a la elección aleatoria de las semillas de nodo de las cuales las comunidades están cerradas. Este problema se analiza en el apéndice A.
El parámetro α sintoniza la resolución del método. La fijación de α significa establecer la escala a la que estamos mirando la red. Los valores grandes de α producen comunidades muy pequeñas, los valores pequeños en cambio proporcionan módulos grandes. Si α es lo suficientemente pequeño, todos los nodos terminan en el mismo clúster, la red misma. Hemos encontrado que, en la mayoría de los casos, para α <0.5, solo hay una comunidad; para α> 2, uno recupera las comunidades más pequeñas. Una elección natural es α = 1, ya que es la relación entre el grado externo y el grado total de la comunidad. Esto corresponde a la llamada definición débil de comunidad introducida por Radicchi et al [32]. Encontramos que, en la mayoría de los casos, la cobertura encontrada para α = 1 es relevante, por lo que brinda información útil sobre la estructura de la comunidad real del grafo en cuestión. Mantener un valor específico de α significa restringir la resolución del método, al igual que sucede al optimizar la modularidad de Newman-Girvan [33, 34]. Sin embargo, no se puede saber a priori qué tan grandes son las comunidades, ya que esta es una de las incógnitas del problema, por lo que es necesario comparar las coberturas obtenidas a diferentes escalas.
Al variar el parámetro de resolución uno explora toda la jerarquía de las cubiertas del grafo, desde toda la red hasta los nodos individuales, lo que lleva a la información más completa sobre la estructura de la comunidad de la red. Sin embargo, el método también proporciona una forma natural de clasificar las coberturas según su relevancia. Es razonable pensar que una buena cobertura de la red es estable, es decir, que solo se puede destruir cambiando sensiblemente el valor de α para el que se recuperó. Cada portada se entrega para α que se encuentra dentro de cierto rango. Una cobertura estable estaría indicada por un amplio rango de α. Lo que necesitamos es un índice cuantitativo para etiquetar una cobertura
. Adoptaremos el valor promedio
de la aptitud de sus comunidades, es decir
donde nc es el número de módulos. La aptitud debe calcularse para un valor fijo de α (elegimos α = 1 por simplicidad), de modo que se puedan reconocer cubiertas idénticas (diferentes) por valores iguales (diferentes). Obtendremos el histograma de los valores
de las cubiertas obtenidas para diferentes valores α: las cubiertas estables se revelan mediante picos pronunciados en el histograma de aptitud física resultante. Cuanto más alto es el pico, más estable es la cobertura. De esta manera, las cubiertas se pueden clasificar según su frecuencia. Un concepto similar de estabilidad ha sido adoptado en un estudio reciente, donde se introdujo un parámetro de resolución en la modularidad de Newman-Girvan [35].
Una pregunta natural es cómo combinar comunidades jerárquicas con comunidades superpuestas, ya que el significado habitual de la jerarquía parece incompatible con la existencia de nodos compartidos entre las comunidades. Sin embargo, esto es solo aparente y la misma definición de particiones jerárquicas puede extenderse al caso de comunidades superpuestas. Decimos que hay dos coberturas
y
están
ordenados jerárquicamente, con un número
superior a
, si todos los nodos de cada comunidad de
participan (total o parcialmente) en una sola comunidad de cobertura
.
Es difícil estimar la complejidad computacional del algoritmo, ya que depende del tamaño de las comunidades y del alcance de sus superposiciones, que a su vez depende en gran medida de la red específica que se estudia junto con el valor del parámetro α. El tiempo para construir una comunidad con nodos s se escala aproximadamente como
O(s2), debido a los pasos de retroceso. Por lo tanto, una estimación aproximada de la complejidad para un valor α fijo es
O(nc
s2
), donde
nc es el número de módulos de la cubierta entregada y langs2rang el segundo momento del tamaño de la comunidad. El cuadrado proviene del ciclo de todos los nodos de una comunidad para verificar su estado físico después de cada movimiento. La complejidad del caso más desfavorable es
O(n2), donde
n es la cantidad de nodos de la red cuando las comunidades son de un tamaño comparable con
n. En general, este no es el caso, por lo que en la mayoría de las aplicaciones el algoritmo se ejecuta mucho más rápido y casi linealmente cuando las comunidades son pequeñas. La situación se muestra en la figura 3, donde trazamos el tiempo para ejecutar el algoritmo hasta su finalización para dos valores α diferentes como una función del número de nodos para los grafos Erdös-Rényi con un grado promedio de 10: la complejidad va desde la cuadrática a lineal. La complejidad total del algoritmo para realizar el análisis completo de una red también depende del número de valores α necesarios para resolver su estructura jerárquica. Cuanto mejor se muestre la jerarquía de cubiertas, mayor será el número de valores α utilizados para ejecutar el algoritmo. Si la red tiene una estructura jerárquica, como sucede a menudo en sistemas reales, el número de cubiertas crece como log n. En este caso, el número de diferentes valores α necesarios para resolver la jerarquía también es del orden de log n y el análisis completo puede llevarse a cabo muy rápidamente. Notamos que cada iteración del algoritmo para un α dado es independiente de los otros. Entonces, el cálculo se puede paralelizar trivialmente ejecutando diferentes valores α en cada computadora. Si no se dispone de grandes recursos informáticos, una manera económica de proceder podría ser comenzar desde un gran valor α, para el cual el algoritmo se ejecuta hasta su finalización en un tiempo muy corto, y usar la cubierta final como configuración inicial para una ejecución en un valor α ligeramente menor. Dado que la cubierta correspondiente es similar a la inicial, la segunda carrera también se completará en un tiempo corto y uno puede repetir el procedimiento hasta la izquierda del rango de α.
Figura 3. Complejidad computacional del algoritmo. Las dos curvas muestran cómo el tiempo para ejecutar el algoritmo se escala con el tamaño del grafo para redes Erdös-Rényi con un grado promedio de 10 para α = 0.9 y 1.6, respectivamente. La complejidad varía desde cuadrático para α = 0.9, para el cual las comunidades son considerables, hasta lineal para α = 1.6, para el cual las comunidades son pequeñas.
Concluimos que para las redes jerárquicas nuestro procedimiento tiene una complejidad computacional del peor caso de
O(n2log n). Observamos que, si bien es cierto que actualmente varios algoritmos tienen una complejidad menor, ninguno de ellos es capaz de llevar a cabo un análisis completo de la estructura jerárquica de la comunidad, ya que generalmente ofrecen una única partición. Por lo tanto, una comparación justa no es posible. Además, otras recetas para la optimización local de nuestra u otras funciones de acondicionamiento físico pueden reducir considerablemente la complejidad computacional del algoritmo, lo que parece una prometedora dirección de investigación para el futuro.
3. Resultados
Probamos ampliamente nuestro método en redes artificiales con una estructura de comunidad jerárquica incorporada. Adoptamos una referencia similar a la propuesta recientemente por Arenas et al [36, 37], que es una simple extensión de la referencia clásica propuesta por Girvan y Newman [6]. Hay 512 nodos, organizados en 16 grupos de 32 nodos cada uno. Los 16 grupos están ordenados en cuatro supergrupos. Cada nodo tiene un promedio de enlaces
k1 con los 31 socios de su grupo y enlaces
k2 con los 96 nodos de otros tres grupos dentro del mismo supergrupo. Además, cada nodo tiene un número
k3 de enlaces con el resto de la red. De esta forma, surgen dos niveles jerárquicos: uno que consta de los 16 grupos pequeños y uno de los supergrupos con 128 nodos cada uno (la figura 1 (arriba) es un ejemplo). El grado de mezcla de los cuatro supergrupos se expresa mediante el parámetro
k3 que sintonizamos libremente. En principio, también podríamos sintonizar la mezcla de las pequeñas comunidades, variando la relación
k1 /
k2, pero preferimos establecer
k1 =
k2 = 16, de modo que las microcomunidades sean "borrosas", es decir, bien mezcladas entre sí. , y plantear una dura prueba para nuestro método.
Tenemos que verificar si la jerarquía incorporada se recupera a través del algoritmo. Esto, en general, depende del parámetro
k3. Por lo tanto, consideramos diferentes valores de
k3: para cada valor, construimos 100 realizaciones de la red. Para comparar la estructura modular incorporada con la proporcionada por el algoritmo, adoptamos la información mutua normalizada, una medida de similitud tomada de la teoría de la información, que ha demostrado ser confiable [38]. La extensión de la medida a la superposición de comunidades no es trivial y existen varias alternativas. Nuestra extensión se analiza en el apéndice B. En la figura 4, trazamos el valor promedio de la información mutua normalizada como una función de
k3 para los dos niveles jerárquicos. Vemos que en ambos casos los resultados son muy buenos. La cobertura en los cuatro supergrupos o macrocomunidades está identificada correctamente para
k3 <24, con muy pocas excepciones, y el algoritmo comienza a fallar solo cuando
k3 ~ 32, es decir, cuando cada nodo tiene 32 enlaces dentro y 32 fuera de su macro- comunidad, que luego se mezcla bien con los demás. El rendimiento también es muy bueno para el nivel jerárquico inferior: los módulos siempre están bien mezclados entre sí, ya que
k1 =
k2 = 16 para cualquier valor de
k3, por lo que es notable que la estructura modular resultante encontrada por el algoritmo esté todavía tan cerca de la estructura modular incorporada, hasta
k3 ~ 32. El principal problema con este tipo de pruebas es que no se cuenta con información independiente sobre las cubiertas, por lo tanto, solo se puede juzgar si son razonables o no. Afortunadamente, para algunas redes, las cubiertas se identificaron con información especial sobre el sistema y / o su historial. En la figura 5, mostramos los histogramas de fitness correspondientes a algunas de estas redes, a menudo utilizados para probar algoritmos: el club de karate Zachary [39] (panel superior izquierdo), la red de delfines de Lusseau [40] (panel superior derecho) y el red de equipos de fútbol americano universitario [6] (panel inferior izquierdo). La red social de miembros del club de karate estudiada por el sociólogo Wayne Zachary se ha convertido en un punto de referencia para todos los métodos de detección comunitaria. La red consta de 34 nodos, que se separaron en dos grupos distintos debido a un contraste entre uno de los instructores y el administrador del club. La pregunta es si uno es capaz de detectar la fisión social de la red. La segunda red representa las interacciones sociales de los delfines mulares que viven en Doubtful Sound, Nueva Zelanda. La red fue estudiada por el biólogo David Lusseau, quien dividió los delfines en dos grupos según su edad. El tercer ejemplo es la red de equipos de fútbol americano universitario. Aquí, hay 115 nodos, que representan a los equipos, y dos nodos están conectados si sus equipos juegan uno contra el otro. Los equipos están divididos en 12 conferencias. Los juegos entre equipos en la misma conferencia son más frecuentes que los juegos entre equipos de diferentes conferencias, por lo que uno tiene una cobertura natural donde las comunidades corresponden a las conferencias.
Figura 4. Prueba de la precisión de nuestro método en un punto de referencia jerárquico. La información mutua normalizada se usa para comparar la cobertura encontrada por el algoritmo con la cobertura natural de la red en cada nivel. En el nivel superior (círculos), las comunidades son cuatro clusters, cada uno de los cuales incluye 32 nodos, para un total de 128 nodos por clúster. Nuestro método encuentra los grupos correctos siempre que no estén bien mezclados entre sí. En el nivel inferior (cuadrados), las comunidades son 16 grupos de 32 nodos cada uno. El método funciona muy bien, teniendo en cuenta que cada nodo tiene tantos enlaces dentro como fuera de cada microcomunidad, para cualquier valor de k3. La línea vertical punteada marca las configuraciones de grafo para las cuales el número de enlaces de cada nodo dentro de su macrocomunidad es igual a la cantidad de enlaces que conectan el nodo con las otras tres macrocomunidades.
Figura 5. Análisis de redes reales. Los histogramas de aptitud corresponden al club de karate de Zachary (panel superior izquierdo), la red de delfines de Lusseau (panel superior derecho) y la red de equipos de fútbol americano universitario (panel inferior izquierdo). Los picos más altos indican las mejores coberturas, que coinciden con las coberturas naturales de los grafos, a excepción del club de karate de Zachary, donde corresponde a la misma división en cuatro clústers encontrados a través de la optimización de la modularidad. Sin embargo, la cobertura social en dos de las redes es la tercera tapa más relevante. En el panel inferior derecho, mostramos el histograma de fitness para un grafo aleatorio Erdös-Rényi con 100 nodos y el mismo grado promedio que la red de equipos de fútbol americano universitario: no hay una estructura visible, como se esperaba.
Los picos pronunciados en los histogramas de la figura 5 muestran que estas redes sí tienen estructura de comunidad. Para la red de Zachary, encontramos que la cubierta más estable consiste en cuatro clusters. Incluso si esto no es lo que a uno le gustaría recuperar, hacemos hincapié en que esta cobertura a menudo se encuentra por otros métodos, como la optimización de la modularidad, que indica que es topológicamente significativo. Pero nuestro método puede funcionar mejor: la división social en dos grupos (figura 6 (a)) resulta ser un nivel jerárquico más alto, dado por una fusión por pares de las cuatro comunidades de la cobertura principal. Curiosamente, encontramos que los dos grupos se superponen y comparten algunos nodos. Para la red de delfines, el pico más alto corresponde a la subdivisión de Lusseau de la población de animales en dos comunidades, con cierta superposición entre los dos grupos (figura 6 (b)). De manera similar, el pico más alto en la figura 5 (panel inferior izquierdo) corresponde a la partición natural de los equipos en conferencias.
Figura 6. (a) club de karate de Zachary. Mostramos los niveles jerárquicos correspondientes a la cobertura en dos grupos (0,76 <α <0,84). Los nodos 3, 9, 10, 14 y 31 se comparten entre los dos grupos: dichos nodos a menudo se clasifican erróneamente mediante algoritmos tradicionales. Los nodos superpuestos reflejan la fisión social observada por Zachary, ilustrada por los cuadrados y los círculos en la figura. (b) La red de delfines mulares de Lusseau. La mejor cobertura en dos conglomerados que encontramos (0,77 <α <0,82) concuerda con la separación observada por Lusseau (cuadrados y círculos en la figura). Los nodos 8, 20, 29, 31 y 40 se comparten entre los dos grupos.
Para verificar qué tan bueno es nuestro algoritmo en comparación con otros métodos, hemos analizado el karate, los delfines y las redes de fútbol americano universitario con el método de filtración de camarilla (CPM) de Palla et al [17]. Los valores de la información mutua normalizada de las coberturas encontradas por el algoritmo con respecto a las coberturas reales son 0.690 (nuestro método) y 0.170 (CPM) para el club de karate, 0.781 (nuestro método) y 0.254 (CPM) para los delfines. red, y 0.754 (nuestro método) y 0.697 (CPM) para la red de fútbol americano universitario. Por lo tanto, nuestro método es superior al CPM en estos casos. Por otro lado, el CPM funciona mejor para redes con muchas camarillas. Un ejemplo está representado por la palabra asociación de red construida en la Asociación de Normas Libres de la Universidad del Sur de la Florida [41], analizada en [17]. El CPM encuentra grupos de palabras que corresponden a categorías bien definidas, mientras que con nuestro método las categorías son más mixtas. Una razón importante de esta discrepancia es que nuestro método recupera nodos superpuestos que generalmente se encuentran en el límite entre comunidades, mientras que en la red de asociación de palabras a menudo son nodos centrales de una comunidad. Por ejemplo, la palabra "color" es el eje central de la comunidad de colores, pero también pertenece a otras categorías como "astronomía" y "luz".
Realizamos pruebas en muchos otros sistemas reales, incluidas redes de interacción de proteínas, redes de colaboración científica y otras redes sociales. En todos los casos, encontramos portadas razonables. Por otro lado, encontramos que los grafos aleatorios no tienen una estructura de comunidad natural, ya que las cubiertas son inestables (figura 5 (panel inferior derecho)). Esto es notable, ya que se sabe que otros enfoques también pueden encontrar cubiertas en grafos aleatorios [42], un problema que desencadenó un debate en curso sobre cuándo una portada es de hecho relevante [43].
En la figura 7, mostramos cómo el grado de superposición entre las comunidades depende del parámetro de resolución α, para tres redes reales. A partir de la figura, no es posible inferir ninguna dependencia sistemática de la superposición en α, el patrón depende en gran medida de la topología de grafo específica.
Figura 7. Fracción de nodos superpuestos como una función de α para las tres redes reales discutidas en la figura 5: el club de karate de Zachary y las redes de delfines y equipos de fútbol americano. No existe un patrón único, la extensión de la superposición no muestra una variación sistemática con α.
Concluimos la sección con un análisis de las propiedades estadísticas de la estructura de la comunidad en grafos. La Figura 8 muestra la distribución de tamaños de comunidad para una muestra del grafo de enlace WWW, correspondiente al subconjunto de páginas web dentro del dominio .gov. Analizamos el componente conectado más grande del grafo, que consta de 774 908 nodos y 4 711 340 enlaces. La figura hace referencia a la cubierta encontrada para α = 1, que se identificó en menos de 40 h de tiempo de CPU en una PC pequeña. La distribución del tamaño de la comunidad está sesgada, con una cola que sigue una ley de poder con el exponente 2.2 (1). El resultado es consistente con los análisis previos de distribuciones de tamaño de la comunidad en grafos grandes [8, 17, 44, 45], aunque este es el primer resultado relacionado con la WWW. Hacemos hincapié en que no hemos realizado un análisis completo de esta red, ya que requeriría una gran cantidad de procesadores para llevar a cabo el alto número de ejecuciones en diferentes valores α que son necesarios para un análisis confiable. Por lo tanto, la distribución en la figura 8 no corresponde necesariamente a la cobertura más significativa. Sin embargo, los valores α de las cubiertas más representativas de todas las redes que hemos considerado resultaron cercanas a 1, por lo que es probable que la gráfica de la figura 8 sea una aproximación aproximada de la distribución real.
Figura 8. Distribución de tamaños de comunidad para el grafo de enlace correspondiente al dominio .gov de la WWW. El parámetro de resolución α = 1. La distribución es claramente sesgada, de acuerdo con hallazgos previos en grafos grandes. La cola puede ajustarse bien mediante una ley de potencia con el exponente 2.2 (1) (línea discontinua en la figura).
4. Conclusiones
En este documento, presentamos el primer método que descubre simultáneamente tanto la estructura jerárquica como la estructura de comunidad superpuesta de redes complejas. El método consiste en encontrar los máximos locales de una función de aptitud mediante búsqueda iterativa local. El procedimiento permite que cada nodo se incluya en más de un módulo, lo que lleva a una descripción natural de comunidades superpuestas. Finalmente, ajustando el parámetro de resolución α se puede sondear la red a diferentes escalas, explorando la posible jerarquía de la estructura de la comunidad. La aplicación de nuestro método a varias redes construidas y empíricas ha dado excelentes resultados.
Nos gustaría hacer hincapié en que nuestro método proporciona un marco general que produce una gran clase de algoritmos. Por ejemplo, uno podría elegir una expresión diferente para la función de aptitud, otro criterio para definir la cubierta más significativa, o un procedimiento de optimización diferente de la aptitud para un solo grupo. La configuración que hemos probado demuestra ser muy confiable, pero no podemos excluir que las diferentes opciones rindan incluso mejores resultados. De hecho, el marco es tan flexible que se puede adaptar fácilmente al problema en cuestión: si uno tiene pistas sobre la topología de las comunidades que se encuentran para un sistema específico, esta información puede usarse para diseñar una función de acondicionamiento físico particular, teniendo en cuenta las características requeridas de los módulos.
Dado que el análisis completo de la estructura de la comunidad de una red se puede llevar a cabo simultáneamente en muchas computadoras, el límite de tamaño superior de los grafos tratables puede aumentar considerablemente. Nuestro método brinda la oportunidad de estudiar sistemáticamente la distribución de tamaños de comunidades de redes grandes hasta millones de nodos, un aspecto crucial de la organización interna de un grafo, que los estudiosos recién han empezado a examinar. Un subproducto interesante de nuestra técnica es la posibilidad de cuantificar la participación de nodos superpuestos en sus comunidades por los valores de su aptitud (nodo) con respecto a cada grupo al que pertenecen.
Finalmente, nos gustaría mencionar que el método puede extenderse naturalmente a redes ponderadas, es decir, redes donde los enlaces tienen un peso. No es necesario utilizar ningún tipo de umbralización [46], ya que la generalización de la fórmula de aptitud es sencilla: en la ecuación (1), tenemos que reemplazar el grado k con la fuerza correspondiente s (expresando la suma sobre los enlaces ' pesos). Las aplicaciones a las redes dirigidas también se pueden diseñar fácilmente con opciones adecuadas de la función de aptitud. Nuestra propia función (1) podría extenderse al caso dirigido, ya que considera el grado de los nodos de un subgrafo: es plausible suponer que el grado total de los nodos del subgrafo debido a enlaces internos al subgrafo excede el grado total de grado entrante producido por enlaces provenientes de nodos externos, si el subgrafo es una comunidad.
