b'\n_START_ARTICLE_\nEstructura de comunidades\n_START_PARAGRAPH_\nEn el estudio de redes complejas, se dice que una red tiene estructura de comunidades si los nodos de la red pueden ser f\xc3\xa1cilmente agrupados en grupos de nodos, potencialmente superpuestos. En el caso particular de buscar comunidades no superpuestas, la red se divide de forma natural en grupos de nodos densamente conectados internamente y con pocas conexiones entre grupos. La definici\xc3\xb3n m\xc3\xa1s general est\xc3\xa1 basada en el principio de que un par de nodos tiene mayor probabilidad de estar conectado si ambos son miembros de la(s) misma(s) comunidad(es), y menor probabilidad de estar conectado si no comparten comunidades.\n_START_SECTION_\nPropiedades\n_START_PARAGRAPH_\nEn el estudio de redes, tales como redes de computadoras e informaci\xc3\xb3n, redes sociales y redes biol\xc3\xb3gicas, se han observado m\xc3\xbaltiples caracter\xc3\xadsticas que ocurren com\xc3\xbanmente, incluyendo la propiedad del mundo peque\xc3\xb1o, larga cola de la distribuci\xc3\xb3n de grado y agrupamiento, entre otros. Otra caracter\xc3\xadstica com\xc3\xban es estructura de comunidades\xe2\x80\x8b_NEWLINE_\xe2\x80\x8b_NEWLINE_\xe2\x80\x8b_NEWLINE_.\xe2\x80\x8b En el contexto de redes, la estructura de comunidades se refiere a la ocurrencia de grupos de nodos en una red que son m\xc3\xa1s densamente conectados internamente que el resto de la red, como se muestra en la imagen de ejemplo a la derecha. Esta heterogeneidad de las conexiones sugiere que la red tiene ciertas divisiones naturales._NEWLINE_Las comunidades son a menudo definidas en t\xc3\xa9rminos de la partici\xc3\xb3n del conjunto de v\xc3\xa9rtices, es decir, cada nodo pertenece a una y s\xc3\xb3lo a una comunidad, como en la figura. Esto es una simplificaci\xc3\xb3n \xc3\xbatil y la mayor parte de los m\xc3\xa9todos de detecci\xc3\xb3n de comunidades encuentran este tipo de estructura de comunidades. Aun as\xc3\xad en algunos casos una representaci\xc3\xb3n mejor podr\xc3\xada ser una d\xc3\xb3nde los v\xc3\xa9rtices pertenezcan a m\xc3\xa1s de una comunidad.  Esto podr\xc3\xada pasar en una red social donde cada v\xc3\xa9rtice represente una persona, y las comunidades representen diferentes grupos de amigos: una para familia, otra para compa\xc3\xb1eros de trabajo, una para amigos en el mismo club deportivo, y as\xc3\xad sucesivamente. El uso de cliques para detectar comunidades, explicado m\xc3\xa1s adelante, es un ejemplo de c\xc3\xb3mo pueden ser encontradas estas comunidades con superposici\xc3\xb3n._NEWLINE_Existen redes que no tienen ninguna estructura de comunidades significativa.  Muchos modelos de red b\xc3\xa1sicos, como por ejemplo grafos aleatorios y el modelo Barab\xc3\xa1si\xe2\x80\x93Albert, no muestran estructura de comunidades.\n_START_SECTION_\nAplicaciones\n_START_PARAGRAPH_\nLa estructura de comunidades es bastante com\xc3\xban en redes reales. Las redes sociales incluyen grupos comunitarios (el origen del t\xc3\xa9rmino, de hecho) basados en ubicaciones comunes, intereses comunes, ocupaciones comunes, etc.\xe2\x80\x8b  Las redes metab\xc3\xb3licas tienen comunidades basadas en grupos funcionales. En las redes de citaciones se forman comunidades por temas de investigaci\xc3\xb3n.\xe2\x80\x8b  Ser capaz de identificar estas sub-estructuras dentro de una red puede ayudar a entender de forma intuitiva c\xc3\xb3mo el funcionamiento de la red y su topolog\xc3\xada se afectan el uno al otro. Tal intuici\xc3\xb3n puede ser \xc3\xbatil en mejorar algunos algoritmos sobre grafos tales como agrupamiento espectral.\xe2\x80\x8b\n_START_SECTION_\nAlgoritmos para encontrar comunidades\n_START_PARAGRAPH_\nEncontrar comunidades en una red aleatoria puede ser una tarea computacionalmente dif\xc3\xadcil. El n\xc3\xbamero de comunidades en la red (si hay alguna) es usualmente desconocido y, a menudo, las comunidades tienen diferente tama\xc3\xb1o y/o densidad. A pesar de estas dificultades, m\xc3\xbaltiples m\xc3\xa9todos de detecci\xc3\xb3n de comunidades han sido desarrollados y empleados con diferentes niveles de \xc3\xa9xito.\xe2\x80\x8b\n_START_SECTION_\nM\xc3\xa9todo de corte m\xc3\xadnimo\n_START_PARAGRAPH_\nUno de los algoritmos m\xc3\xa1s antiguos para dividir redes es el m\xc3\xa9todo de corte m\xc3\xadnimo (y variantes como corte de proporci\xc3\xb3n y corte normalizado).  Este m\xc3\xa9todo se usa, por ejemplo, _NEWLINE_para equilibrar la carga del c\xc3\xa1lculo en paralelo con el fin de minimizar la comunicaci\xc3\xb3n entre los nodos del procesador._NEWLINE_En el m\xc3\xa9todo de corte m\xc3\xadnimo, la red est\xc3\xa1 dividida en un n\xc3\xbamero predeterminado de partes, normalmente de aproximadamente el mismo tama\xc3\xb1o, que se escogen de forma tal que el n\xc3\xbamero de las aristas entre grupos sea m\xc3\xadnimo. El m\xc3\xa9todo funciona bien en muchas aplicaciones para las cuales fue inicialmente concebido pero es menos adecuado para encontrar estructura de comunidades en redes generales pues encontrar\xc3\xa1 comunidades sin importar si est\xc3\xa1n impl\xc3\xadcitas en la estructura, y solo encontrar\xc3\xa1 un n\xc3\xbamero fijo de comunidades.\xe2\x80\x8b\n_START_SECTION_\nAgrupamiento jer\xc3\xa1rquico\n_START_PARAGRAPH_\nOtro m\xc3\xa9todo para detectar estructuras de comunidades es el agrupamiento jer\xc3\xa1rquico.  En el cual se define una medida de similitud que cuantifica alg\xc3\xban tipo (usualmente topol\xc3\xb3gico) de similitud entre pares de nodos. Algunas de las medidas m\xc3\xa1s usadas son similitud coseno, el \xc3\xadndice de Jaccard, y la distancia Hamming entre filas de la matriz de adyacencia. Luego se agrupan los nodos similares en comunidades de acuerdo a dicha medida. Existen varios esquemas comunes para realizar el agrupamiento, los dos m\xc3\xa1s sencillos son\xcb\x90 agrupamiento de enlace-simple, en el cual se considera que dos grupos son comunidades separadas si y solo si para todo par de nodos en diferentes grupos la similitud es menor que un umbral, y agrupamiento de enlace-comleto, en el cual se cumple que dentro de cada grupo todo par de nodos tiene una similitud mayor que un umbral. Un acercamiento novedoso en esta direcci\xc3\xb3n es el uso de varias medidas de similitud y disimilitud, combinadas a partir de sumas convexas, sumas convexas, lo cual ha mejorado en gran medida el funcionamiento de este tipo de metodolog\xc3\xada.\xe2\x80\x8b\n_START_SECTION_\nAlgoritmo Girvan\xe2\x80\x93Newman\n_START_PARAGRAPH_\nOtro algoritmo com\xc3\xbanmente utilizado para detectar comunidades es el algoritmo Girvan\xe2\x80\x93Newman.\xe2\x80\x8b El cual identifica las aristas que se encuentran entre comunidades y las elimina, dejando atr\xc3\xa1s las comunidades.  La identificaci\xc3\xb3n de estas aristas se realiza empleando la medida de centralidad en teor\xc3\xada de grafos: intermediaci\xc3\xb3n, la cual asigna un n\xc3\xbamero a cada arista que es mayor si la arista se encuentra entre muchos pares de nodos._NEWLINE_El algoritmo Girvan\xe2\x80\x93Newman obtiene resultados de una calidad razonable y es popular porque ha sido implementado en m\xc3\xbaltiples paquetes est\xc3\xa1ndar de software.  Pero tiene un costo temporal alto (O(m2n)) en una red de n v\xc3\xa9rtices y m aristas, por lo que es poco pr\xc3\xa1ctico para redes de m\xc3\xa1s de unos cuantos miles de nodos.\xe2\x80\x8b\n_START_SECTION_\nMaximizaci\xc3\xb3n de modularidad\n_START_PARAGRAPH_\nA pesar de sus conocidas deficiencias, uno de los m\xc3\xa9todos m\xc3\xa1s usados para detecci\xc3\xb3n de comunidades es maximizaci\xc3\xb3n de modularidad.\xe2\x80\x8b Modularidad es una funci\xc3\xb3n de beneficio que mide la calidad de una partici\xc3\xb3n de la red en comunidades. El m\xc3\xa9todo de maximizaci\xc3\xb3n de modularidad detecta comunidades buscando entre posibles particiones de la red la que tenga un valor particularmente alto de modularidad. Dado que una b\xc3\xbasqueda exhaustiva por todas las posibles particiones de la red es normalmente impracticable, los algoritmos pr\xc3\xa1cticos se basan en m\xc3\xa9todos aproximados de optimizaci\xc3\xb3n tales con algoritmos golosos, recosido simulado, u optimizaci\xc3\xb3n espectral, con diferentes enfoques basados en velocidad y exactitud.\xe2\x80\x8b\xe2\x80\x8b _NEWLINE_Un enfoque popular es el m\xc3\xa9todo Louvain, que iterativamente optimiza comunidades locales hasta que la modularidad global no puede ser mejorada a trav\xc3\xa9s de modificaciones a la distribuci\xc3\xb3n de comunidades actual.\xe2\x80\x8b El mejor algoritmo de maximizaci\xc3\xb3n de modularidad en la actualidad (ganador del d\xc3\xa9cimo Concurso de Implementaci\xc3\xb3n CIMACS) es un algoritmo iterativo de ensamblaje.\xe2\x80\x8b_NEWLINE_La utilidad de la optimizaci\xc3\xb3n de modularidad es cuestionable, dado que se ha sido mostrado que falla en detectar comunidades menores que cierta escala, dependiendo del tama\xc3\xb1o de la red (l\xc3\xadmite de resoluci\xc3\xb3n\xe2\x80\x8b); por otra parte los valores de modularidad se caracterizan por una gran degeneraci\xc3\xb3n de particiones con alta modularidad, cercana al m\xc3\xa1ximo absoluto, que pueden ser muy diferentes entre ellas.\xe2\x80\x8b\n_START_SECTION_\nInferencia estad\xc3\xadstica\n_START_PARAGRAPH_\nLos m\xc3\xa9todos basados en inferencia estad\xc3\xadstica intentan ajustar un modelo generador a los datos de la red, el cual codifica la estructura de comunidades. La ventaja general de esta enfoque con respecto a sus alternativas es su naturaleza de principios, y la capacidad de dirigirse inherentemente a asuntos de importancia estad\xc3\xadstica. La mayor parte de los m\xc3\xa9todos en la literatura est\xc3\xa1n basados en el modelo de bloque estoc\xc3\xa1stico\xe2\x80\x8b as\xc3\xad como variantes que incluyen afiliaci\xc3\xb3n mixta,\xe2\x80\x8b\xe2\x80\x8bgrado-correcci\xc3\xb3n,\xe2\x80\x8b y estructuras jer\xc3\xa1rquicas.\xe2\x80\x8b_NEWLINE_La selecci\xc3\xb3n del modelo puede realizarse utilizando enfoques de principios como longitud de descripci\xc3\xb3n m\xc3\xadnima\xe2\x80\x8b y selecci\xc3\xb3n de modelo bayesiana.\xe2\x80\x8b Actualmente existen muchos algoritmos para realizar una inferencia eficaz de modelos de bloque estoc\xc3\xa1stico, incluyendo propagaci\xc3\xb3n de creencia\xe2\x80\x8b\xe2\x80\x8by Monte Carlo aglomerativo.\xe2\x80\x8b_NEWLINE_A diferencia de los enfoques que intentan agrupar la red a partir de una funci\xc3\xb3n de calidad ad-hoc, esta clase de m\xc3\xa9todo est\xc3\xa1 basado en modelos generativos que no solo sirven como una descripci\xc3\xb3n a gran escala de la estructurad de la red, sino que tambi\xc3\xa9n puede ser utilizado para generalizar los datos, y predecir la ocurrencia de aristas faltantes o falsas en la red.\xe2\x80\x8b\xe2\x80\x8b\n_START_SECTION_\nM\xc3\xa9todos basados en cliques\n_START_PARAGRAPH_\nLos cliques son subgrafos en los cuales todos los nodos est\xc3\xa1n conectados al resto de los nodos del clique. No es sorprendente que existan m\xc3\xbaltiples enfoques para detectar comunidades en una red basados la detecci\xc3\xb3n de cliques en un grafo y en el an\xc3\xa1lisis de como estos se superponen dado que los nodos no pueden estar m\xc3\xa1s densamente conectados que en un clique. Note que como un nodo puede ser miembro de m\xc3\xa1s de un clique, en estos m\xc3\xa9todos un nodo puede ser miembro de m\xc3\xa1s de una comunidad formado una estructura de comunidades con superposici\xc3\xb3n._NEWLINE_Un enfoque es encontrar los cliques maximales, es decir los cliques que no son subgrafos de otros cliques. El algoritmo cl\xc3\xa1sico para encontrarlos es el algoritmo Bron-Kerbosch. Es posible utilizar la superposici\xc3\xb3n de los cliques maximales para definir comunidades de m\xc3\xbaltiples formas. La m\xc3\xa1s sencilla es considerar solo los cliques maximales que sean m\xc3\xa1s grandes que un tama\xc3\xb1o m\xc3\xadnimo (n\xc3\xbamero de nodos). La uni\xc3\xb3n de estos cliques forma un grafo cuyas componentes conexas definen comunidades.\xe2\x80\x8b Estos enfoques a menudo son implementadas en softwares de an\xc3\xa1lisis de red social tales como UCInet._NEWLINE_El enfoque alternativo es utilizar cliques de tama\xc3\xb1o fijo, k. La superposici\xc3\xb3n de los cuales puede definir un tipo de hipergrafo k-regular o una estructura que es una generalizaci\xc3\xb3n del grafo l\xc3\xadnea (el caso cuando k=2) conocido como Grafo Clique.\xe2\x80\x8b  En el cual los v\xc3\xa9rtices representan cliques en el grafo original y existe una arista entre dos nodos si los cliques que representan tienen alg\xc3\xban nodo en com\xc3\xban.   El Grafo clique puede ser utilizado para detectar una estructura de comunidades aplicando cualquiera de los m\xc3\xa9todos de detecci\xc3\xb3n de comunidades anteriores (los cuales asignan cada nodo a una comunidad) al grafo clique, asignando cada clique a una comunidad.  Luego como un nodo puede pertenecer a varios cliques puede pertenecer a varias comunidades. Por ejemplo el m\xc3\xa9todo de Percolaci\xc3\xb3n de Cliques\xe2\x80\x8b define comunidades como grupos de percolaci\xc3\xb3n de k-cliques. Para hacer esto _NEWLINE_encuentra todos los k-cliques en una red, es decir todos los sub-grafos completos de k-nodos. Luego define que dos k-cliques son adyacentes si comparten k \xe2\x88\x92 1 nodos, lo cual es utilizado para definir aristas en un grafo clique. Entonces se define una comunidad como la uni\xc3\xb3n m\xc3\xa1xima de k-cliques en los que podemos alcanzar cualquier k-clique en ella desde cualquier otro de sus k-cliques a trav\xc3\xa9s de una serie de k-cliques adyacentes. Es decir comunidades que son las componentes conexas del grafo clique. Como un nodo puede pertenecer a m\xc3\xbaltiples grupos de percolaci\xc3\xb3n de k-cliques al mismo tiempo las comunidades se pueden superponer.\n_START_SECTION_\nM\xc3\xa9todos de prueba para algoritmos de detecci\xc3\xb3n comunidades\n_START_PARAGRAPH_\nLa evaluaci\xc3\xb3n de algoritmos, para determinar cu\xc3\xa1les son mejores para detectar estructura de comunidades, es todav\xc3\xada una discusi\xc3\xb3n abierta. Debe ser basado en el an\xc3\xa1lisis de redes estructura conocida. Un ejemplo t\xc3\xadpico es la prueba de "cuatro grupos", en la cual una red se divide en cuatro grupos del mismo tama\xc3\xb1o grupos (normalmente de 32 nodos cada uno) y las probabilidades de conexi\xc3\xb3n dentro y entre los grupos var\xc3\xada para crear estructuras m\xc3\xa1s o menos desafiantes para el algoritmo de detecci\xc3\xb3n. Tal benchmark  es un caso especial del modelo plantado de l-partici\xc3\xb3n\xe2\x80\x8b de Condon y Karp, o de forma m\xc3\xa1s general de "modelos de bloque estoc\xc3\xa1stico," una clase general de modelos de red aleatoria que contienen estructura de comunidades. Se han propuesto otros benchmarks m\xc3\xa1s flexibles que permiten variar el tama\xc3\xb1o de los grupos y distribuciones de grado no triviales, tales como LFR benchmark propuesto por Lancichinetti et al._NEWLINE_,\xe2\x80\x8b el cual es una extensi\xc3\xb3n del benchmark de cuatro grupos que incluye distribuciones de grados heterog\xc3\xa9neas y tama\xc3\xb1o de comunidad variable, lo cual lo convierte en una prueba m\xc3\xa1s fuerte para algoritmos de detecci\xc3\xb3n comunidades._NEWLINE_Lo benchgmarks generados por computadora com\xc3\xbanmente utilizados comienzan con una red con comunidades bien definidas. Luego esta estructura se degradad agregado o eliminando aristas de forma que cada vez es m\xc3\xa1s dif\xc3\xadcil detectar las comunidades originales para el algoritmo.  Al final, la red llega a un punto donde es esencialmente aleatoria. Este tipo de benchmark puede ser llamado "abierto". El rendimiento en estos benchmarks se eval\xc3\xbaa por medidas tales como informaci\xc3\xb3n mutua normalizada o variaci\xc3\xb3n de informaci\xc3\xb3n. Esto algoritmos comparan la soluci\xc3\xb3n obtenida por un algoritmo con la estructura comunitaria original, evaluando la semejanza de ambas particiones.'