Accesibilidad a clúster de percolación 3D
Un clúster de percolación tridimensional con sitios coloreado de acuerdo a su accesibilidad a la difusión de los caminantes al azar
David A. Adams
Leonard M. Sander
Departamento de Física
Universidad de Michigan
Ann Arbor, Michigan
Robert M. Ziff
Departamento de Ingeniería Química
Universidad de Michigan
Ann Arbor, Michigan
Accesibilidad 3D percolación Cluster
Los fractales son auto-similares, ellos tienen el mismo aspecto en muchas escalas, y se producen con frecuencia en la naturaleza por lo que son objeto de interés teórico, experimental y estética sostenida.
Una propiedad importante de un fractal es la facilidad con las que diminutas partículas de polvo pueden llegar a diferentes partes del objeto. Esta propiedad se llama la medida armónica y es importante para aplicaciones tales como la forma en que crece un catalizador áspero y lo resistente catalizadores son ásperas al ser contaminados por moléculas no reactivos. La medida de armónicos es con frecuencia difícil de obtener debido a que las partes más íntimas de un objetos fractales típicamente tienen probabilidades más pequeño que uno en un billón de billones de ser golpeado por las partículas de polvo.
Hemos desarrollado una herramienta para medir esos extremadamente pequeñas probabilidades de objetos fractales tridimensionales simulados llamados cúmulos de percolación. Las imágenes muestran un pequeño grupo de percolación con los sitios en el clúster de color de acuerdo a sus portabilidades de ser golpeado por las partículas de polvo.
APS Physics
Este blog reúne material del curso de posgrado "Análisis de redes sociales" dictado en la Universidad Nacional del Sur (Argentina).
Mostrando entradas con la etiqueta método de percolación de cliques. Mostrar todas las entradas
Mostrando entradas con la etiqueta método de percolación de cliques. Mostrar todas las entradas
martes, 3 de noviembre de 2015
sábado, 25 de julio de 2015
Las nuevas leyes de redes explosivas
Las Nuevas Leyes de Redes explosivas
Los investigadores están descubriendo las leyes ocultas que revelan cómo crece Internet, cómo se extienden los virus, y cómo las burbujas estallan financiera.
Quanta Magazine
Paolo Ceric / PATAKK
Las redes crecen a medida que nodos individuales se conectan entre sí. Al ajustar las reglas que rigen cuando los nodos se conectan, los investigadores pueden dar forma a las propiedades de la red.
Por: Jennifer Ouellette
La semana pasada, United Airlines a tierra cerca de 5.000 vuelos cuando su sistema informático se estrelló. El culpable: un router de red defectuoso. Más tarde en la misma mañana, otro error de computadora detuvo cotización en la Bolsa de Nueva York durante más de tres horas.
Algunos vieron la mano siniestra de un hacker en estos apagones, pero son mucho más propensos a ser una coincidencia, una característica intrínseca del sistema en lugar de un error. Redes bajan todo el tiempo, como consecuencia de niveles sin precedentes de interconexión. Las interrupciones pueden ocurrir incluso en las redes más robustas, si se trata de las redes eléctricas, los mercados financieros globales, o su red social favorita. Como el ex reportero del Atlántico Alexis Madrigal observó cuando un error de la computadora cerró la bolsa de valores Nasdaq en 2013: "Cuando las cosas funcionan de nuevas maneras, se rompen en nuevas formas."
Una nueva comprensión fresca de tales sistemas - la forma en que crecen, y cómo se rompen - ha surgido de la física de café.
Los investigadores piensan generalmente de conectividad de red como sucede de una manera lenta y continua, similar al agua manera mueve a través de los granos de café recién molidos, lentamente saturar todos los gránulos para convertirse café en el recipiente por debajo. Sin embargo, en los últimos años, los investigadores han descubierto que, en casos especiales, la conectividad podría emerger con una explosión, no un gemido, a través de un fenómeno que han denominado "percolación explosivo."
Cortesía de Raissa D'Souza
Los clusters cultivan a través de percolación explosivo.
Esta nueva comprensión de cómo emerge über-conectividad, que se describió a principios de este mes en la revista Nature Physics, es el primer paso hacia la identificación de signos de alarma que pueden producirse cuando estos sistemas van mal - por ejemplo, cuando las redes de energía comienzan a fallar, o cuando una enfermedad infecciosa comienza a multiplicarse en una pandemia global. Percolación explosivo puede ayudar a crear estrategias eficaces de intervención para controlar esa conducta y, quizás, evitar consecuencias catastróficas.
La formación de conectividad puede ser entendido como una transición de fase, el proceso por el cual el agua se congela en hielo o hierve lejos en vapor.
Transiciones de fase son ubicuos en la naturaleza, y también proporcionan un modelo útil para cómo nodos individuales en una red aleatoria unir de forma progresiva, uno por uno, a través de conexiones de corto alcance en el tiempo. Cuando el número de conexiones alcanza un umbral crítico, un cambio de fase hace que el más grande grupo de nodos a crecer rápidamente, y los resultados über-conectividad. (Visto así, el proceso de percolación que da origen a su taza de la mañana de Joe es un ejemplo de una transición de fase de agua caliente pasa a través de granos tostados y los cambios en un nuevo estado -.. Café)
Raissa D'Souza, un físico de la Universidad de California, Davis, está explorando cómo las intervenciones a pequeña escala pueden alterar una red grande, compleja.
La Percolación Explosiva funciona un poco diferente. La idea surgió durante un taller en 2000 en el Instituto de Campos de Investigación en Ciencias Matemáticas en Toronto. Dimitris Achlioptas, un científico de la computación en la Universidad de California, Santa Cruz, propuso un posible medio para retrasar una transición de fase en una red mejor conectada, mediante la fusión de la noción tradicional de percolación con una estrategia de optimización conocido como el poder de dos opciones. En lugar de limitarse a dejar que dos nodos se conectan al azar (o no), se tiene en cuenta dos pares de nodos de azar, y decidir qué par prefiere conectarse. Su elección se basa en criterios predeterminados - por ejemplo, puede seleccionar el que sea par tiene el menor número de conexiones preexistentes a otros nodos.
Debido a un sistema aleatorio normalmente favorecería los nodos con las conexiones más pre-existentes, esta elección forzada introduce un sesgo en la red - una intervención que altere su comportamiento típico. En 2009, Achlioptas, Raissa D'Souza, un físico de la Universidad de California, Davis, y Joel Spencer, un matemático en el Instituto Courant de la Universidad de Nueva York de Ciencias Matemáticas, encontraron que ajustar el modelo de percolación tradicional de esta manera cambia radicalmente la naturaleza de la transición de fase resultante. En lugar de surgir de un proceso lento, marcha continua constante hacia una mayor y una mayor conectividad, conexiones surgen a nivel mundial de una sola vez en todo el sistema en una especie de explosión - de ahí el apodo de "percolación explosivo."
El concepto se ha disparado en su propio derecho, generando un sinnúmero de papeles en los últimos seis años. Muchos de los documentos de debatir si este nuevo modelo constituye una transición de fase verdaderamente discontinua. De hecho, en 2011 los investigadores mostraron que para el modelo en particular analizada en el estudio original de 2009, transiciones explosivos sólo ocurren si la red es finito. Mientras que las redes como Internet tienen como máximo alrededor de mil millones de nodos, transiciones de fase son los más comúnmente asociado con materiales, que son celosías intrincados de tantas moléculas (aproximadamente 1.023 o más) que los sistemas sean efectivamente infinito. Una vez extendido a un sistema verdaderamente infinito, filtraciones explosivas parecen perder parte de su auge.
Sin embargo, D'Souza y sus cohortes no han estado inactiva tampoco. Ellos han descubierto muchos otros modelos de percolación que producen transiciones verdaderamente abruptos. Estos nuevos modelos comparten una característica clave, según D'Souza. En percolación tradicional, los nodos y los pares de nodos son elegidos al azar para formar conexiones, pero la probabilidad de que la fusión de dos grupos es proporcional a su tamaño. Una vez que un gran grupo se ha formado, que domina el sistema, absorbiendo las agrupaciones más pequeñas que de otra manera podrían fusionarse y crecer.
Sin embargo, en los modelos de explosivos, que la red crece, pero el crecimiento de la agrupación grande se suprime. Esto permite que muchos grupos grandes pero desconectados a crecer, hasta que el sistema realiza el umbral crítico en el que la adición de sólo uno o dos enlaces adicionales desencadena un interruptor instantáneo para über-conectividad. Todos los grandes grupos se combinan a la vez en una sola fusión violenta.
Percolación explosiva es un primer paso para pensar en el control, de acuerdo con D'Souza, ya que proporciona un medio de la manipulación de la aparición de la conectividad a larga distancia a través de interacciones de pequeña escala. Una serie de intervenciones a pequeña escala puede tener consecuencias dramáticas - para bien o para mal.
Profesionales de las relaciones públicas a menudo preguntan cómo el trabajo de D'Souza podría ayudar a que sus productos van viral. Ella normalmente responde señalando que sus modelos realmente suprimen el comportamiento viral, al menos en el corto plazo. "¿Quieres ganarse todas las ganancias tan rápido como puedas, o quiere suprimir [el crecimiento] así que cuando esto ocurre, más personas aprenden acerca de inmediato?", Dijo. Lo mismo es válido para las campañas políticas, según Ziff. Siguiendo este modelo, podrían pasar gran parte de su tiempo a principios de la campaña en los esfuerzos locales de base, la creación de grupos localizados de conexiones y la supresión de la aparición de conexiones de largo alcance hasta que la campaña estaba listo para ir nacional con una gran bienvenida medios.
En otros sistemas, como los mercados financieros o de las redes de energía eléctrica, cuando se produce un colapso, es probable que sea catastrófico, y este enfoque mosaico podría utilizarse para revertir el proceso, rompiendo el sistema über-conectada en una colección de grupos inconexos , o "islas", para evitar fallos en cascada catastróficos. Lo ideal sería que uno esperaría encontrar un "punto dulce" para el nivel óptimo de intervención.
En las redes de energía, las empresas de servicios públicos pierden dinero cada vez que una línea de baja, por lo que idealmente se deben tratar de evitar cualquier tiempo de inactividad. Sin embargo, actuar para evitar cualquier interrupción en absoluto puede conducir inadvertidamente a muy grandes cortes que son mucho más costosos. Por lo tanto, el fomento de las pequeñas "fallas" en cascada puede disipar los desequilibrios de energía que de otro modo habrían causado fallas masivas más adelante, una estrategia potencialmente inteligente a pesar de que se come en los márgenes de beneficio. "Si suele disparar pequeñas cascadas, nunca te acontecimientos realmente masivas, pero [el sacrificio] todo lo que los beneficios a corto plazo", explicó D'Souza. "Si evita cascadas a toda costa, es posible hacer un montón de beneficios, pero al final una cascada va a suceder, y será tan masiva que [podía] acabar con toda su beneficio."
El siguiente paso es identificar los signos que pueden indicar cuando un sistema está a punto de crítica. Los investigadores entienden transiciones de fase como los que suceden cuando el agua se convierte en hielo, y puede identificar signos de un cambio inminente. Lo mismo no puede decirse de percolación explosivo. "Una vez que tengamos una mejor comprensión, vamos a ser capaces de ver cómo nuestras intervenciones de control están afectando el sistema", dijo D'Souza. "Vamos a tener estos datos podemos analizar en tiempo real para ver si estamos viendo la firma de las señales de alerta temprana de muchas clases diferentes de transiciones."
Transiciones de fase tienen los físicos y matemáticos fascinado por igual durante décadas, ¿por qué se ha encontrado este comportamiento explosivo sólo ahora? D'Souza cree que es debido a que el avance requiere la fusión de ideas de varios campos, especialmente idea Achlioptas 'para mezclar los algoritmos y la física estadística, creando así un nuevo y emocionante fenómeno modelado. "Realmente es un nuevo paradigma de percolación", dijo Ziff.
Los investigadores están descubriendo las leyes ocultas que revelan cómo crece Internet, cómo se extienden los virus, y cómo las burbujas estallan financiera.
Quanta Magazine
Paolo Ceric / PATAKK
Las redes crecen a medida que nodos individuales se conectan entre sí. Al ajustar las reglas que rigen cuando los nodos se conectan, los investigadores pueden dar forma a las propiedades de la red.
Por: Jennifer Ouellette
La semana pasada, United Airlines a tierra cerca de 5.000 vuelos cuando su sistema informático se estrelló. El culpable: un router de red defectuoso. Más tarde en la misma mañana, otro error de computadora detuvo cotización en la Bolsa de Nueva York durante más de tres horas.
Algunos vieron la mano siniestra de un hacker en estos apagones, pero son mucho más propensos a ser una coincidencia, una característica intrínseca del sistema en lugar de un error. Redes bajan todo el tiempo, como consecuencia de niveles sin precedentes de interconexión. Las interrupciones pueden ocurrir incluso en las redes más robustas, si se trata de las redes eléctricas, los mercados financieros globales, o su red social favorita. Como el ex reportero del Atlántico Alexis Madrigal observó cuando un error de la computadora cerró la bolsa de valores Nasdaq en 2013: "Cuando las cosas funcionan de nuevas maneras, se rompen en nuevas formas."
Una nueva comprensión fresca de tales sistemas - la forma en que crecen, y cómo se rompen - ha surgido de la física de café.
Los investigadores piensan generalmente de conectividad de red como sucede de una manera lenta y continua, similar al agua manera mueve a través de los granos de café recién molidos, lentamente saturar todos los gránulos para convertirse café en el recipiente por debajo. Sin embargo, en los últimos años, los investigadores han descubierto que, en casos especiales, la conectividad podría emerger con una explosión, no un gemido, a través de un fenómeno que han denominado "percolación explosivo."
Cortesía de Raissa D'Souza
Los clusters cultivan a través de percolación explosivo.
Esta nueva comprensión de cómo emerge über-conectividad, que se describió a principios de este mes en la revista Nature Physics, es el primer paso hacia la identificación de signos de alarma que pueden producirse cuando estos sistemas van mal - por ejemplo, cuando las redes de energía comienzan a fallar, o cuando una enfermedad infecciosa comienza a multiplicarse en una pandemia global. Percolación explosivo puede ayudar a crear estrategias eficaces de intervención para controlar esa conducta y, quizás, evitar consecuencias catastróficas.
Un giro explosivo
Modelos matemáticos tradicionales de percolación, que se remontan a la década de 1940, ven el proceso como una transición suave y continua. "Pensamos en la percolación como el agua que fluye a través de la tierra", dijo Robert Ziff, un físico de la Universidad de Michigan que ha estado estudiando las transiciones de fase en los últimos 30 años. "Es una formación de conectividad de largo alcance en el sistema."La formación de conectividad puede ser entendido como una transición de fase, el proceso por el cual el agua se congela en hielo o hierve lejos en vapor.
Transiciones de fase son ubicuos en la naturaleza, y también proporcionan un modelo útil para cómo nodos individuales en una red aleatoria unir de forma progresiva, uno por uno, a través de conexiones de corto alcance en el tiempo. Cuando el número de conexiones alcanza un umbral crítico, un cambio de fase hace que el más grande grupo de nodos a crecer rápidamente, y los resultados über-conectividad. (Visto así, el proceso de percolación que da origen a su taza de la mañana de Joe es un ejemplo de una transición de fase de agua caliente pasa a través de granos tostados y los cambios en un nuevo estado -.. Café)
Raissa D'Souza, una física de la Universidad de California, Davis, está explorando cómo las intervenciones a pequeña escala pueden alterar una red grande, compleja. Kevin Tong, UC Davis |
Raissa D'Souza, un físico de la Universidad de California, Davis, está explorando cómo las intervenciones a pequeña escala pueden alterar una red grande, compleja.
La Percolación Explosiva funciona un poco diferente. La idea surgió durante un taller en 2000 en el Instituto de Campos de Investigación en Ciencias Matemáticas en Toronto. Dimitris Achlioptas, un científico de la computación en la Universidad de California, Santa Cruz, propuso un posible medio para retrasar una transición de fase en una red mejor conectada, mediante la fusión de la noción tradicional de percolación con una estrategia de optimización conocido como el poder de dos opciones. En lugar de limitarse a dejar que dos nodos se conectan al azar (o no), se tiene en cuenta dos pares de nodos de azar, y decidir qué par prefiere conectarse. Su elección se basa en criterios predeterminados - por ejemplo, puede seleccionar el que sea par tiene el menor número de conexiones preexistentes a otros nodos.
Debido a un sistema aleatorio normalmente favorecería los nodos con las conexiones más pre-existentes, esta elección forzada introduce un sesgo en la red - una intervención que altere su comportamiento típico. En 2009, Achlioptas, Raissa D'Souza, un físico de la Universidad de California, Davis, y Joel Spencer, un matemático en el Instituto Courant de la Universidad de Nueva York de Ciencias Matemáticas, encontraron que ajustar el modelo de percolación tradicional de esta manera cambia radicalmente la naturaleza de la transición de fase resultante. En lugar de surgir de un proceso lento, marcha continua constante hacia una mayor y una mayor conectividad, conexiones surgen a nivel mundial de una sola vez en todo el sistema en una especie de explosión - de ahí el apodo de "percolación explosivo."
El concepto se ha disparado en su propio derecho, generando un sinnúmero de papeles en los últimos seis años. Muchos de los documentos de debatir si este nuevo modelo constituye una transición de fase verdaderamente discontinua. De hecho, en 2011 los investigadores mostraron que para el modelo en particular analizada en el estudio original de 2009, transiciones explosivos sólo ocurren si la red es finito. Mientras que las redes como Internet tienen como máximo alrededor de mil millones de nodos, transiciones de fase son los más comúnmente asociado con materiales, que son celosías intrincados de tantas moléculas (aproximadamente 1.023 o más) que los sistemas sean efectivamente infinito. Una vez extendido a un sistema verdaderamente infinito, filtraciones explosivas parecen perder parte de su auge.
Sin embargo, D'Souza y sus cohortes no han estado inactiva tampoco. Ellos han descubierto muchos otros modelos de percolación que producen transiciones verdaderamente abruptos. Estos nuevos modelos comparten una característica clave, según D'Souza. En percolación tradicional, los nodos y los pares de nodos son elegidos al azar para formar conexiones, pero la probabilidad de que la fusión de dos grupos es proporcional a su tamaño. Una vez que un gran grupo se ha formado, que domina el sistema, absorbiendo las agrupaciones más pequeñas que de otra manera podrían fusionarse y crecer.
Sin embargo, en los modelos de explosivos, que la red crece, pero el crecimiento de la agrupación grande se suprime. Esto permite que muchos grupos grandes pero desconectados a crecer, hasta que el sistema realiza el umbral crítico en el que la adición de sólo uno o dos enlaces adicionales desencadena un interruptor instantáneo para über-conectividad. Todos los grandes grupos se combinan a la vez en una sola fusión violenta.
Un nuevo paradigma para el control
D'Souza quiere aprender cómo controlar mejor las redes complejas. La conectividad es una espada de doble filo, de acuerdo con ella. "Para los sistemas normales de funcionamiento [como Internet, redes aéreas o la bolsa de valores], queremos que se pueden conectar en gran medida", dijo. "Pero cuando pensamos en las epidemias de difusión, queremos restringir el alcance de la conectividad". Incluso cuando la alta conectividad es deseable, a veces puede ser contraproducente, provocando un colapso potencialmente catastrófico del sistema. "Nos gustaría ser capaces de intervenir en el sistema fácilmente para mejorar o retrasar su conectividad", dependiendo de la situación, dijo.Percolación explosiva es un primer paso para pensar en el control, de acuerdo con D'Souza, ya que proporciona un medio de la manipulación de la aparición de la conectividad a larga distancia a través de interacciones de pequeña escala. Una serie de intervenciones a pequeña escala puede tener consecuencias dramáticas - para bien o para mal.
Profesionales de las relaciones públicas a menudo preguntan cómo el trabajo de D'Souza podría ayudar a que sus productos van viral. Ella normalmente responde señalando que sus modelos realmente suprimen el comportamiento viral, al menos en el corto plazo. "¿Quieres ganarse todas las ganancias tan rápido como puedas, o quiere suprimir [el crecimiento] así que cuando esto ocurre, más personas aprenden acerca de inmediato?", Dijo. Lo mismo es válido para las campañas políticas, según Ziff. Siguiendo este modelo, podrían pasar gran parte de su tiempo a principios de la campaña en los esfuerzos locales de base, la creación de grupos localizados de conexiones y la supresión de la aparición de conexiones de largo alcance hasta que la campaña estaba listo para ir nacional con una gran bienvenida medios.
En otros sistemas, como los mercados financieros o de las redes de energía eléctrica, cuando se produce un colapso, es probable que sea catastrófico, y este enfoque mosaico podría utilizarse para revertir el proceso, rompiendo el sistema über-conectada en una colección de grupos inconexos , o "islas", para evitar fallos en cascada catastróficos. Lo ideal sería que uno esperaría encontrar un "punto dulce" para el nivel óptimo de intervención.
En las redes de energía, las empresas de servicios públicos pierden dinero cada vez que una línea de baja, por lo que idealmente se deben tratar de evitar cualquier tiempo de inactividad. Sin embargo, actuar para evitar cualquier interrupción en absoluto puede conducir inadvertidamente a muy grandes cortes que son mucho más costosos. Por lo tanto, el fomento de las pequeñas "fallas" en cascada puede disipar los desequilibrios de energía que de otro modo habrían causado fallas masivas más adelante, una estrategia potencialmente inteligente a pesar de que se come en los márgenes de beneficio. "Si suele disparar pequeñas cascadas, nunca te acontecimientos realmente masivas, pero [el sacrificio] todo lo que los beneficios a corto plazo", explicó D'Souza. "Si evita cascadas a toda costa, es posible hacer un montón de beneficios, pero al final una cascada va a suceder, y será tan masiva que [podía] acabar con toda su beneficio."
El siguiente paso es identificar los signos que pueden indicar cuando un sistema está a punto de crítica. Los investigadores entienden transiciones de fase como los que suceden cuando el agua se convierte en hielo, y puede identificar signos de un cambio inminente. Lo mismo no puede decirse de percolación explosivo. "Una vez que tengamos una mejor comprensión, vamos a ser capaces de ver cómo nuestras intervenciones de control están afectando el sistema", dijo D'Souza. "Vamos a tener estos datos podemos analizar en tiempo real para ver si estamos viendo la firma de las señales de alerta temprana de muchas clases diferentes de transiciones."
Transiciones de fase tienen los físicos y matemáticos fascinado por igual durante décadas, ¿por qué se ha encontrado este comportamiento explosivo sólo ahora? D'Souza cree que es debido a que el avance requiere la fusión de ideas de varios campos, especialmente idea Achlioptas 'para mezclar los algoritmos y la física estadística, creando así un nuevo y emocionante fenómeno modelado. "Realmente es un nuevo paradigma de percolación", dijo Ziff.
jueves, 18 de diciembre de 2014
ARS 101: Método de percolación de cliques
Método de percolación de cliques
Wikipedia
El método de percolación de clique [1] es un método popular para analizar la estructura de comunidades superpuestas de redes. El término comunidad de redes (también llamado módulo, clúster o grupo cohesivo) ha sido ampliamente aceptado como definición única y por lo general se define como un grupo de nodos que están más densamente conectada entre sí que a otros nodos de la red. Existen numerosos métodos alternativos para la detección de las comunidades en las redes, [2], por ejemplo, el algoritmo Girvan-Newman, la agrupación jerárquica y la maximización de modularidad.
Evolución temporal de las comunidades superpuestas. La estructura (parte) y la dinámica esquemáticas de la red de co-autoría de ~ 30.000 autores cond-mat y la red de comunicación de más de 4 millones de suscriptores de telefonía. De Palla et. al., Nature 446, 664 (2007).
Esta definición permite solapamientos entre las comunidades de una manera natural, como se ilustra en la Figura 1, que muestra cuatro comunidades k-clique en k = 4. Las comunidades están codificados por color y la superposición entre ellas se destacan en rojo. La definición anterior también es local: si un determinado sub-gráfico cumple los criterios para ser considerado como una comunidad, entonces seguirá siendo una comunidad independiente de lo que sucede a otra parte de la red lejos. Por el contrario, en la búsqueda de las comunidades mediante la optimización con respecto a una cantidad global, un cambio muy lejos, en la red se puede formar de nuevo las comunidades de las regiones perturbadas también. Además, se ha demostrado que los métodos globales pueden sufrir de un problema de límite de resolución, [3], donde el tamaño de la comunidad más pequeña que se puede extraer es dependiente del tamaño del sistema. Una definición de la comunidad local, como aquí evita este problema de forma automática.
Puesto que incluso las redes pequeñas pueden contener un gran número de k-cliques, la aplicación de este enfoque se basa en la localización de las cliques máxima en lugar de los k-cliques individuales. [1] Por lo tanto, la complejidad de este enfoque en la práctica es equivalente a la del hallazgo NP-completo máxima de clique, (a pesar de que la búsqueda de k-cliques es polinómica). Esto significa que aunque las redes con pocos millones de nodos ya se han analizado con éxito con este enfoque, [4] ninguna estimación previa se puede dar para el tiempo de ejecución del algoritmo basado simplemente en el tamaño del sistema.
Fig.1. Ilustración de las comunidades k-clique en k = 4.
Por ejemplo, en un gráfico simple, podemos definir la superposición entre dos k-cliques ser el número de vértices comunes a los dos k-cliques. El método de percolación de cliques es entonces equivalente a thresholding este grafo clique, cayendo todos los enlaces de peso menor que (k-1), con los componentes conectados restantes que forman las comunidades de cliques que se encuentran en la RPC. Para k = 2 las cliques son los enlaces del grafo original y la grafo de clique en este caso es el grafo de líneas de la red original.
En la práctica, utilizando el número de vértices comunes como una medida de la fuerza de solapamiento clique puede dar resultados pobres como grandes clique en el gráfico original, los que tienen muchos más de k vértices, dominarán el grafo de clique. El problema surge porque si un vértice está en n diferentes k-cliques que contribuirá a n (n-1) / 2 enlaces en un gráfico como clique. Una solución sencilla es dejar que cada vértice común a dos kcliques superpuestas para contribuir un peso igual a 1 / n en la medición de la fuerza de la superposición de los dos k-cliques.
En general, el punto de vista del grafo clique es una manera útil de encontrar generalizaciones de métodos de percolación de cliques estándar para obtener algún problema redondas encontradas. Incluso muestra cómo describir las extensiones de estos métodos basados en otros motivos, subgrafos distinta k-cliques. En este caso un gráfico clique es mejor pensamiento de un ejemplo particular de un hipergrafo.
Una implementación más rápida (disponible bajo la licencia GPL) ha sido implementado por otro grupo. [17] Otro ejemplo, que también es muy rápido en ciertos contextos, es el algoritmo SCP. [18]
Wikipedia
El método de percolación de clique [1] es un método popular para analizar la estructura de comunidades superpuestas de redes. El término comunidad de redes (también llamado módulo, clúster o grupo cohesivo) ha sido ampliamente aceptado como definición única y por lo general se define como un grupo de nodos que están más densamente conectada entre sí que a otros nodos de la red. Existen numerosos métodos alternativos para la detección de las comunidades en las redes, [2], por ejemplo, el algoritmo Girvan-Newman, la agrupación jerárquica y la maximización de modularidad.
Evolución temporal de las comunidades superpuestas. La estructura (parte) y la dinámica esquemáticas de la red de co-autoría de ~ 30.000 autores cond-mat y la red de comunicación de más de 4 millones de suscriptores de telefonía. De Palla et. al., Nature 446, 664 (2007).
Definiciones
Clique Percolation Method (CPM)
El método de percolación de cliques acumula las comunidades de k-cliques, que corresponden a un grafo completo (totalmente conectados) de sub-grafos de k nodos. (Por ejemplo, una k-clique en k = 3 es equivalente a un triángulo). Dos k-cliques se consideran adyacentes si comparten k - 1 nodos. Una comunidad se define como la unión máxima de k-cliques que se puede alcanzar una de la otra a través de una serie de k-cliques adyacentes. Tales comunidades pueden interpretarse mejor con la ayuda de una plantilla k-clique (un objeto isomorfo a un grafo completo de nodos k). Una plantilla de este tipo puede ser colocado en cualquier k-clique en el gráfico, y rodó a un k-clique adyacente mediante la reubicación de uno de sus nodos y mantener su otro k - 1 nodos fijos. Por lo tanto, las comunidades k-clique de una red son todas aquellas sub-gráficos que se pueden explorar plenamente haciendo rodar una plantilla-k clique en ellos, pero no pueden ser dejados por esta plantilla.Esta definición permite solapamientos entre las comunidades de una manera natural, como se ilustra en la Figura 1, que muestra cuatro comunidades k-clique en k = 4. Las comunidades están codificados por color y la superposición entre ellas se destacan en rojo. La definición anterior también es local: si un determinado sub-gráfico cumple los criterios para ser considerado como una comunidad, entonces seguirá siendo una comunidad independiente de lo que sucede a otra parte de la red lejos. Por el contrario, en la búsqueda de las comunidades mediante la optimización con respecto a una cantidad global, un cambio muy lejos, en la red se puede formar de nuevo las comunidades de las regiones perturbadas también. Además, se ha demostrado que los métodos globales pueden sufrir de un problema de límite de resolución, [3], donde el tamaño de la comunidad más pequeña que se puede extraer es dependiente del tamaño del sistema. Una definición de la comunidad local, como aquí evita este problema de forma automática.
Puesto que incluso las redes pequeñas pueden contener un gran número de k-cliques, la aplicación de este enfoque se basa en la localización de las cliques máxima en lugar de los k-cliques individuales. [1] Por lo tanto, la complejidad de este enfoque en la práctica es equivalente a la del hallazgo NP-completo máxima de clique, (a pesar de que la búsqueda de k-cliques es polinómica). Esto significa que aunque las redes con pocos millones de nodos ya se han analizado con éxito con este enfoque, [4] ninguna estimación previa se puede dar para el tiempo de ejecución del algoritmo basado simplemente en el tamaño del sistema.
Fig.1. Ilustración de las comunidades k-clique en k = 4.
Método de percolación de cliques dirigidos (CPMD)
En una red con enlaces dirigidos a k-clique dirigida es un subgrafo completo con nodos k cumplir la siguiente condición. Los nodos k pueden ser ordenados de tal manera que entre un par arbitrario de ellos existe un enlace apuntando dirigida desde el nodo con el rango más alto hacia el nodo con el rango inferior. The Clique Método percolación dirigida define dirigida comunidades en red como los clusters de percolación de k-cliques dirigidos.Método de percolación de cliques ponderado (CPMw)
En una red con enlaces ponderados una k-clique ponderada es un subgrafo completo con k nodos tales que la media geométrica de la k (k - 1) / 2 de enlace de pesos dentro de la k-clique es mayor que un valor umbral seleccionado, I. The Clique ponderado Método percolación define comunidades red ponderados como los clusters de percolación de k-cliques ponderados. Tenga en cuenta que la media geométrica de los pesos de enlace dentro de un subgrafo se llama la intensidad de ese subgrafo. [5]Generalizaciones de grafos de clique
Los métodos de percolación de clique pueden generalizarse mediante el registro de diferentes cantidades de solapamiento entre las distintas k-cliques. Esto define entonces un nuevo tipo de gráfico, un grafo clique, [6], donde cada k-clique en el gráfico original se representa por un vértice en el nuevo grafo clique. Los enlaces en el grafo de clique se utilizan para registrar la fuerza de la superposición de cliques en el gráfico original. Entonces, uno puede aplicar cualquier método de detección de la comunidad a este grafo clique para identificar los grupos en la gráfica original a través de la estructura de k-clique.Por ejemplo, en un gráfico simple, podemos definir la superposición entre dos k-cliques ser el número de vértices comunes a los dos k-cliques. El método de percolación de cliques es entonces equivalente a thresholding este grafo clique, cayendo todos los enlaces de peso menor que (k-1), con los componentes conectados restantes que forman las comunidades de cliques que se encuentran en la RPC. Para k = 2 las cliques son los enlaces del grafo original y la grafo de clique en este caso es el grafo de líneas de la red original.
En la práctica, utilizando el número de vértices comunes como una medida de la fuerza de solapamiento clique puede dar resultados pobres como grandes clique en el gráfico original, los que tienen muchos más de k vértices, dominarán el grafo de clique. El problema surge porque si un vértice está en n diferentes k-cliques que contribuirá a n (n-1) / 2 enlaces en un gráfico como clique. Una solución sencilla es dejar que cada vértice común a dos kcliques superpuestas para contribuir un peso igual a 1 / n en la medición de la fuerza de la superposición de los dos k-cliques.
En general, el punto de vista del grafo clique es una manera útil de encontrar generalizaciones de métodos de percolación de cliques estándar para obtener algún problema redondas encontradas. Incluso muestra cómo describir las extensiones de estos métodos basados en otros motivos, subgrafos distinta k-cliques. En este caso un gráfico clique es mejor pensamiento de un ejemplo particular de un hipergrafo.
Transición de percolación en el CPM
El modelo Erdös-Rényi muestra una serie de transiciones interesantes cuando se aumenta la probabilidad p de dos nodos están conectados. Para cada k uno puede encontrar un cierto pc probabilidad umbral por encima del cual los k-cliques se organizan en una comunidad gigante. [7] [8] (El tamaño de la comunidad gigante es comparable con el tamaño del sistema, en palabras oder la comunidad gigante ocupa una parte finita del sistema incluso en el límite termodinámico.) Esta transición es análoga a la transición de percolación en la física estadística. Un fenómeno similar se observa en muchas redes reales, así: si k es grande, sólo las partes más densamente vinculados son aceptadas como las comunidades, por lo tanto, por lo general permanecen pequeñas y dispersas. Cuando se baja k, tanto el número como el tamaño de las comunidades comienzan a crecer. Sin embargo, en la mayoría de los casos un valor crítico k puede ser alcanzado, por debajo del cual una comunidad gigante emerge, manchando los detalles de la estructura de la comunidad mediante la fusión (y haciendo invisibles) muchas comunidades más pequeñas.Aplicaciones
El método de percolación clique había sido utilizada para detectar las comunidades de los estudios de la metástasis del cáncer [9] [10] a través de diversas redes sociales [4] [11] [12] [13] [14] para documentar la agrupación [15] y las redes económicas . [16]Algoritmos y Software
Hay un número de implementaciones de percolación clique. El método de percolación de clique se implementó y popularizado por CFinder [1] (freeware para uso no comercial) de software para detectar y visualizar comunidades superpuestas en las redes de primera. El programa permite la visualización personalizable y permite un fácil paseo a través de las comunidades que se encuentran. El paquete contiene una versión de línea de comandos del programa, así, que es adecuado para scripting.Una implementación más rápida (disponible bajo la licencia GPL) ha sido implementado por otro grupo. [17] Otro ejemplo, que también es muy rápido en ciertos contextos, es el algoritmo SCP. [18]
Algoritmos Paralelos
Una versión paralela del método de percolación cliques fue diseñado y desarrollado por S. Mainardi et al .. [19] Mediante la explotación de multi-core / multi-procesador arquitecturas de computación de hoy en día, el método permite la extracción de las comunidades k-cliques de redes muy grandes tales como Internet. [20] los autores lanzaron el código fuente del método bajo la GPL y lo hizo libremente disponible para la comunidad.Referencias
- Uncovering the overlapping community structure of complex networks in nature and society G. Palla, I. Derényi, I. Farkas, and T. Vicsek: Nature 435, 814–818 (2005)
- Community detection in graphs by S. Fortunato, Physics Reports 486, 75-174 (2010)
- Resolution limit in community detection S. Fortunato and M. Barthelemy: Proc. Natl. Acad. Sci. USA 104 (1), 36–41 (2007)
- Quantifying social group evolution G. Palla, A.-L. Barabási and T. Vicsek: Nature 446, 664–667(2007)
- Intensity and coherence of motifs in weighted complex networks J.-P. Onnela, J. Saramäki, J. Kertész, and K. Kaski: Phys. Rev. E 71, 065103 (2005)
- Clique Graphs and Overlapping Communities T.S. Evans: J. Stat. Mech. P12037 (2010) doi:10.1088/1742-5468/2010/12/P12037
- Clique percolation in random networks I. Derényi, G. Palla, and T. Vicsek: Phys. Rev. Lett. 94, 160202 (2005)
- The critical point of k-clique percolation in the Erdos–Renyi graph G. Palla, I. Derényi, and T. Vicsek: J. Stat. Phys. 128, 219–227 (2007)
- Global topological features of cancer proteins in the human interactome P.F. Jonsson and P.A. Bates: Bioinformatics 22(18):2291–2297 (2006)
- Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasis P.F. Jonsson, T. Cavanna, D. Zicha and P. A. Bates: BMC Bioinformatics 7, 2 (2006)
- A system of mobile agents to model social networks M.C. Gonzalez, P.G. Lind and H.J. Herrmann: Phys. Rev. Lett. 96, 088702 (2006)
- Emergence of communities in weighted networks J.M. Kumpula, J.-P. Onnela, J. Saramaki, K. Kaski and J. Kertész: Phys. Rev. Lett. 99, 228701 (2007)
- A Model for Social Networks R. Toivonen, J.-P. Onnela, J. Saramäki, J. Hyvönen and K. Kaski: Physica A-Statistical Mechanics and its Applications 370, 851–860 (2006)
- Community structure and ethnic preferences in school friendship networks M. C. Gonzalez, H. J. Herrmann, J. Kertesz and T. Vicsek: Physica A-Statistical Mechenics and its Applications 379, 307–316 (2007)
- Natural Document Clustering by Clique Percolation in Random Graphs W. Gao and K.-F. Wong: Lect. Notes in Comp. Sci. 4182, 119–131, (2006)
- Spectral and network methods in the analysis of correlation matrices of stock returns T. Heimo, J. Saramaki, J.-P. Onnela and K. Kaski: Physica A-Statistical Mechenics and its Applications 383, 147–151 (2007)
- Percolation Computation in Complex Networks Fergal Reid, Aaron McDaid, Neil Hurley: ASONAM 2012, (2012)
- Sequential algorithm for fast clique percolation Jussi M. Kumpula, Mikko Kivelä, Kimmo Kaski, and Jari Saramäki: Phys. Rev. E 78, 026109 (2008) (2008)
- Parallel k-Clique Community Detection on Large-Scale Networks Enrico Gregori, Luciano Lenzini and Simone Mainardi: IEEE Transactions on Parallel and Distributed Systems, 31 Aug. 2012.
- k-clique Communities in the Internet AS-level Topology Graph Enrico Gregori, Luciano Lenzini and Chiara Orsini: International Conference on Distributed Computing Systems Workshops (ICDCSW), 2011.
Suscribirse a:
Entradas (Atom)