Algoritmia/Estructuras comunitarias

Las redes complejas naturales, sociales y tecnológicas exhiben, de manera emergente, una estructura modular (o comunitaria) en la que la mayoría de los entes que definen la red se agrupan en conglomerados con alta densidad de enlaces entre ellos, con respecto al resto de los nodos de la red. Dichos conglomerados, llamados comunidades, están relacionados con unidades funcionales en redes metabólicas y de interacción proteína-proteína, con regiones de propagación acelerada de enfermedades en redes de transporte, con funciones cognitivas en redes neuronales, etc. A pesar de la inmensa cantidad de trabajos relacionados con el problema de la detección de comunidades, no hay un consenso de lo que es una comunidad. Sin embargo, la noción de comunidad y las primeras formalizaciones de este concepto, para el caso de las redes, fueron propuestas dentro de las ciencias sociales.

Estructura comunitaria de la red del club de karate de Zachary, obtenida con el método de optimización voraz de Newman.

Definición de Estructura Comunitaria o Comunidad

Sea $R=(N,E)$ una red, donde $N$ es el conjunto de nodos de la red, y $E$ el conjunto de enlaces:

i) Una comunidad (agrupamiento, o grupo cohesivo) es una subred $R(N,E)$ cuyos nodos están densamente conectados, i.e., es cohesiva. La diversidad de formas en las que se puede medir el nivel de cohesión estructural de los nodos de una subred $R$ ha producido diversas metodologías de detección de comunidades.

ii) Una comunidad es una subred $R(N,E)$, cuyos nodos son altamente similares con respecto al resto de los nodos de la red. La similitud entre dos nodos puede medirse de diferentes formas, e.g., dos nodos son similares si la fracción de vecinos comunes es alta o si tienden a aparecer juntos cuando se coloca un paseo aleatorio sobre la red original. De manera análoga a la definición anterior, existen muchas medidas de similitud entre nodos, y por tanto muchos métodos asociados a dichas medidas.

Detección de Estructuras Comunitarias

Generalmente, detectar una comunidad en una red compleja es sumamente costoso computacionalmente y solo gracias a los métodos heurísticos ad hoc se ha logrado atacar este problema satisfactoriamente. Esto, junto con la necesidad de clasificar los nodos siguiendo requerimientos particulares (e.g., dos nodos están en una misma comunidad si comparten muchos vecinos o si están conectados y el enlace es un intermediario débil) justifican hasta cierto punto la enorme diversidad de métodos existentes.

Métodos de Detección de Estructuras Comunitarias

Función de Modularidad de Newman

La medida de calidad más popular en la literatura es la función de modularidad de Newman y Girvan. Esta se basa en la idea de que en una red aleatoria no se esperan estructuras comunitarias. Así, la existencia de posibles comunidades se manifiesta por la comparación entre la densidad de enlaces en una subred y la densidad que uno esperaría que tuviese la subred si sus enlaces fueran reconectados independientemente de la estructura comunitaria, e.g. de manera uniformemente aleatoria. Esta densidad de enlace esperada depende del modelo nulo elegido, i.e., una versión de la red que mantenga algunas de sus propiedades estructurales pero sin estructura comunitaria. La modularidad puede entonces escribirse como sigue:

$Q={\dfrac {1}{2m}}\sum _{ij}(A_{ij}-P_{ij})\delta _{C_{i},C_{j}}$

donde la suma recorre todos los pares de nodos, $A$ es la matriz de adyacencia, $m$ es el número total de enlaces de la red y $P_{ij}$ representa el número esperado de enlaces entre el nodo $i$ y el nodo $j$ en el modelo nulo. La función $\delta$ toma el valor $1$ si los nodos $i$ y $j$ están en la misma comunidad, i.e., si $C_{i}=C_{j}$, y cero en otro caso. La elección del modelo nulo es en principio arbitraria y existen varias posibilidades. Por ejemplo, uno podría simplemente demandar que la red mantenga el mismo número de enlaces que la red original o que los enlaces se coloquen con la misma probabilidad para todo par de nodos (un grafo de Erdös-Rényi), en este caso, el término del modelo nulo en la ecuación anterior sería constante, (i.e., $P_{ij}=p=2m/[n(n-1)],\forall i,j$). Sin embargo, este modelo nulo no es un buen descriptor para una red real, pues como ya se ha mencionado, su distribución de grado difiere notablemente de las distribuciones sesgadas encontradas en redes reales. Debido a las implicaciones importantes que una distribución de grado de cola larga tiene sobre la estructura y función de una red real, es preferible usar un modelo nulo con la misma distribución de grado que la red original. El modelo nulo estándar para la modularidad impone que la sucesión de grado esperada (después de promediar sobre todas las posibles configuraciones del modelo nulo) concuerde con la sucesión de grado actual de la red. Esta es una restricción más estricta y esencialmente el modelo nulo ser\'a equivalente al modelo de las configuraciones.

Método de Remoción de Enlaces de Girvan y Newman

El algoritmo de Girvan y Newman es uno de los métodos de detección de comunidades más populares en la literatura. El algoritmo se basa en el cálculo de la intermediación (o centralidad) de los enlaces presentes en la red ubicando a los que son intermediarios entre comunidades, para luego detectar dichas comunidades mediante la remoción progresiva de dichos enlaces. Generalmente se utiliza el coeficiente de intermediación de enlace, definido por:

${\mathcal {B}}(i)={\underset {j\neq k}{\sum _{j,k\in {\mathcal {N}}}}}{\frac {\gamma _{jk}(i)}{\gamma _{jk}}},$

donde $\gamma _{jk}$ es el número de caminos más cortos entre el nodo $j$ y el nodo $k$ y $\gamma _{jk}(i)$ es el número de caminos más cortos que van desde el nodo $j$ hasta el nodo $k$ y que pasan a través del nodo $i$. Si la red posee comunidades con pocas conexiones entre ellas, entonces todos los caminos más cortos entre diferentes comunidades pasarán a través de esos pocos enlaces, los cuales terminarán por tener los valores más altos de intermediación. Removiendo estos enlaces progresivamente, los grupos se separan unos de otros y la estructura comunitaria subyacente es revelada. Luego de cada remoción, se mide la modularidad de la partición definida por las componentes conexas de la red, a través de la función de modularidad de Newman.

Optimización directa de la Función de Modularidad

Uno de los métodos más ampliamente utilizados para la detección de estructuras comunitarias es la maximización directa de la función de modularidad. La modularidad es una función de calidad que mide que tan buena es una partición del conjunto de nodos de una red en terminos de densidad de enlaces, i.e., entre mayor sea la densidad de enlaces internos que posee una comunidad y menos sea el número de enlaces entre comunidades, mayor será la modularidad de la partición. El método de maximización directa de la modularidad permite detectar comunidades mediante la búsqueda sobre el espacio de todas las posibles particiones del conjunto de nodos de la red, quedándose en la exploración de dicho espacio con las particiones que alcancen el mayor valor de modularidad posible. La búsqueda exhaustiva sobre todas las particiones posibles es en general intratable (pues el número de particiones posibles va como los Números de Bell). Sin embargo, existe un conjunto de algoritmos prácticos (basados en esquemas propios de optimización combinatoria) tales como: optimización voraz, recocido simulado, optimización espectral, con diferencias particulares en velocidad y precisión. Uno de los enfoques más populares de maximización de la modularidad es el método de Louvain (llamado así por la universidad de Louvain), el cual es un método iterativo que optimiza comunidades locales hasta llegar a la estructura comunitaria global. Sin embargo, la optimización directa de la función de modularidad es cuestionable, ya que se ha demostrado que a menudo falla en el caso de comunidades pequeñas en redes muy grandes (problema de escala), conocido como límite de resolución.

Disimilitudes nodales y agrupamiento jerárquico

Otro método para encontrar estructuras comunitarias en redes complejas es el método de agrupamiento jerarquico. En este método uno define una medida de similitud (usualmente topológica) entre pares de nodos. Medidas comúnmente utilizadas son: el coeficiente de Jaccard, el coeficiente de solapamiento topológico o variantes del coeficiente de correlación de Pearson, entre muchos otros. Luego, los nodos con mayor similitud son agrupados en comunidades, de acuerdo con estas medidas. Hay varias estrategias para ejecutar la tarea de agrupamiento, entre ellas están los esquemas de enlazado simple, enlazado promedio, y enlazado completo. Un enfoque reciente en esta dirección es utilizar la información de varias medidas de similitud no correlacionadas para crear medidas más sensibles, a través de la suma convexa de medidas lo que ha mostrado mejorar considerablemente este tipo de metodología.

Véase también

• Centralidad
• Minería de Grafos