La ley de Zipf que revela frecuencias de palabras libres de escala

La minería de datos revela un patrón fundamental del pensamiento humano.

Los patrones de frecuencia de palabras muestran que los humanos procesan palabras comunes y poco comunes de diferentes maneras, con importantes consecuencias para el procesamiento del lenguaje natural.
por Emerging Technology from the arXiv



En 1935, el lingüista estadounidense George Zipf hizo un descubrimiento notable. Zipf sentía curiosidad por la relación entre las palabras comunes y las menos comunes. Así que contó la frecuencia con que aparecen las palabras en el lenguaje común y luego las ordenó de acuerdo con su frecuencia.

Esto reveló una regularidad notable. Zipf descubrió que la frecuencia de una palabra es inversamente proporcional a su lugar en las clasificaciones. Por lo tanto, una palabra que ocupa el segundo lugar en el ranking aparece la mitad de las veces que la palabra más común. La palabra del tercer puesto aparece un tercio con la frecuencia y así sucesivamente.

En inglés, la palabra más popular es the, que constituye aproximadamente el 7 por ciento de todas las palabras, seguida por y, que ocurre el 3.5 por ciento del tiempo, y así sucesivamente. De hecho, alrededor de 135 palabras representan la mitad de todas las apariciones de palabras. Así que algunas palabras aparecen a menudo, mientras que casi nunca aparecen.



¿Pero por qué? Una posibilidad intrigante es que el cerebro procesa las palabras comunes de manera diferente y que el estudio de la distribución de Zipf debería revelar información importante sobre este proceso cerebral.

Sin embargo hay un problema. No todos los lingüistas están de acuerdo en que la distribución estadística de la frecuencia de palabras es el resultado de procesos cognitivos. En cambio, algunos dicen que la distribución es el resultado de errores estadísticos asociados con palabras de baja frecuencia, que pueden producir distribuciones similares.

Lo que se necesita, por supuesto, es un estudio más amplio en una amplia gama de idiomas. Tal estudio a gran escala sería más poderoso estadísticamente y sería tan capaz de separar estas posibilidades.

Hoy, recibimos un estudio de este tipo gracias al trabajo de Shuiyuan Yu y sus colegas de la Universidad de Comunicación de China en Beijing. Estos muchachos han encontrado la Ley de Zipf en 50 idiomas tomados de una amplia gama de clases lingüísticas, entre ellas indoeuropeas, urálicas, altaicas, caucásicas, chino-tibetanas, dravidianas, afroasiáticas, etc.

Yu y sus colegas dicen que las frecuencias de palabras en estos idiomas comparten una estructura común que difiere de la que producirían los errores estadísticos. Lo que es más, dicen que esta estructura sugiere que el cerebro procesa las palabras comunes de manera diferente a las poco comunes, una idea que tiene consecuencias importantes para el procesamiento del lenguaje natural y la generación automática de texto.

El método de Yu y sus compañeros es sencillo. Comienzan con dos grandes colecciones de texto llamadas British National Corpus y Leipzig Corpus. Estas incluyen muestras de 50 idiomas diferentes, cada muestra con al menos 30,000 oraciones y hasta 43 millones de palabras.

Los investigadores encontraron que las frecuencias de palabras en todos los idiomas siguen una Ley de Zipf modificada en la que la distribución se puede dividir en tres segmentos. "Los resultados estadísticos muestran que las leyes de Zipf en 50 idiomas comparten un patrón estructural de tres segmentos, y cada segmento demuestra propiedades lingüísticas distintivas", dicen Yu.

Esta estructura es interesante. Yu y compañía han intentado simularlo utilizando una serie de modelos para crear palabras. Un modelo es el modelo de máquina de escribir mono, que genera letras aleatorias que forman palabras cada vez que se produce un espacio.

Este proceso genera una distribución de ley de poder como la Ley de Zipf. Sin embargo, no puede generar la estructura de tres segmentos que Yu y compañía han encontrado. Esta estructura tampoco puede ser generada por errores asociados con palabras de baja frecuencia.

Sin embargo, Yu y sus colegas pueden reproducir esta estructura utilizando un modelo de la forma en que funciona el cerebro, llamado teoría del proceso dual. Esta es la idea de que el cerebro funciona de dos maneras diferentes.

El primero es un pensamiento rápido e intuitivo que requiere poco o ningún razonamiento. Se piensa que este tipo de pensamiento ha evolucionado para permitir que los humanos reaccionen rápidamente en situaciones amenazantes. En general, proporciona buenas soluciones a problemas difíciles, como el reconocimiento de patrones, pero puede ser fácilmente engañado por situaciones no intuitivas.

Sin embargo, los humanos son capaces de un pensamiento mucho más racional. Este segundo tipo de pensamiento es más lento, más calculador y deliberado. Es este tipo de pensamiento el que nos permite resolver problemas complejos, como rompecabezas matemáticos, etc.

La teoría del proceso dual sugiere que las palabras comunes como el, y, si y así sucesivamente, se procesan mediante un pensamiento rápido e intuitivo y, por lo tanto, se usan con más frecuencia. Estas palabras forman una especie de columna vertebral para las oraciones.

Sin embargo, las palabras y frases menos comunes, como la hipótesis y la Ley de Zipf, requieren un pensamiento mucho más cuidadoso. Y debido a esto ocurren con menos frecuencia.

De hecho, cuando Yu y co simulan este proceso dual, conduce a la misma estructura de tres segmentos en la distribución de frecuencia de palabras que midieron en 50 idiomas diferentes.

El primer segmento refleja la distribución de palabras comunes, el último segmento refleja la distribución de palabras no comunes y el segmento medio es el resultado del cruce de estos dos regímenes. "Estos resultados muestran que la Ley de Zipf en los idiomas está motivada por mecanismos cognitivos como el procesamiento dual que gobierna las conductas verbales humanas", dicen Yu y compañía.

Eso es un trabajo interesante. La idea de que el cerebro humano procesa la información de dos maneras diferentes ha adquirido un impulso considerable en los últimos años, entre otras cosas gracias al libro El pensamiento, rápido y lento del psicólogo ganador del Premio Nobel Daniel Kahneman, quien ha estudiado esta idea en detalle.

Un problema conocido que se usa para provocar un pensamiento rápido y lento es el siguiente:

“Un bate y una pelota cuestan $ 1.10 en total. El bate cuesta $ 1.00 más que la pelota. ¿Cuánto cuesta la pelota?

La respuesta, por supuesto, es de 5 centavos. Pero casi todos tienen la inclinación inicial a pensar 10 centavos. Eso es porque 10 centavos se sienten bien. Es el orden de magnitud correcto y lo sugiere el marco del problema. Esa respuesta proviene del lado rápido e intuitivo de tu cerebro.

Pero esta mal La respuesta correcta requiere la parte más lenta y más calculadora de tu cerebro.

Yu y compañía dicen que los mismos dos procesos están involucrados en la generación de oraciones. La parte de pensamiento rápido de su cerebro crea la estructura básica de la oración (las palabras aquí marcadas en negrita). Las otras palabras requieren la parte más lenta y más calculadora de tu cerebro.

Es este proceso dual el que conduce a la Ley Zipf de tres segmentos.

Eso debería tener consecuencias interesantes para los informáticos que trabajan en el procesamiento del lenguaje natural. Este campo se ha beneficiado de enormes avances en los últimos años. Estos provienen de algoritmos de aprendizaje automático, pero también de grandes bases de datos de texto recopiladas por compañías como Google.

Pero generar lenguaje natural sigue siendo difícil. No tienes que chatear con Siri, Cortana o el Asistente de Google por mucho tiempo para alcanzar sus límites de conversación.

Por lo tanto, una mejor comprensión de cómo los humanos generan oraciones podría ayudar significativamente. Zipf seguramente habría quedado fascinado.

ARS 101: Amistad, redes y distribución de frecuencia de grados

Cómo la matemática de las redes puede ayudarte a hacer amigos

Estudiar la estructura de las amistades existentes en su comunidad puede ayudarlo a forjar las mejores conexiones al formar un nuevo círculo de amigos.


8



Patrick Honner | Quanta Magazine



Cuando comienzas en una nueva escuela o trabajo, o te mudas a una nueva ciudad, ¿cómo haces para hacer nuevos amigos? Podrías adoptar un enfoque activo, forjando conexiones estratégicas con los niños populares y los que hacen movimientos. O podría dejar las cosas al azar, confiando en agrupaciones y asociaciones aleatorias. Sea cual sea su enfoque, comprender la estructura de las amistades existentes en su nueva comunidad puede ayudarlo a hacer las mejores conexiones, que en última instancia definirán su círculo de amigos.

Imagínese mudarse a una ciudad nueva y extraña, Regulartown, que tiene una regla extraña: todos pueden tener a lo sumo cuatro amigos, y todos quieren maximizar sus amistades. ¿Cómo será la estructura de las amistades en Regulartown? Para explorar esta pregunta, usaremos un objeto matemático llamado red.

En pocas palabras, una red es un conjunto de objetos, llamados "nodos", y las conexiones entre ellos. Las redes son matemáticamente versátiles: pueden representar computadoras y los cables que las conectan, los autores y sus colaboraciones, o los estados de un cubo de Rubik y los movimientos que los transforman, esencialmente cualquier conjunto de conexiones, reales o abstractas. Para estudiar amistades en Regulartown, crearemos una red donde los nodos son personas y las conexiones son las amistades entre ellos.

Una forma útil de representar redes es imaginar los nodos como puntos y las conexiones como segmentos de línea, lo que también llamaremos enlaces. Este diagrama de red nos puede dar una idea de su estructura. Entonces, ¿cómo será la red de amistades en Regulartown? En algún momento puede parecer algo como esto:




Cada persona intentará encontrar a sus cuatro amigos y, a medida que nuevas personas se muden a la ciudad, buscarán a alguien con menos de cuatro amigos para conectarse. De esta manera, la red seguirá creciendo con el tiempo, expandiéndose continuamente en los enlaces a medida que se agregan nuevos nodos. (También es posible que se formen camarillas independientes, pero ignoraremos esa posibilidad en nuestro ejemplo).

Los diagramas de redes pueden iluminarse cuando indican una estructura clara. Pero cuando las redes se vuelven grandes o no exhiben el tipo de estructura regular de un Regulartown, los diagramas pueden ser menos útiles. Ayuda a desarrollar diferentes formas de analizar la estructura de una red. Una forma es pensar en la distribución del grado de la red.

En una red, el número de conexiones que tiene un nodo se conoce como el "grado" de ese nodo. Un nodo con un alto grado está conectado a muchos otros nodos; un nodo con un grado bajo está conectado a algunos otros nodos.



El grado de un nodo es una medida importante en una red, pero es local: solo describe la estructura de una red en un solo nodo. Pero al pensar en los grados de todos los nodos a la vez, podemos crear una herramienta útil para comprender la estructura global de una red.

En nuestra red de amistad, el grado de cada nodo es el número de amigos que tiene cada persona. En Regulartown, la mayoría de las personas tendrá cuatro amigos, por lo que la mayoría de los nodos tendrán el grado 4. Los residentes no tendrán más de cuatro amigos, pero algunos tendrán menos, por lo que habrá nodos con los grados 3, 2 o 1. Podemos resumir la distribución de grados como este:



Este histograma transmite información importante sobre la estructura de nuestra red. En este simple ejemplo, puede que no nos diga tanto como nuestro diagrama de red, pero veremos cómo las distribuciones de grado pueden ser herramientas poderosas para comprender diferentes tipos de redes.

Vayamos a una nueva ciudad. En Randomville, las amistades suceden al azar. Dado que la aleatoriedad puede ser un asunto complicado, seamos claros sobre lo que queremos decir: imaginaremos a cada persona de la ciudad como un nodo en una red, lo que hace que cada posible ventaja sea una posible amistad. Para generar una amistad aleatoria, elegiremos uno de esos posibles enlaces al azar y lo dibujaremos, estableciendo una conexión entre esos dos nodos y, por lo tanto, una amistad entre esas dos personas.

¿Cómo sería la red de Randomville? Suponiendo que comencemos con un grupo de nodos y agregamos al azar un grupo de enlaces, la imagen puede verse así:


Puede ser difícil ver la estructura en este diagrama. Pero el grado de distribución de esta red es esclarecedor. Si bien no es fácil calcular directamente, podemos razonar a través de algunas propiedades importantes usando un ejemplo simple.

Imagina que eres una de las 10 personas en Randomville. ¿Cuántas amistades posibles hay? Cada una de las 10 personas podría estar conectada a las otras nueve, por lo que parece que potencialmente podría dibujar 10 × 9 = 90 enlaces. Pero esto en realidad cuenta cada amistad posible dos veces: una para cada amigo. Entonces, el número total de amistades posibles es realmente 90 dividido por 2, o 45.

Ahora digamos que elegimos al azar una amistad, es decir, seleccionamos al azar uno de los 45 enlaces posibles en nuestra red. ¿Cuál es la probabilidad de que se conecte con usted? Bueno, hay nueve enlaces posibles que se extienden desde usted a cada uno de los otros nueve nodos. Dado que nueve de los 45 enlaces se conectan con usted, la probabilidad de que un enlace seleccionado al azar se conecte con usted es de 945 = 15, o 20 por ciento.

Pero este mismo argumento se aplica a todos en Randomville, por lo que cada nodo tiene un 20% de probabilidad de estar conectado al enlace seleccionado al azar. Ahora, a medida que se agregan los enlaces (y los nodos), estas probabilidades cambiarán ligeramente, pero a la larga seguirán siendo aproximadamente las mismas. Esto significa que las amistades se distribuirán de manera bastante uniforme alrededor de Randomville. Habrá algunas variaciones leves aquí y allá, pero tener pocos amigos o muchos amigos será poco probable. En Randomville, es probable que casi todos terminen con algo parecido a un número promedio de amigos.

 Estas características familiares están incorporadas en la distribución de grado "binomial" de una red aleatoria típica.

 

Al observar solo la distribución en grados de esta red, podemos inferir un tipo particular de uniformidad: cuando se trata de conectividad, la mayoría de los nodos son promedio y muy pocos son extremos. Esta es una información útil cuando se trata de entender la estructura de la red. (A medida que se agregan nodos, digamos, cuando nuevas personas vienen a la ciudad, la distribución cambiará ligeramente, pero las características generales persistirán).

Ahora, ninguno de estos dos ejemplos, la regla de la mayoría de los cuatro amigos de Regulartown o las amistades seleccionadas al azar de Randomville, son modelos realistas de amistad. Las personas pueden tener más de cuatro amigos, y tener muchos amigos no es tan inusual como sugiere la distribución binomial. Entonces, ¿qué es un modelo de amistad más realista?

A medida que establezca conexiones con amigos y amigos de amigos, la estructura de sus amistades probablemente compartirá características comunes a otras redes del mundo real como redes de alimentos, interacciones de proteínas e Internet. Estas características caracterizan las llamadas redes "sin escala", un modelo de conectividad que ha llegado a dominar la ciencia de redes en los últimos 20 años. Investigadores de matemáticas, física, economía, biología y ciencias sociales han visto los signos reveladores de redes sin escala en sus campos dispares.



Una compleja red sin escala que representa los metadatos de una red social.
Martin Grandjean

La estructura de las redes sin escala depende del principio simple de "conexión preferencial". La conexión preferencial es una regla de crecimiento de la red rica en riqueza: un nodo con muchas conexiones existentes es más probable que obtenga nuevas conexiones que un nodo con pocas conexiones Conexiones existentes. Las nuevas conexiones muestran una preferencia por los nodos de alto grado.

¿Tiene sentido esto en el contexto de la formación de la amistad? En general, parece razonable argumentar que una persona con muchos amigos tendrá más probabilidades de hacer nuevos amigos. Como ya están conectados a más personas, es más probable que conozcan a nuevas personas a través de esas conexiones existentes. Tener más amigos crea más oportunidades para hacer nuevos amigos. Y el hecho de que ya tengan muchos amigos sugiere que pueden tener algún tipo de capacidad o afinidad para hacer amigos. Esto probablemente atraerá a otros, al igual que los sitios web populares dibujan enlaces de otros sitios y blogs, y las ciudades establecidas invitan a nuevas líneas de ferrocarril y rutas aéreas.

Si bien hay múltiples factores que intervienen en el desarrollo de redes sin escala, muchos consideran que el vínculo preferencial es el más fundamental. Y tiene una consecuencia fascinante en la distribución de un grado de red.



El apego preferencial predice una distribución de grados "de cola gruesa". La mayoría de los nodos en la red serán de grado bajo, pero habrá nodos de grado cada vez más alto. Esto contrasta con las redes de amistad de Regulartown y Randomville, que tenían pocos o ningún nodo de alto grado.

Estos nodos de alto grado, que actúan como centros, son una característica crítica de las redes sin escala. Son las mariposas sociales de las redes de amistad, los bancos en el centro de las economías, los enrutadores centralizados que recorren las líneas regionales de Internet, los Kevin Bacons del mundo en funciones. Los hubs pueden aportar una sensación de pequeño mundo a una red enorme; por ejemplo, dos usuarios seleccionados al azar de los dos mil millones de personas en Facebook son, en promedio, menos de cuatro amigos. Y la cantidad y diversidad de hubs también proporciona a las redes sin escalas resistencia frente a ciertos tipos de fallas: por ejemplo, incluso si fallan muchas conexiones a Internet, los mensajes aún se pueden transmitir, en parte porque todavía habrá muchas formas de llegar y salir de la red. muchos centros (hubs).

Si bien parece haber acuerdo sobre la utilidad de las redes sin escala y sus características de alto nivel, esta área de estudio no está exenta de controversia. Las características matemáticas precisas de estas distribuciones de grados pueden ser difíciles de interpretar. En su libro Linked: The New Science of Networks, el pionero de la ciencia en redes y físico Albert-László Barabási argumentó que las redes que exhiben un apego preferencial tendrán distribuciones de grado que esencialmente siguen una "ley de poder". Las distribuciones de la ley de poder se ven en muchas situaciones físicas, Como las leyes de la inversa al cuadrado de la gravitación y los campos eléctricos. Pueden representarse como funciones de la forma  f(x)=axk, y sus gráficas suelen tener este aspecto:



Las distribuciones de la ley de poder tienen colas gruesas. ¿Pero qué tan gordo? Es decir, ¿cuántos concentradores de cada grado deberíamos esperar en una red de este tipo? Un estudio publicado a principios de este año analizó 1,000 redes del mundo real y concluyó que solo un tercio tenía distribuciones de grado que podrían ser descritas razonablemente por una distribución de ley de poder. Muchas de las redes tenían distribuciones de grado que podrían describirse con mayor precisión utilizando distribuciones "exponenciales" y "log-normal". Pueden tener las características de alto nivel características de las redes sin escala, pero sin la distribución de grado esperada, ¿pueden realmente considerarse sin escala? ¿Y realmente importa?

Importa si queremos conectar nuestras teorías a nuestros datos. ¿Es el apego preferencial realmente el factor principal en la formación de redes sin escala? ¿O hay otros factores que también desempeñan roles sustanciales, factores que pueden impulsar las distribuciones de grados en diferentes direcciones? Responder a estas preguntas y descubrir cuáles son las preguntas correctas que se formulan a continuación, es parte de comprender completamente la naturaleza y la estructura de las redes, cómo se desarrollan y cómo evolucionan.

Y la controversia también nos recuerda que, al igual que nuestras redes, las matemáticas en sí mismas son un conjunto de conexiones en evolución. La investigación contemporánea está desafiando las conjeturas de 20 años en el campo relativamente joven de la ciencia de redes. A medida que las nuevas ideas se unen a la red, nos conectan a las matemáticas del pasado y del futuro. Entonces, cuando se trata de matemáticas, al igual que en las amistades, harás bien en encontrar los centros y maximizar tu título.

Ejercicios

1. ¿Cómo sería una red de amistad si cada persona tuviera exactamente dos amigos?
2. En Regulartown cada persona puede tener hasta cuatro amigos. Es posible que se formen camarillas en Regulartown, pequeños grupos en los que cada persona tiene exactamente cuatro amigos. ¿Cuántas personas podrían estar en tal pandilla? (Sugerencia: la respuesta está relacionada con un sólido platónico).
3. Nuestras redes de amistad confían en que la amistad sea una relación simétrica, es decir, si A es amigo de B, entonces B es amigo de A. ¿Cómo podríamos ajustar nuestro modelo de red para adaptarse a una noción no simétrica de amistad, donde A podría ser amigo de B pero B no ser amigos con A?
4. En Friendville, todos son amigos de todos los demás. Si hay n personas en Friendville, ¿cuántas amistades hay?

No hay tanta evidencia de redes libre de escala en la realidad

Escasa evidencia de leyes de potencia encontradas en redes del mundo real

Un nuevo estudio desafía una de las ideas más celebradas y controvertidas en la ciencia de redes.

Erica Klarreich | Quanta Magazine



Un artículo publicado en línea el mes pasado ha reavivado un debate sobre una de las afirmaciones más antiguas y sorprendentes en la era moderna de la ciencia de redes: la proposición de que las redes más complejas en el mundo real, desde la World Wide Web hasta proteínas interactuando en una célula, están "libres de escala". Hablando en términos generales, eso significa que algunos de sus nodos deberían tener muchas más conexiones que otras, siguiendo una fórmula matemática llamada ley de poder, de modo que no haya una sola escala que caracterice a la red.

Las redes puramente aleatorias no obedecen las leyes de poder, así que cuando los primeros defensores del paradigma sin escalas comenzaron a ver leyes de poder en las redes del mundo real a fines de la década de 1990, las vieron como evidencia de un principio de organización universal subyacente a la formación de estos diversos redes. La arquitectura de la ausencia de escalas, argumentaron los investigadores, podría proporcionar información sobre cuestiones fundamentales, como la probabilidad de que un virus cause una epidemia, o qué tan fácilmente los hackers pueden deshabilitar una red.

En las últimas dos décadas, una avalancha de artículos ha afirmado la ausencia de escala de cientos de redes del mundo real. En 2002, Albert-László Barabási - un físico convertido en red científico que fue pionero en el paradigma de redes sin escala - escribió un libro para una audiencia general, Linked, en el que afirmaba que las leyes de poder son omnipresentes en redes complejas.

Las redes del mundo real exhiben una rica diversidad estructural que probablemente requerirá nuevas ideas y mecanismos para explicar.
Anna Broido y Aaron Clauset

"Las leyes naturales increíblemente simples y de largo alcance rigen la estructura y la evolución de todas las redes complejas que nos rodean", escribió Barabási (que ahora se encuentra en la Universidad Northeastern de Boston) en Linked. Más tarde agregó: "Descubrir y explicar estas leyes ha sido una atracción fascinante de la montaña rusa durante la cual hemos aprendido más sobre nuestro mundo complejo e interconectado de lo que se conocía en los últimos cien años".

Pero a lo largo de los años, otros investigadores han cuestionado tanto la omnipresencia de la ausencia de escala como la medida en que el paradigma ilumina la estructura de redes específicas. Ahora, el nuevo artículo informa que pocas redes del mundo real muestran evidencia convincente de la ausencia de escala.

En un análisis estadístico de casi 1.000 redes extraídas de la biología, las ciencias sociales, la tecnología y otros dominios, los investigadores descubrieron que solo el 4 por ciento de las redes (como ciertas redes metabólicas en las células) superaban las pruebas más sólidas del documento. Y para el 67 por ciento de las redes, incluidas las redes de amistad de Facebook, las redes alimentarias y las redes de distribución de agua, las pruebas estadísticas rechazaron una ley de poder como una descripción plausible de la estructura de la red.

"Estos resultados socavan la universalidad de las redes sin escala y revelan que las redes del mundo real exhiben una rica diversidad estructural que probablemente requerirá nuevas ideas y mecanismos para explicar", escribieron los autores del estudio, Anna Broido y Aaron Clauset de la Universidad de Colorado. Boulder


Aaron Clauset ha descubierto que las redes libres de escala son de naturaleza rara, contrariamente a la creencia popular.
Universidad de Colorado, Boulder

Los científicos de redes están de acuerdo, en general, en que el análisis del artículo es estadísticamente sólido. Pero cuando se trata de interpretar sus hallazgos, el documento parece funcionar como una prueba de Rorschach, en la que tanto los defensores como los críticos del paradigma libre de escala ven lo que ya creían que era cierto. Gran parte de la discusión se ha desarrollado en vigorosos debates de Twitter.

Los partidarios del punto de vista libre de escala, muchos de los cuales llegaron a la ciencia de la red a través de la física, argumentan que la ausencia de escala pretende ser un modelo idealizado, no algo que captura precisamente el comportamiento de las redes del mundo real. Muchas de las propiedades más importantes de las redes libres de escala, dicen, también son válidas para una clase más amplia llamada "redes de cola pesada" a la que pueden pertenecer muchas redes del mundo real (estas son redes que tienen centros significativamente más conectados que la red aleatoria tiene, pero no necesariamente obedece una ley de poder estricta).

Los críticos objetan que términos como "sin escalas" y "colas pesadas" se mencionan en la literatura de ciencias de la red de manera tan vaga e inconsistente como para hacer que las afirmaciones centrales del sujeto sean infalsificables.

El nuevo documento "fue un intento de tomar un enfoque basado en datos para ordenar esta cuestión", dijo Clauset.

La ciencia de la red es una disciplina joven -la mayoría de sus trabajos datan de los últimos 20 años- y la conflictividad que rodea al periódico y el vocabulario propio de la ausencia de escala se deriva de la inmadurez del campo, dijo Mason Porter, matemático y científico de redes de la Universidad. de California, Los Angeles. La ciencia de la red, dijo, "todavía está en el Salvaje Oeste".

¿Una ley universal?

Muchas redes, desde celosías perfectamente ordenadas hasta redes puramente aleatorias, tienen una escala característica. En una retícula cuadrada bidimensional, por ejemplo, cada nodo está conectado exactamente a otros cuatro nodos (por lo que los matemáticos dicen que el "grado" del nodo es cuatro). En una red aleatoria, en la que cada par de nodos tiene alguna probabilidad constante de estar conectado entre sí, los diferentes nodos pueden tener diferentes grados, pero estos grados sin embargo se agrupan bastante cerca de la media. La distribución de grados tiene aproximadamente la forma de una curva de campana, y los nodos con un número desproporcionadamente grande de enlaces nunca ocurren, así como la distribución de las alturas de las personas se agrupa en un rango de 5 a 6 pies y nadie es un millón ( o incluso 10) pies de altura.

Pero cuando un equipo dirigido por Barabási examinó una muestra de la World Wide Web en 1998, vio algo muy diferente: algunas páginas web, como las páginas principales de Google y Yahoo, se vincularon con mucha más frecuencia que otras. Cuando los investigadores trazaron un histograma de los grados de los nodos, parecía seguir la forma de una ley de potencia, lo que significa que la probabilidad de que un nodo dado tuviera un grado k era proporcional a 1 / k elevado a una potencia. (En el caso de los enlaces entrantes en la World Wide Web, este poder fue de aproximadamente 2, informó el equipo).


Revista Lucy Reading-Ikkanda / Quanta

En una distribución de la ley de poder, no hay una escala característica (por lo tanto, el nombre "sin escala"). Una ley de poder no tiene ningún pico: simplemente disminuye para grados más altos, pero de forma relativamente lenta, y si amplía las secciones de su gráfico, se verá similar. Como resultado, aunque la mayoría de los nodos aún tienen un grado bajo, los centros con una enorme cantidad de enlaces aparecen en pequeñas cantidades, en todas las escalas.

El paradigma libre de escala en las redes surgió en un momento histórico en el que las leyes de poder habían adquirido un papel de gran envergadura en la física estadística. En los años sesenta y setenta, desempeñaron un papel clave en las leyes universales que subyacen a las transiciones de fase en una amplia gama de sistemas físicos, un hallazgo que le valió a Kenneth Wilson el Premio Nobel de Física de 1982. Poco después, las leyes de poder formaron el núcleo de otros dos paradigmas que se extendieron por el mundo de la física estadística: los fractales y una teoría sobre la organización en la naturaleza llamada criticidad autoorganizada.

Para cuando Barabási estaba centrando su atención en las redes a mediados de la década de 1990, los físicos estadísticos estaban preparados para ver leyes de poder en todas partes, dijo Steven Strogatz, un matemático de la Universidad de Cornell (y miembro del consejo asesor de Quanta). En física, dijo, hay una "religión de ley de poder".

Hubo un efecto de vagón en el que la gente hacía cosas indiscriminadamente.Mason Porter

El equipo de Barabási publicó sus hallazgos en Nature en 1999; un mes después, Barabási y su entonces estudiante de posgrado Réka Albert (ahora un científico de la red en la Universidad Estatal de Pensilvania) escribieron en Science, en un documento que ha sido citado más de 30,000 veces, que las leyes de poder describen la estructura no solo del World Wide Web pero también de muchas otras redes, incluida la red de colaboración de actores de cine, la red de energía eléctrica del oeste de los Estados Unidos y la red de citas de artículos científicos. La mayoría de las redes complejas, afirmó Barabási unos años más tarde en Linked, obedecen una ley de poder, cuyo exponente suele ser entre 2 y 3.

Un simple mecanismo llamado "fijación preferencial", argumentaron Albert y Barabási, explica por qué aparecen estas leyes de poder: cuando un nuevo nodo se une a una red, es más probable que se conecte a un nodo llamativo y de alto grado que a un oscuro y oscuro grado nodo. En otras palabras, los ricos se hacen más ricos y los centros se vuelven más exclusivos.

Las redes libres de escala, escribió el equipo de Barabási en el número del 27 de julio de 2000 de Nature, tienen algunas propiedades clave que las distinguen de otras redes: son robustas al mismo tiempo contra fallas en la mayoría de los nodos y vulnerables a los ataques dirigidos contra los centros. La portada de Nature pregonó esta última propiedad como el "talón de Aquiles de internet" (una caracterización que desde entonces ha sido disputada rotundamente por expertos en Internet).

El trabajo de Barabási electrizó a muchos matemáticos, físicos y otros científicos, y fue instrumental en el lanzamiento del campo moderno de la ciencia de redes. Desató un torrente de papeles que afirmaban que una red del mundo real tras otra no tenía escalas, una especie de vínculo preferencial en el que los primeros artículos de Barabási se convirtieron en los centros neurálgicos. "Hubo un efecto de vagón (efecto de red) en el que las personas estaban haciendo cosas indiscriminadamente", dijo Porter. La emoción se extendió a la prensa popular, con palabras sobre leyes universales de la naturaleza e historias de portada en Science, New Scientist y otras revistas.


Albert-László Barabási ha sido un campeón del paradigma de red sin escala. Su artículo de 1999 en Science argumentando que las redes libres de escala se encuentran ampliamente en la naturaleza ha sido citado más de 30,000 veces.

Desde el principio, sin embargo, el paradigma libre de escala también atrajo retrocesos. Los críticos señalaron que el apego preferencial está lejos del único mecanismo que puede dar lugar a leyes de poder, y que las redes con la misma ley de poder pueden tener topologías muy diferentes. Algunos científicos de redes y expertos en el campo arrojan dudas sobre la ausencia de escala de redes específicas como redes eléctricas, redes metabólicas y la internet física.

Otros se opusieron a la falta de rigor estadístico. Cuando una ley de poder se grafica en un "diagrama de registro y registro" (en el que los ejes xey tienen escalas logarítmicas) se convierte en una línea recta. Entonces, para decidir si una red estaba libre de escalas, muchos de los primeros investigadores simplemente observaron un diagrama log-log de los grados de la red. "Incluso bizqueábamos la pantalla de la computadora desde un ángulo para tener una mejor idea si la curva era recta o no", recuerda el científico de redes Petter Holme del Instituto de Tecnología de Tokio en una publicación de blog.

"Debe haber un millar de papeles", dijo Clauset, "en los que las personas planifican la distribución de títulos, la trazan y dicen que no tiene escalas sin realmente hacer un trabajo estadístico cuidadoso".

En respuesta a estas críticas, a lo largo de los años algunos de los físicos que estudiaban la ausencia de escalas cambiaron su enfoque a la clase más amplia de redes de cola pesada. Aun así, un flujo constante de artículos continuó afirmando que no hay escala para una creciente gama de redes.

Y la discusión quedó empañada por la falta de coherencia, de un periódico a otro, sobre lo que realmente significaba "sin escala". ¿Era una red sin escala una que obedecía a una ley de poder con un exponente entre 2 y 3, o una en la cual esta ley de poder surgía de un vínculo preferencial? ¿O fue solo una red que obedece a alguna ley de poder, o sigue una ley de poder en algunas escalas, o algo aún más impresionista?

"La falta de precisión del lenguaje es una frustración constante", dijo Porter.

Clauset, quien es activo en los esfuerzos de divulgación, ha descubierto que muchos de los estudiantes con los que interactúa todavía piensan que la omnipresencia de las leyes de poder es ciencia establecida. "Me llamó la atención la cantidad de confusión que había en la próxima generación de científicos acerca de las redes libres de escala", dijo.

La evidencia contra la falta de escalabilidad estaba dispersa en la literatura, con la mayoría de los documentos examinando solo unas pocas redes a la vez. Clauset estaba bien posicionado para hacer algo mucho más ambicioso: su grupo de investigación ha pasado los últimos años seleccionando un compendio gigante en línea, el Índice de Redes Complejas de Colorado (ICON), que comprende más de 4.000 redes extraídas de economía, biología, transporte y otros dominios

"Queríamos tratar la hipótesis como falsable, y luego evaluar la evidencia en todos los dominios", dijo.

Barriendo la suciedad y el polvo

Para probar el paradigma sin escalas, Clauset y Broido, su estudiante de posgrado, sometieron a casi un millar de las redes de ICON a una serie de pruebas estadísticas cada vez más estrictas, diseñadas para medir qué definiciones de escalabilidad (si es que las hay) podrían ser plausibles explicar la distribución de grados de la red. También compararon la ley de poder con varios otros candidatos, incluyendo una distribución exponencial (que tiene una cola relativamente delgada) y una distribución "logarítmica normal" (que tiene una cola más pesada que una distribución exponencial, pero una cola más ligera que una ley de poder )

No hay una teoría general de redes.

Alessandro Vespignani

Broido y Clauset descubrieron que, en cerca de dos tercios de las redes, ninguna ley de poder encaja lo suficientemente bien como para explicar de manera plausible la distribución de grados. (Eso no significa que el tercio restante necesariamente obedezca una ley de poder, solo que no se descartó una ley de poder). Y cada una de las otras distribuciones candidatas superó a la ley de poder en muchas redes, con el registro normal superando al poder ley en el 45 por ciento de las redes y, esencialmente, vincular con él en otro 43 por ciento.

Solo alrededor del 4 por ciento de las redes cumplió con la prueba más fuerte de Broido y Clauset, lo que requiere, en términos generales, que la ley de poder sobreviva a su prueba de bondad de ajuste, tenga un exponente entre 2 y 3 y supere las otras cuatro distribuciones.

Para Barabási, estos hallazgos no socavan la idea de que la falta de escalabilidad subyace a muchas o más complejas redes. Después de todo, dijo, en las redes del mundo real, un mecanismo como el afecto preferencial no será lo único que ocurre: otros procesos a menudo empujarán a la red lejos de la pureza, haciendo que la red falle las pruebas de Broido y Clauset. Los científicos de la red ya han descubierto cómo corregir estos otros procesos en docenas de redes, dijo Barabási.

"En el mundo real, hay tierra y polvo, y esta suciedad y polvo estarán en sus datos", dijo Alessandro Vespignani de Northeastern, otro físico convertido en científico de la red. "Nunca verás la ley de poder perfecta".

Como una analogía, observó Barabási, una roca y una pluma caen a velocidades muy diferentes a pesar de que la ley de la gravedad dice que deberían caer a la misma velocidad. Si no supiera sobre el efecto de la resistencia del aire, dijo, "concluiría que la gravitación es incorrecta".

Clauset no encuentra esta analogía convincente. "Creo que es bastante común para los físicos que están entrenados en mecánica estadística ... usar este tipo de analogías de por qué su modelo no debe mantenerse a un nivel muy alto".


Anna Broido es coautora del nuevo artículo.

Si observaras 1,000 objetos que caen en lugar de solo una roca y una pluma, dijo Clauset, surgiría una imagen clara de cómo funcionan tanto la gravedad como la resistencia al aire. Pero su análisis y el de Broido de casi 1,000 redes no han arrojado una claridad similar. "Es razonable creer que un fenómeno fundamental requeriría un trabajo de detective menos personalizado" de lo que pide Barabási, escribió Clauset en Twitter.

"La suposición tácita y común de que todas las redes están libres de escalas y depende de nosotros descubrir cómo verlas de esa manera, eso suena como una hipótesis no infalsificable", dijo.

Si algunas de las redes rechazadas por las pruebas involucran un mecanismo libre de escala superpuesto por otras fuerzas, entonces esas fuerzas deben ser bastante fuertes, dijeron Clauset y Strogatz. "Al contrario de lo que vemos en el caso de la gravedad ... donde los efectos dominantes son realmente dominantes y los efectos más pequeños en realidad son pequeñas perturbaciones, parece que lo que sucede con las redes es que no hay un solo efecto dominante", dijo Strogatz. .

Para Vespignani, el debate ilustra un abismo entre las mentalidades de físicos y estadísticos, quienes tienen perspectivas valiosas. Los físicos están tratando de ser "los artistas de la aproximación", dijo. "Lo que queremos encontrar es algún principio de organización".

El paradigma libre de escala, dijo Vespignani, brinda una valiosa intuición sobre cómo debería comportarse la clase más amplia de redes de cola pesada. Muchos de los rasgos de las redes sin escala, incluida su combinación de solidez y vulnerabilidad, son compartidos por redes de cola pesada, dijo, por lo que la pregunta importante no es si una red es precisa o no, sino si tiene una cola pesada. "Pensé que la comunidad estaba de acuerdo con eso", dijo.

Pero Duncan Watts, un científico de redes de Microsoft Research en la ciudad de Nueva York, objetó en Twitter que este punto de vista "realmente está cambiando las metas". Al igual que con "sin escala", dijo, el término "cola pesada" se usa de diferentes maneras en la literatura, y los dos términos a veces se combinan, lo que dificulta la evaluación de los diversos reclamos y pruebas. La versión de "cola larga" que está lo suficientemente cerca como para "escalar" para que muchas propiedades se transfieran no es una clase de redes especialmente amplia, dijo.

La ausencia de escala "en realidad significó algo muy claro una vez, y casi con certeza esa definición no se aplica a muchas cosas", dijo Watts. Pero en lugar de que los científicos de la red retrocedieran y retractaran las primeras afirmaciones, dijo, "el reclamo simplemente se transforma lentamente para ajustarse a toda la evidencia, al mismo tiempo que mantiene su factor sorpresa de etiqueta de marca. Eso es malo para la ciencia ".

A Porter le gusta bromear que si las personas quieren discutir algo polémico, deberían dejar de lado la política de EE. UU. Y hablar sobre las leyes de poder. Pero, dijo, hay una buena razón por la cual estas discusiones son tan tensas. "Tenemos estos argumentos porque los problemas son difíciles e interesantes".

Clauset ve su trabajo con Broido no como un ataque, sino como un llamado a la acción para los científicos de la red, para examinar un conjunto más diverso de posibles mecanismos y distribuciones de grados de lo que han estado haciendo. "Tal vez deberíamos considerar nuevas ideas, en lugar de intentar forzar viejas ideas para que encajen", dijo.

Vespignani está de acuerdo en que hay trabajo por hacer. "Si me preguntan, '¿Están todos de acuerdo en cuál es la verdad del campo?' Bueno, todavía no hay verdad", dijo. "No hay una teoría general de las redes".

Taxonomía de estructuras de comunidades en grandes redes

La caracterización de la estructura de la comunidad de las redes complejas

Andrea Lancichinetti, Mikko Kivelä, Jari Saramäki, Santo Fortunato
Publicado: 12 de agosto de 2010 | http://dx.doi.org/10.1371/journal.pone.0011976

Resumen

Trasfondo

La estructura de la comunidad es una de las propiedades fundamentales de las redes complejas y desempeña un papel crucial en su topología y función. Mientras que una cantidad impresionante de trabajo se ha hecho sobre la cuestión de la detección de la comunidad, muy poca atención se ha dedicado hasta ahora a la investigación de las comunidades en las redes reales.

Metodología / Principales conclusiones

Se presenta un análisis empírico sistemático de las propiedades estadísticas de las comunidades en la información general, la comunicación, tecnológicos, biológicos, y las redes sociales. Nos encontramos con que la organización mesoscópica de las redes de la misma categoría es notablemente similar. Esto se refleja en varias características de la estructura de la comunidad, que pueden ser utilizados como "huellas dactilares" de categorías específicas de la red. Mientras que las distribuciones de tamaño de la comunidad son siempre amplio, ciertas categorías de redes consisten principalmente en las comunidades en forma de árbol, mientras que otros tienen módulos más densos. ruta longitudes medias dentro de las comunidades inicialmente crecen logarítmicamente con el tamaño de la comunidad, pero se satura el crecimiento se ralentiza o para las comunidades más grandes que un tamaño característico. Este comportamiento está relacionado con la presencia de los centros dentro de las comunidades, cuyas funciones difieren entre categorías. También la inserción comunitaria de nodos, medido en términos de la fracción de enlaces dentro de sus comunidades, tiene una distribución característica para cada categoría.

Conclusiones / Importancia

Nuestros resultados, verificados por el uso de dos métodos de detección comunidad fundamentalmente diferentes, permiten una clasificación de las redes reales y allanan el camino a un modelado realista de la evolución de redes '.

Introducción

La moderna ciencia de los sistemas complejos ha experimentado un avance significativo después del descubrimiento de que la representación gráfica de este tipo de sistemas, a pesar de su simplicidad, revela un conjunto de características cruciales que son suficientes para revelar sus propiedades, función y evolución mecanismos estructurales generales [1] - [ 8]. Que representa un sistema complejo como un grafo que significa convertir las unidades elementales del sistema en los nodos, mientras que los enlaces entre nodos indican sus interacciones o relaciones mutuas. Muchas redes complejas se caracterizan por una amplia distribución del número de vecinos de un nodo, es decir, su grado. Esto es responsable de las propiedades peculiares tales como alta robustez frente a fallos aleatorios [9] y la ausencia de un umbral para la propagación de epidemias [10].

Otra característica importante de las redes complejas está representado por su estructura mesoscopic, caracterizado por la presencia de grupos de nodos, denominados comunidades o módulos, con una alta densidad de enlaces entre los nodos de un mismo grupo y una relativamente baja densidad de enlaces entre los nodos de diferentes grupos [11] - [14]. Esta organización compartimental de las redes es muy común en los sistemas de origen diverso. Ya se comentó en la década de 1960 que una estructura modular jerárquica es necesario para la robustez y estabilidad de los sistemas complejos, y les da una ventaja evolutiva [15].

La exploración de las comunidades de la red es importante por tres razones principales: 1) para revelar organización de la red a un nivel grueso, lo que puede ayudar a formular mecanismos realistas para su génesis y evolución; 2) para entender mejor los procesos dinámicos que tienen lugar en la red (por ejemplo, los procesos de innovación y epidemias), que pueden verse afectados considerablemente por la estructura modular del grafo de difusión; 3) para descubrir relaciones entre los nodos que no son aparentes mediante la inspección de la gráfica como un todo y que por lo general se pueden atribuir a la función del sistema.

Por lo tanto, no es sorprendente que los últimos años han sido testigos de una explosión de investigación sobre la estructura de la comunidad en los grafos. El problema principal, por supuesto, es la forma de detectar las comunidades, en primer lugar, y este es el punto esencial empujón por parte de la mayoría de los artículos sobre el tema que han aparecido en la literatura. Un gran número de métodos y técnicas se han diseñado, pero la comunidad científica todavía no ha acordado cuáles son los métodos más fiables y cuando un método deben o no deben ser adoptadas. Esto es debido al hecho de que está mal definida el concepto de comunidad. Dado que la atención se ha centrado en el desarrollo del método, muy poco se ha hecho hasta ahora para abordar una cuestión fundamental de este esfuerzo: ¿qué comunidades en redes reales parecen? Esto es lo que vamos a tratar de evaluar en este documento.

Investigaciones anteriores han demostrado que a través de una amplia gama de redes, la distribución de tamaños de la comunidad es amplio, con muchas pequeñas comunidades que coexisten con algunos otros mucho más grandes [12], [16] - [19]. La cola de la distribución puede ser a menudo bastante bien equipado por una ley de potencia. Leskovec et al. [20] han llevado a cabo una investigación exhaustiva de la calidad de las comunidades en las redes reales, medido por la puntuación de la conductancia [21]. Encontraron que la conductancia más bajo, lo que indica módulos bien definidos, se alcanza a las comunidades de un tamaño característico de los nodos, mientras que las comunidades mucho más grandes son más "mezclarse" con el resto de la red. Por esta razón se sugiere que la organización mesoscopic de redes puede tener una estructura de núcleo-periferia, donde la periferia se compone de pequeñas comunidades bien definidas y el núcleo comprende módulos más grandes, que están conectados más densamente entre sí y por lo tanto más difícil de detectar. Guimerá y Amaral han propuesto una clasificación de los nodos basados ​​en sus roles dentro de las comunidades [22].

Sin embargo, las propiedades fundamentales de las comunidades en las redes reales siguen siendo en su mayoría desconocidos. El descubrimiento de estas propiedades es el objetivo principal de este trabajo. Con este fin, hemos realizado un extenso análisis estadístico de la estructura de la comunidad de muchas redes reales de la naturaleza, la sociedad y la tecnología. La principal conclusión es que las comunidades se caracterizan por rasgos distintivos, que son comunes para las redes de la misma clase, pero que difieren de una clase a otra. Cabe destacar que dicha caracterización es independiente del método específico adoptado para encontrar las comunidades.

Métodos

Como nuestro objetivo es estudiar las características estadísticas de las comunidades, es necesario emplear conjuntos de datos en las redes grandes que contienen un gran número de comunidades de tamaño variable. Nuestros conjuntos de datos contienen los nodos, con excepción de las redes de interacción de proteínas (PIN), donde los más grandes conjuntos de datos disponibles son del orden de los nodos.

La Tabla 1 enumera los conjuntos de datos de red que hemos utilizado, junto con algunas estadísticas básicas. La mayoría de ellos han sido descargados de la red grande de conjunto de datos de la colección de Stanford (http://snap.stanford.edu/data/). Algunas redes están dirigidas originalmente (por ejemplo, el grafo de la web), pero los hemos tratado como no dirigida. Para más detalles sobre todas las redes se pueden encontrar en el Apéndice S1.


Table 1. Lista de datos de red usadas para el análisis


En general, hemos tenido en cuenta cinco categorías de redes:

• Redes de comunicación. Esta clase comprende la red de correo electrónico de una gran institución europea de investigación, y un conjunto de relaciones entre los usuarios de Wikipedia que se comunican a través de sus páginas de discusión. Tenga en cuenta que en los dos casos, la comunicación no es necesariamente personal, sino que implica, por ejemplo, correos electrónicos en masa, y por lo tanto estas redes no se puede considerar como redes sociales.
• Internet. Aquí tenemos dos mapas de Internet a nivel de sistemas autónomos (AS) (es decir, los nodos son grupos de enrutadores administrados por una sola entidad), producidas por los dos principales proyectos que exploran la topología de Internet: CAIDA (http: // www .caida.org /) y diez centavos (http://www.netdimes.org/).
• Redes de información. Esta clase incluye una red cita de pre-impresiones en línea en www.arxiv.org, una red de co-compra de los artículos vendidos por www.amazon.com y dos muestras de la gráfica Web, uno en representación de la berkeley.edu dominios y stanford.edu ( web-BS), y el otro fue lanzado por Google (web-G).
• Redes biológicas. Esta clase contiene los conjuntos de interacciones entre proteínas de tres organismos: mosca de la fruta (Drosophila melanogaster), levadura (Saccharomyces cerevisiae) y el hombre (Homo sapiens).
• Redes sociales. Aquí hemos considerado cuatro conjuntos de datos: una red de relaciones de amistad entre los usuarios de la comunidad en línea LiveJournal (www.livejournal.com); el conjunto de las relaciones de confianza entre los usuarios del sitio epinions.com opinión de los consumidores; la red de amistad de los usuarios del slashdot.org; la red de los usuarios de friedship www.last.fm.

El problema de la elección de un método para la detección de las comunidades es muy delicada. En primer lugar, se necesitan algoritmos muy eficiente, debido a que las redes que estudiamos son grandes. Este requisito excluye la mayoría de los métodos existentes. En segundo lugar, como se mencionó anteriormente, no existe un acuerdo común sobre un método de detección de la comunidad para todo uso. Esto se debe a la ausencia de una definición compartida de la comunidad, que se justifica por la naturaleza del problema en sí. En consecuencia, existe también la arbitrariedad en la definición de los procedimientos de ensayo fiables para los algoritmos. Sin embargo, existe un amplio consenso sobre la definición de comunidad originalmente introducido en un artículo de Condon y Karp [23]. La idea es que una red tiene comunidades si la probabilidad de que dos nodos de una misma comunidad están conectados excede la probabilidad de que los nodos de diferentes comunidades están conectados. Este concepto de comunidad se ha implementado para crear clases de grafos de referencia con las comunidades, tales como los introducidos por Girvan y Newman [11] y los grafos diseñados recientemente por Lancichinetti et al. [24], que integran al índice de referencia Girvan y Newman con distribuciones realistas de grado y el tamaño de la comunidad (LFR referencia). Investigaciones recientes indican que algunos algoritmos funcionan muy bien en el punto de referencia LFR [25]. En particular, el método introducido por Infomap Rosvall y Bergstrom [26] tiene una destacada actuación, y también es rápido y por lo tanto adecuado para grandes redes. Sin embargo, como todos los métodos de detección comunidad tiene su propio "sabor" y la preferencia hacia el etiquetado de determinados tipos de estructura de las comunidades, depender de un solo método no es suficiente si las conclusiones generales sobre la estructura de la comunidad deben ser presentados. Por lo tanto hemos verificado de forma cruzada los resultados obtenidos por Infomap con los producidos por un algoritmo muy diferente, la etiqueta de Propagación Método (LPM), propuesto por Leung et al. [27]. Este último ha demostrado ser fiable en el punto de referencia LFR y también es lo suficientemente rápido para manejar los sistemas más grandes de nuestra colección. Las descripciones detalladas de Infomap y la LPM se dan en el Apéndice S1. Aquí acabamos de señalar las profundas diferencias entre las dos técnicas. Infomap es un método de optimización global, que tiene como objetivo optimizar una función que expresa la calidad de la longitud del código de un paseo aleatorio de longitud infinita que tiene lugar en el grafo. El LPM es un método local, donde los nodos se atribuyen a la misma comunidad donde la mayoría de sus vecinos son. Las particiones obtenidos por ambos métodos para la misma red están en diferente general. Sin embargo, las características estadísticas generales de la estructura de la comunidad no parecen depender mucho de los detalles de las particiones. En lo que sigue, sólo se presentaron los resultados Infomap; para LPM, véase el Apéndice S1.

Resultados

Comenzamos el análisis por discutir brevemente la distribución de tamaños de la comunidad (Fig. 1). Vemos que, como era de esperar, para cada sistema hay una amplia gama de tamaños de la comunidad, que abarca varios órdenes de magnitud para los sistemas más grandes. Esto está de acuerdo con estudios anteriores [12], [16] - [19]. Las formas generales de las distribuciones son sistemas similares a través de la misma clase. Las distribuciones de las redes biológicas muestran las diferencias más grandes, que, sin embargo, es probable que el resultado de ruido como las redes son más pequeñas. Para las redes biológicas, el análisis realizado con el LPM muestra ligeramente diferentes distribuciones, así superpuestos (véase el Apéndice S1).

Figura 1. Distribución de tamaños de la comunidad.
Todas las distribuciones son amplios, y similar para los sistemas de la misma categoría. Los puntos de datos son promedios dentro de contenedores logarítmicas del tamaño del módulo.




A continuación, nos dirigimos a la topología de las comunidades, y estudiamos la densidad de enlace de las comunidades y su dependencia del tamaño de la comunidad. La densidad de enlace de un subgrafo se define como la fracción de enlaces existentes a posibles enlaces,  donde  es el número de sus enlaces internos y su tamaño se mide en los nodos. Aquí, utilizamos la densidad de enlace a escala , que también equivale aproximadamente al grado promedio interna de nodos en la comunidad. Hemos elegido esta medida, ya que señala claramente la naturaleza de subgrafos. Para los árboles, siempre hay  enlaces, y por lo tanto . Por otro lado, para cliques completo  y por lo tanto .

La Figura 2 muestra el promedio de las densidades escalados de enlaces  como función del tamaño de la comunidad para diferentes redes. Las líneas discontinuas indican los casos límite (). Vemos que las densidades de enlace en las redes de comunicación e Internet son muy cerca del límite inferior, lo que significa que sus comunidades son en forma de árbol y contienen pocos o ningún bucle. En las redes de comunicación, la densidad de enlace reducido no depende del tamaño de la comunidad, mientras que en los grafos de grandes comunidades de Internet parecen algo más densa. Redes en estas dos clases son los más escasa en nuestra colección, como su muy pequeño grado medio indica que en general no son mucho más densos que los árboles (ver Tabla 1). Cabe señalar que, en general, la vista intuitiva en las comunidades es que son "denso" en comparación con el resto de la red. Sin embargo, como los métodos aplicados aquí producen particiones, las comunidades de una red en forma de árbol son también necesariamente árbol similar. Contrariamente a lo anterior, las redes de información mucho más denso revelan una imagen diferente, donde las comunidades son bastante objetos densos, con la densidad de escala creciente con s. Especialmente en la red de Amazon, las comunidades con  son casi camarillas. Las redes sociales muestran aún otro patrón: la densidad de escalado de los módulos crece bastante regularmente con el tamaño, aproximadamente como una ley de potencia. Comunidades en las redes sociales son en su mayoría muy lejos de los dos casos límite: son más densos que los árboles, pero mucho más escasa que camarillas, con la excepción de las pequeñas comunidades que aparecen más árbol similar. Por último, las redes biológicas se caracterizan por dos regímenes: para , las comunidades son muy similares a árboles; para valores más grandes de s la densidad escalada aumenta con s. En la Figura 3 se ilustran las comunidades características de las clases de red.

Figura 2. Densidad escalada de enlaces de las comunidades como una función del tamaño de la comunidad.
Las redes de comunicación e Internet consisten esencialmente de las comunidades de árboles similares, mientras que las comunidades de redes sociales e información son mucho más denso. Pequeños módulos en redes biológicas son a menudo árbol similar, mientras que los módulos de mayor tamaño son más densos. Los puntos de datos son promedios dentro de contenedores logarítmicas del tamaño del módulo s.


Figura 3. Ejemplos visualizada de las comunidades en las redes de diferentes clases.
Las redes de comunicación (a: correo electrónico, b: Wiki Discusión) contienen comunidades muy dispersas con cubos en forma de estrella. Estos centros dan lugar a muy bajo longitudes de camino más corto dentro de las comunidades (ver Fig. 2). cubos parecidos a estrellas también están presentes en las comunidades de Internet (C: Dimes, d: Caida), que son relativamente escasas también. La comunidad CAIDA muestra una estructura de "estrellas fusionado" bastante típico de estas redes (véase el Apéndice S1). Por el contrario, las redes de información contienen densas comunidades hasta grandes camarillas (e: Amazon, f: Web-BS). En las redes biológicas, cuanto mayor sea la comunidad, menos del árbol-como es (g: D. melanogaster, h: H. sapiens). Por último, las comunidades en las redes sociales aparecen en promedio bastante homogénea (i: Slashdot, j: Epinions).



La compacidad de las comunidades se puede medir utilizando la longitud del camino más corto promedio dentro de cada comunidad. Higo. 4 muestra los valores medios de en función del tamaño de la comunidad. Para todas las redes, las longitudes medias camino más corto son muy pequeñas, con la excepción de las redes sociales. Curiosamente, todas las parcelas revelan el mismo patrón básico, con independencia de la clase de red. Para las comunidades muy pequeñas, crece aproximadamente como el logaritmo del tamaño de la comunidad (indicado por la línea de puntos), que es la propiedad "mundo pequeño" se observa típicamente en redes complejas [28]. Llamamos a estos módulos microcomunidades. Para los tamaños del orden de, sin embargo, el aumento de repente se vuelve menos pronunciada, y varias curvas de alcanzar una meseta. Los módulos con nodos son macrocommunidades. La estabilización de la longitud del camino más corto medio en macrocommunidades se puede atribuir a la presencia de nodos con alto grado, es decir, cubos, que hacen caminos geodésicos en promedio corto. Hacemos notar que, dado que la mayoría de nuestros sistemas tienen grado distribuciones amplias, más cortas longitudes de paso son muy cortos [29], pero la brusca transición que observamos es inesperada y aparece como una característica completamente nueva.

Figura 4. El camino más corto promedios de duración dentro de las comunidades como una función del tamaño de la comunidad.
Después de un régimen inicial logarítmica "mundo pequeño" (línea de trazos en diagonal), el camino más corto promedio crece mucho más lento o se satura para las comunidades con nodos (línea punteada vertical). Los puntos de datos son promedios dentro de contenedores logarítmicas de tamaño del módulo.


Para las redes de comunicación, hay una meseta con  para . A medida que estas comunidades son en forma de árbol, esto indica que tienen una estructura semejante a una estrella donde la mayoría de los nodos están conectados a un concentrador central única y por lo tanto es igual a dos su distancia. Para las redes de Internet, la presencia conjunta de baja densidad y baja distancias también significa que los cubos dominan la estructura - aquí, estructuras "-combinado de la estrella" que consta de dos o más ejes que comparten muchos de sus vecinos fueron observados (véase la figura 3d.). Esta estructura garantiza una comunicación eficiente entre las unidades de los sistemas. Por el contrario, la información, social, y redes biológicas tener una densidad más alta y por lo tanto sus longitudes de trayectoria cortas son debido tanto a la densidad y la presencia de concentradores. Hubs juegan un papel menor en las redes sociales, ya que las longitudes medias camino más corto siguen aumentando poco a poco también para grandes.

La imagen de arriba se ve corroborada por la Fig. 5, que muestra la relación entre la máxima observada grado interna en la comunidad de nodos  y   como una función del tamaño s de la comunidad. Esta relación es igual a la unidad, si cualquier nodo está conectado a todos los otros nodos de su comunidad, y por lo tanto se cuantifica el predominio de los mayores centros dentro de las comunidades. Para las redes de comunicación,  es cercano a la unidad, incluso para los s grandes, de acuerdo con las observaciones anteriores sobre las comunidades en forma de estrella. Para Internet, esta cantidad disminuye con un poco, ya que las comunidades pueden contener varios concentradores que no se conectan a todos los demás nodos. En las redes de información, hay algunas diferencias. En los grafos Web, las comunidades más grandes contienen nodos de conexión (casi) toda la comunidad. A medida que la densidad de borde en estas comunidades es alta, puede haber varios de estos nodos - en una pandilla, todos los nodos tienen grado . Para las redes biológicas y sociales, hay una tendencia a la baja. Sobre todo en las redes sociales, hay pocas o ninguna centros dominantes en grandes comunidades. Estamos observación de que el acuerdo entre las curvas de la figura. 5 es más cualitativo que cuantitativo (sobre todo para las redes sociales y biológicas), en desacuerdo con otras firmas. Esto se debe a las parcelas se refieren a las propiedades de una clase muy restringido de nodos "extremales", es decir, de los centros de la comunidad. Por lo tanto, por una parte, el ruido de las curvas es más grande. Por otro lado, los métodos de detección de la comunidad tienen diferentes maneras de tratar a los centros: mientras que los métodos generalmente tienden a ponerlos "dentro de" comunidades, otros (como Infomap) de vez en cuando les ponen "entre" comunidades.

Figura 5. La máxima observada grado interno de nodos como una función del tamaño de la comunidad.
Esta cantidad es igual a uno si cualquier nodo está vinculado a todos los demás nodos de su comunidad, y por lo tanto cuantifica el predominio de los centros dentro de las comunidades.




Veamos próxima a echar un vistazo más de cerca a la relación entre los nodos individuales y estructura de la comunidad. Aquí, la propiedad más natural para investigar es el grado interno , que indica el número de vecinos de un nodo en su comunidad. Medimos la incrustación de un nodo en su comunidad con la relación , que caracteriza el grado en que el vecindario del nodo pertenece a la misma comunidad que el propio nodo. La distribución de probabilidad de la relación de arraigo de todos los nodos de sus respectivas redes se muestra en la Fig. 6. Uno directamente puede suponer que, en promedio, el arraigo de nodos sería bastante grande, y una fracción sustancial de sus vecinos deben residir dentro de sus respectivas comunidades. Sin embargo, la Fig. La figura 6 muestra un patrón más complejo, donde los valores  más pequeños de no son nada raro. Todas nuestras redes se caracterizan por una fracción sustancial de los nodos que son totalmente interna a sus comunidades, es decir, que no tienen enlaces a fuera de su comunidad y por lo tanto . Estos corresponden a los puntos de datos más a la derecha en cada parcela, y tales nodos normalmente ascienden a más del 50% todos los nodos. Estos nodos tienen en su mayoría un bajo grado (por ejemplo, los grados-uno nodos conectados a hubs en las redes de comunicación). Redes en la misma clase siguen esencialmente un patrón muy similar. Las redes de comunicación e Internet tienen perfiles muy similares a futuro, donde la distribución tiene un pico alrededor de . Las redes de información, en cambio, tienen un perfil bastante diferente, con un incremento suave inicial de llegar a una meseta en alrededor . Las redes biológicas, a pesar de la inevitable ruido, también muestran una imagen consistente a través de conjuntos de datos. Ellos se asemejan algo a las redes de comunicación y de Internet, con una subida inicial hasta que , seguido de un lento descenso para los valores más grandes. Las redes sociales tienen una distribución bastante plana en toda la gama, con pequeñas variaciones de un sistema a otro. Esto significa que hay muchos nodos con la mayor parte de sus vecinos fuera de su comunidad. La mayoría de las técnicas de detección de la comunidad, incluidos los que hemos adoptado, tienden a asignar a cada nodo de la comunidad, que contiene la mayor fracción de sus vecinos. Esto implica que si un nodo tiene sólo unos pocos vecinos dentro de su propia comunidad, que tendrá aún menos vecinos dentro de otras comunidades individuales. Dichos nodos actúan como "intermediarios" entre muchos módulos diferentes, y se comparten entre muchas comunidades en lugar de pertenecer a una única comunidad. Por lo tanto, sería más correcto para asignarlos a más de una comunidad. La superposición de las comunidades son conocidos por ser muy comunes en las redes sociales, y se han introducido técnicas especializadas para su detección [16], [30] - [35].

Figura 6. Distribución de probabilidad para ISA , la fracción de los vecinos de un nodo que pertenece a su propia comunidad.
Redes en la misma clase presentan un comportamiento similar.



En el Apéndice S1 se investigan otras propiedades estadísticas de las comunidades.

Discusión

Desde el advenimiento de la ciencia de las redes complejas, su atención se ha desplazado desde la comprensión de la aparición y la importancia de las características a nivel de sistema para mesoscopic propiedades de las redes. Estos se manifiestan en las comunidades, es decir subgraphs densamente conectada. Las comunidades son ubicuos en las redes y por lo general juegan un papel importante en la función de un sistema complejo - módulos en las redes de interacción proteína-se refieren a funciones biológicas específicas, y las comunidades en las redes sociales representan el nivel fundamental de la organización en una sociedad. El doble problema de definir formalmente y detectar con precisión las comunidades ha atraído hasta ahora la mayor parte de la atención, a costa de una falta de comprensión de las propiedades estructurales fundamentales de las comunidades. Nuestro objetivo en este trabajo ha sido el de descubrir algunas de estas propiedades.

Nuestros resultados indican que las comunidades detectados en las redes de la misma pantalla clase características estructurales sorprendentemente similares. Esto es notable, ya que algunas clases son muy amplio y comprenden sistemas de diferente origen (por ejemplo, la clase de redes de información, que incluye grafos de citación, co-compra y la Web). El resultado se verifica mediante dos métodos de detección de la comunidad que son diferentes tanto partición-basan, pero se basan en principios completamente diferentes. De acuerdo con los resultados anteriores, las distribuciones de tamaño de la comunidad son amplios para todos los sistemas que hemos estudiado. densidades de enlace dentro de las comunidades dependen en gran medida de la clase de red. La longitud media de camino más corto muestra un comportamiento similar en todas las clases, en un principio aumentará de manera logarítmica en función del tamaño de la comunidad (microcomunidades) y luego la ralentización o la saturación de las comunidades de tamaño  (macrocommunities). En combinación con nuestros resultados en la densidad de enlace en las comunidades, el comportamiento de las longitudes de trayectoria revela un cuadro donde los nodos de alto grado son muy dominantes en las comunidades de ciertas clases (de comunicación, Internet) y juega un papel menos importante en la conectividad de los demás, especialmente redes sociales. Esta imagen se ve corroborada por el análisis de los grados internos en la comunidad máximas de nodos. Por último, también la distribución de probabilidad de la fracción de los enlaces internos para los nodos muestra una firma clara para cada una de las clases consideradas.

Las firmas que hemos encontrado son una especie de identificación de la red, y podrían utilizarse tanto para clasificar otros sistemas e identificar nuevas clases de red. Por otra parte, podrían convertirse en elementos esenciales de los modelos de red, con la ventaja de las descripciones más precisas de las redes reales y las predicciones de su evolución.

Aunque nuestros resultados se han obtenido utilizando dos métodos diferentes, sus méritos generales de validez alguna discusión. A medida que el concepto de "comunidad" es mal definido, todos los métodos para la detección de las comunidades se basa en una interpretación específica del concepto. Además, las filosofías subyacentes de los métodos pueden diferir en gran medida. Métodos que requieren que las comunidades son "local" muy densa, como camarilla percolación [16], detectaría sólo unas pocas comunidades en las redes de comunicación e Internet, ya que no tienen en cuenta los árboles o estrellas como comunidades - sin embargo, este resultado sería coherente para las redes de la misma clase. Por otra parte, es evidente que los métodos basados ​​en particiones descuidar el hecho de que los nodos pueden participar en múltiples comunidades. Sin embargo, vale la pena señalar que cualquiera que sea el método utilizado, las comunidades resultantes son subgrafos reales de la red en estudio, es decir, sus bloques de construcción. Por lo tanto sus propiedades estadísticas reflejan la organización mesoscópicas de las redes, y nuestros resultados indican que esta organización es similar dentro de las clases de redes.

Un artículo muy reciente [36] ha llegado a una conclusión similar con un enfoque totalmente diferente, donde las taxonomías de redes se construyeron sobre la base de firmas derivadas de la modularidad de Newman y Girvan.

Referencias