domingo, 24 de septiembre de 2017

Clusters bibliométricos sobre el Antropoceno

Mapeando una controversia de nuestro tiempo: El Antropoceno

Simone Belli | Lo Sguardo




Ofrecemos un análisis bibliométrico de la literatura y autores de la polémica disciplina antropocénica. Gracias a las herramientas digitales, comprendemos esta complejidad aprovechando la literatura existente y las redes digitales. Con el fin de apreciar el carácter interdisciplinario de la controversia, se muestran agrupamientos de co-citado publicaciones, co-autores, y co-occurrencia detérminos en los campos de las ciencias sociales, la agricultura y la biología, la ciencia ambiental y la Tierra y la ciencia planetaria. El carácter multidisciplinario de la investigación antropocénica se refleja en el análisis de la co-citación y en el análisis del término co-ocurrencia. Encontramos dos grupos de términos coexistentes, que representan acuerdo y desacuerdo con Antropoceno, y ofrecen una comparación de las obras emblemáticas presentadas en la red.



viernes, 22 de septiembre de 2017

Percolación y crecimiento explosivo detrás de la viralidad

Las nuevas leyes de las redes explosivas


Los investigadores están descubriendo las leyes ocultas que revelan cómo crece Internet, cómo se propagan los virus y cómo estallan las burbujas financieras.

Jennifer Ouellette | Quanta Magazine


Las redes crecen a medida que los nodos individuales se conectan entre sí. Al modificar las reglas que rigen cuando los nodos se conectan, los investigadores pueden configurar las propiedades de la red.
Paolo Čerić / PATAKK


La semana pasada, United Airlines mantuvo en tierra cerca de 5.000 vuelos cuando su sistema informático se cayó. El culpable: un enrutador de red defectuoso. Más tarde, la misma mañana, otro fallo de la computadora interrumpió la negociación en la Bolsa de Nueva York durante más de tres horas.

Algunos vieron la mano siniestra de un hacker en estas interrupciones, pero son mucho más probables ser una coincidencia, una característica intrínseca del sistema algo que un insecto. Las redes bajan todo el tiempo, consecuencia de niveles de interconexión sin precedentes. Las interrupciones pueden ocurrir incluso en las redes más robustas, ya sean redes eléctricas, mercados financieros globales o su red social favorita. Como señaló el ex reportero del Atlantic, Alexis Madrigal, cuando un error informático cerró la bolsa de valores Nasdaq en 2013, "Cuando las cosas funcionan de nuevas maneras, se rompen de nuevas maneras".

Una nueva comprensión de estos sistemas - la forma en que crecen, y cómo se rompen - ha surgido de la física del café.

Los investigadores suelen pensar en la conectividad de red como sucediendo de una manera lenta y continua, similar a la forma en que el agua se mueve a través de granos de café recién molido, saturando lentamente todos los gránulos para convertirse en café en el contenedor de abajo. Sin embargo, en los últimos años, los investigadores han descubierto que en casos especiales, la conectividad podría surgir con una explosión, no un gemido, a través de un fenómeno que han denominado "percolación explosiva".







Clusters cultivados por percolación explosiva

Esta nueva comprensión de cómo surge la über-conectividad, que fue descrita a principios de este mes en la revista Nature Physics, es el primer paso hacia la identificación de señales de advertencia que pueden ocurrir cuando tales sistemas fallan -por ejemplo, cuando las redes eléctricas comienzan a fallar o cuando una enfermedad infecciosa comienza a convertirse en una pandemia mundial. La percolación explosiva puede ayudar a crear estrategias eficaces de intervención para controlar ese comportamiento y, quizás, evitar consecuencias catastróficas.

Un giro explosivo

Los modelos matemáticos tradicionales de percolación, que datan de 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 por el suelo", dijo Robert Ziff, físico de la Universidad de Michigan, que ha estado estudiando transiciones de fase durante los últimos 30 años. "Es una formación de conectividad de largo alcance en el sistema".

La formación de conectividad puede entenderse como una transición de fase, el proceso por el cual el agua se congela en hielo o se separa en vapor.

Las transiciones de fase son omnipresentes por naturaleza, y también proporcionan un modelo práctico de cómo los nodos individuales en una red aleatoria se unen gradualmente, uno por uno, a través de conexiones de corto alcance a lo largo del tiempo. Cuando el número de conexiones alcanza un umbral crítico, un cambio de fase hace que el mayor clúster de nodos crezca rápidamente y resultados de über-conectividad. (Visto de esta manera, el proceso de percolación que da lugar a su taza de mañana de Joe es un ejemplo de una transición de fase.La agua caliente pasa a través de frijoles tostados y cambia a un nuevo estado - café.)

Raissa D'Souza, física de la Universidad de California, Davis, 
está explorando cómo las intervenciones a pequeña escala
pueden alterar una red grande y compleja

.

La percolación explosiva funciona un poco diferente. La noción surgió durante un taller en 2000 en el Instituto Fields para la Investigación en Ciencias Matemáticas en Toronto. Dimitris Achlioptas, científico de computación de la Universidad de California en Santa Cruz, propuso un posible medio para retrasar la transición de fase a una red densamente conectada, fusionando la noción tradicional de percolación con una estrategia de optimización conocida como el poder de dos opciones. En lugar de dejar que dos nodos aleatorios se conecten (o no), considere dos pares de nodos aleatorios y decida qué par prefiere conectar. Su elección se basa en criterios predeterminados; por ejemplo, puede seleccionar el par que tenga menos conexiones preexistentes con otros nodos.

Debido a que un sistema aleatorio normalmente favorecería a los nodos con las conexiones más preexistentes, esta elección forzada introduce un sesgo en la red, una intervención que altera su comportamiento típico. En 2009, Achlioptas, Raissa D'Souza, físico de la Universidad de California, Davis, y Joel Spencer, matemático del Instituto Courant de Ciencias Matemáticas de la Universidad de Nueva York, encontraron que modificar el modelo de percolación tradicional de esta manera cambia dramáticamente la naturaleza de la transición de fase resultante. En lugar de surgir de una marcha lenta y continua hacia una conectividad cada vez mayor, las conexiones emergen globalmente de una vez por todas en todo el sistema en una especie de explosión, de ahí el apodo de "percolación explosiva".

El concepto ha explotado por derecho propio, generando innumerables documentos en los últimos seis años. Muchos de los trabajos discuten si este nuevo modelo constituye una transición de fase verdaderamente discontinua. De hecho, en 2011 los investigadores mostraron que para el modelo particular analizado en el estudio original de 2009, las transiciones explosivas sólo ocurren si la red es finita. Mientras que las redes como Internet tienen como máximo alrededor de mil millones de nodos, las transiciones de fase se asocian más comúnmente con los materiales, que son redes intrincadas de tantas moléculas (aproximadamente 1023 o más) que los sistemas son efectivamente infinitos. Una vez extendidas a un sistema verdaderamente infinito, las percolaciones explosivas parecen perder parte de su boom.

Sin embargo, D'Souza y sus cohortes tampoco han estado ociosos. Han descubierto muchos otros modelos de percolación que producen transiciones realmente abruptas. Estos nuevos modelos comparten una característica clave, según D'Souza. En la percolación tradicional, los nodos y pares de nodos se eligen al azar para formar conexiones, pero la probabilidad de que dos grupos se fusionen es proporcional a su tamaño. Una vez que un gran grupo se ha formado, domina el sistema, absorbiendo cualquier racimo más pequeño que podría fusionarse y crecer.

Sin embargo, en los modelos explosivos, la red crece, pero el crecimiento del gran grupo se suprime. Esto permite que muchos clústeres grandes pero desconectados crezcan, hasta que el sistema alcance el umbral crítico en el que agregar sólo uno o dos enlaces adicionales desencadena un cambio instantáneo a la über-conectividad. Todos los grandes clusters se combinan a la vez en una sola fusión violenta.

Un nuevo paradigma para el control

D'Souza quiere aprender a controlar mejor las redes complejas. La conectividad es una espada de doble filo, según ella. "Para sistemas operativos normales (como Internet, las redes aéreas o la bolsa de valores), queremos que estén fuertemente conectados", dijo. "Pero cuando pensamos en la propagación de epidemias, queremos reducir el alcance de la conectividad". Incluso cuando la conectividad es deseable, a veces puede ser contraproducente, causando 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.

La percolación explosiva es un primer paso en el pensamiento sobre el control, según D'Souza, ya que proporciona un medio de manipular el inicio de la conectividad de largo alcance a través de interacciones a pequeña escala. Una serie de intervenciones a pequeña escala puede tener consecuencias dramáticas - para bien o para mal.

Los profesionales de las relaciones públicas a menudo se preguntan cómo el trabajo de D'Souza podría ayudar a sus productos ir viral. Ella responde típicamente señalando que sus modelos suprimen realmente comportamiento viral, por lo menos en el corto plazo. "¿Quieres ganar todas las ganancias tan rápido como puedas, o quieres suprimir el crecimiento, así que cuando sucede, más gente aprende de inmediato?", Dijo. Lo mismo ocurre con las campañas políticas, según Ziff. Siguiendo este modelo, pasarán gran parte de su tiempo a principios de la campaña en los esfuerzos locales de base, creando grupos localizados de conexiones y suprimiendo la aparición de conexiones de largo alcance hasta que la campaña esté lista para ir nacional con un gran chapoteo mediático.

En otros sistemas, como los mercados financieros o las redes de energía eléctrica, cuando ocurre un colapso, es probable que sea catastrófico, y este enfoque de mosaico podría ser utilizado para invertir el proceso, rompiendo el sistema conectado en una colección de agrupamientos disjuntos, o "islas", para evitar catastróficas fallas en cascada. Idealmente, uno esperaría encontrar un "punto dulce" para el nivel óptimo de intervención.


En las redes eléctricas, las empresas de servicios públicos pierden dinero cada vez que una línea baja, por lo que idealmente uno debe tratar de evitar cualquier tiempo de inactividad. Sin embargo, actuar para evitar cualquier interrupción en absoluto puede conducir inadvertidamente a interrupciones muy grandes que son mucho más costosas. Por lo tanto, el fomento de pequeños "fallos" en cascada puede disipar los desequilibrios energéticos que de otro modo habrían causado fracasos masivos más adelante, una estrategia potencialmente inteligente a pesar de que come en los márgenes de beneficio. "Si suelen desencadenar pequeñas cascadas, nunca se obtienen eventos realmente masivos, pero sacrifican todo ese beneficio a corto plazo", explicó D'Souza. "Si se evitan las cascadas a toda costa, se puede obtener una gran ganancia, pero eventualmente se producirá una cascada, y será tan masiva que [podría] borrar todo su beneficio".

El siguiente paso es identificar los signos que pueden indicar cuando un sistema está a punto de ser crítico. Los investigadores entienden las transiciones de fase como las que suceden cuando el agua se convierte en hielo y pueden identificar señales de un cambio inminente. Lo mismo no puede decirse de la percolación explosiva. "Una vez que tengamos una mejor comprensión, podremos ver cómo nuestras intervenciones de control están impactando el sistema", dijo D'Souza. "Vamos a tener estos datos que 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".

Las transiciones de fase han fascinado físicos y matemáticos por décadas, así que ¿por qué se ha encontrado este comportamiento explosivo sólo ahora? D'Souza piensa que es porque el descubrimiento requirió la fusión de ideas de varios campos, sobre todo la idea de Achlioptas de mezclar algoritmos y física estadística, creando así un emocionante nuevo fenómeno de modelado. "Realmente es un nuevo paradigma de percolación", dijo Ziff.

miércoles, 20 de septiembre de 2017

Extremistas de derecha dominan el Twitter alemán

La AfD de la derechista populista domina el Twitter alemán, según un nuevo estudio


Partido nacionalista mantiene una influencia desmesurada en las redes sociales cuando la elección se acerca

Financial Times



La investigación publicada hoy por un grupo en la universidad de Oxford demuestra que la alternativa populista de la derecha Alternative für Deutschland (AfD) conduce más tráfico de Twitter que cualquier partido alemán importante, y más uniforme que la discusión no partidista de las próximas elecciones generales sí mismo.

El estudio realizado por el Oxford Computational Propaganda encontró que, de casi 1m tweets recolectados entre el 1 y el 10 de septiembre, las hashtags asociadas específicamente con la AfD aparecieron en más del 30 por ciento.

El AfD, que espera ganar sus primeros escaños en el parlamento alemán el domingo, es "muy destacado en la esfera alemana de Twitter", concluye el estudio. La investigadora principal Lisa-Maria Neudert dijo al FT que la AfD "domina absolutamente" el tráfico político alemán de Twitter.

AfD domina el tráfico del Twitter político alemán

Miles de tweets por categoría de hashtags usados, 1-10 de Septiembre de 2017


Neudert dijo: "AfD es muy ruidoso en los medios sociales. Tienen un gran seguimiento y una buena estrategia de comunicación, una estrategia de medios sociales primero ". El estudio no distingue entre el tráfico de Twitter que apoya a la AfD y que se opone a ella.

El estudio también encontró que la proporción total de tráfico generada por cuentas altamente automatizadas, conocidas como bots, era "no sustancial", aunque el nivel de automatización era mayor para el tráfico usando hashtags relacionados con AfD.

La AfD es el partido populista derechista más exitoso en Alemania desde la segunda guerra mundial. Su objetivo declarado es "la autopreservación no la autodestrucción de nuestro estado y nuestro pueblo" y sus políticas incluyen el "cierre de todas las fronteras alemanas". Se espera que el partido gane 50 o más escaños en las elecciones del domingo.

La publicación del estudio llega después de una semana en la que las empresas de medios sociales dominantes se enfrentan a un escrutinio renovado sobre su papel, en gran medida opaco, en la formación del discurso político. Facebook entregó información a la investigación del abogado especial Robert Mueller sobre la interferencia rusa en las elecciones de 2016 en Estados Unidos después de revelar que los usuarios vinculados a Rusia habían comprado por lo menos $ 100,000 de publicidad en el sitio.

Los análisis originales de FT de los datos de Twitter y Facebook muestran cómo la posición de los medios de comunicación social de la AfD tiene el potencial de proporcionar el punto de apoyo para un cambio en el discurso político alemán hacia la extrema derecha y que tal cambio ya esté en marcha.




El mapeo de las relaciones de Twitter entre más de 700 candidatos del Bundestag identificados como usuarios de la plataforma de medios sociales por el grupo de campaña de transparencia Abgeordnetenwatch.de muestra hasta qué punto la AfD es distinta de la corriente política. Los candidatos a los partidos principales tienen más probabilidades de seguirse unos a otros, mientras que pocos candidatos al AfD siguen a los de otros partidos y viceversa.

Ms Neudert, el investigador de Oxford, puso el número de usuarios de Twitter en Alemania en 1m - una fracción de los más de 30m usuarios alemanes de Facebook. Sin embargo, señaló, Twitter es considerado importante por "líderes de opinión e influenciadores" y sirve como un canal para la comunicación abierta entre políticos y periodistas.

Con más de 350.000 gustos - más de dos de los partidos más grandes, CDU y SPD, juntos - el AfD tiene una presencia formidable Facebook similar. Mientras que la participación de los usuarios con el partido en Facebook creció constantemente a lo largo de la crisis de refugiados del verano de 2015, su mayor impulso llegó después de una protesta por una serie de agresiones sexuales en Colonia y otras ciudades alemanas en la víspera de Año Nuevo 2015. Los mensajes de la AfD se triplicaron a más de 380.000 en un mes. Muchos de los perpetradores de los asaltos eran solicitantes de asilo o inmigrantes ilegales, y el episodio ayudó a empujar el nivel de AfD de compromiso de Facebook a nuevas alturas.

El momento definitorio en el cambio de las páginas de Facebook de AfD

Compromiso del usuario por posteo realizado luego del Año Nuevo



No fue sólo el nivel de compromiso con el partido que se elevó tras los ataques de fin de año. El tono de la página Facebook de AfD cambió: las palabras y frases que, en Alemania, están más estrechamente asociadas con la era nazi comenzaron a aparecer con más frecuencia en los comentarios que los usuarios estaban publicando en la página.

Basado en investigaciones académicas y entrevistas con dos investigadores de lengua política alemanes, el FT compiló una lista de 25 términos asociados con la era nazi y / u otras ideologías nacionalistas alemanas. A continuación, utilizamos el software original para determinar la frecuencia con que aparecen estos términos en los comentarios de los usuarios en la página de AfD en Facebook.

En mayo de 2015, se utilizó un promedio de 2,6 de los términos en todos los comentarios por puesto de AfD. Un año más tarde, esta cifra había aumentado a 29,6 - un aumento del 1,100 por ciento. Entre los términos más frecuentemente utilizados se encuentran "Volksverräter" (traidor al pueblo) y "Altparteien" (partidos de establecimiento), ambos con fuertes connotaciones nazis.

Y también cambiaron las palabras que usan en su página de Facebook

Frecuencia de vocabulario del Tercer Reich en el comentario de cada post


Términos tales como "nacional" y "patriota" también han visto aumentos en la frecuencia. Aunque son ostensiblemente incontrovertibles, estos son algunos de los términos con una historia más problemática en Alemania.

El número de usuarios distintos de Facebook para utilizar dichos términos en los comentarios también aumentó, y aunque el uso de este lenguaje ha caído desde su pico a principios de 2016, sigue siendo significativamente mayor que para gran parte de la existencia de la página.

lunes, 18 de septiembre de 2017

Software: Visone

Visone (visual social network)

par Laurent Beauguitte | groupe fmr

Visone es un software desarrollado desde 2001 en la Universidad de Konstanz y el Instituto de Tecnología de Karlsruhe. La versión probada aquí es el 2.6.5 (Java jar, 18 MB) del 5 de marzo de 2012. Gratuito, el software es multiplataforma (Linux, OSX y Windows) pero no es de código abierto. La instalación supone que tiene instalado un entorno Java en su computadora (consulte el siguiente tutorial.).

La GUI se ve muy similar a otro software (Tulip, Gephi, etc), pero tiene la ventaja de ofrecer todas las opciones posibles en la misma página.


Interfaz de software de Visone

Los algoritmos de visualización propuestos son pocos y a menudo clásicos (circle, random o MDS en particular). Las herramientas de análisis son pocas, pero variadas y se basan tanto en aportes desde el lado de los físicos como en los sociólogos (especialmente para agrupación). Permiten estudiar grafos booleanos y valuados. Los resultados, así como los grafos abiertos (o directamente dibujados por el lápiz) se almacenan en la carpeta denominada gestor de atributos. Es posible obtener los resultados y aplicar un algoritmo de visualización simultáneamente a todos los grafos abiertos.



El formato de los archivos es, para los grafos, son archivos .graphml y los atributos de vértices y / o enlaces, archivos .csv. Es posible importar y exportar en los formatos más comunes (Ucinet, Pajek o .gml) y la exportación de las visualizaciones es posible en formato de imagen como en formato vectorial.

Curiosamente, el software se puede conectar a R (ver aquí), que permite lanzar modelos de Siena (ver la síntesis fmr n ° 13 dedicada al modelado estadístico de redes - en francés). También hace posible crear animaciones de una manera relativamente simple: simplemente crea un gestor de colecciones de red y selecciona los grafos que se van a insertar en la animación y luego haz clic en el carrete para generarlo.

Por otro lado, no encontré ninguna indicación acerca de los tamaños límite de los grafos soportados por el software (pero aún no lo he leído todo).


viernes, 15 de septiembre de 2017

Detección de comunidades con Pajek (1)

Detección de comunidades con Pajek 3.6

por Marion Maisonobe | groupe fmr


La nueva versión de Pajek ofrece buenas sorpresas para los exploradores de grafos complejos.

Las nuevas características discutidas aquí se agregaron al software entre mayo de 2012 y septiembre de 2012.

Se han implementado dos algoritmos de detección de comunidades:

Network/Create Partition/Communities


-Louvain method



El primer algoritmo se basa en el método de Louvain [1]. Este método se adapta bien a los grafos ponderados, incluso si están firmados (signed graphs). Al igual que con muchos algoritmos de agrupación, la calidad de la partición se optimiza mediante la maximización de la función de modularidad [2]. El índice de modularidad mide la diferencia entre la densidad de un grafo (o subgrafo) dado y la densidad de un grafo aleatorio que tiene las mismas características (número y peso de los enlaces).


Principio

Maximizar la función de modularidad para particionar un grafo es como asegurarse de que el número y el peso de los enlaces sean mayores dentro de las particiones que entre las particiones. Para expresarlo de manera diferente, la densidad intra-comunitaria debe exceder la densidad intercomunitaria.

El método de Louvain es "de abajo hacia arriba" y multi-nivel. Al inicio del algoritmo, todos los vértices pertenecen a una partición diferente. Se agrupan, por iteración, en particiones de modularidad óptima. En la primera situación óptima, el proceso continúa en el nivel superior: cada partición se trata como un vértice y así sucesivamente. La operación continúa hasta que no hay más ganancia de modularidad posible.

Ventaja

Este enfoque evita la falta de modularidad conocida como el "límite de resolución" [3]. Si asociar una partición del primer nivel con otro resultaría en una pérdida de modularidad, esta asociación no se realizaría por el método de Louvain. Como resultado, no es probable que estructuras pequeñas con buena modularidad estén incrustadas en estructuras mayores y menos significativas. Esto es lo que sucedería con un algoritmo "top-down" aplicado a un grafo grande.

Desventaja

El defecto conocido del método proviene de la sensibilidad del resultado al orden de tratamiento de los vértices. El orden en que los vértices son considerados tiene una influencia sobre la partición. Por lo tanto, puede ser útil realizar permutaciones para asegurar la robustez del resultado [4]. La otra forma es imponer un orden que tenga en cuenta las características de la red [5].

Además del algoritmo convencional de Louvain, Pajek ofrece una variante (con el refinamiento de niveles múltiples) que tiende a dar mejores resultados para grandes grafos. [6] El método de Louvain también está disponible en los software Gephi y NetworkX, así como en la biblioteca de software de I igraph, el algoritmo es más rápido en Pajek que en Gephi.

-VOS Clustering


El método de detección de la comunidad VOS optimiza otra función de calidad que la función de modularidad: la denominada función de agrupación VOS [7]. Esta es una variante ponderada de la modularidad que se ha pensado para el procesamiento de datos bibliométricos. Esta técnica da menos peso que un método clásico con un grado muy alto. A diferencia del método de Louvain, depende de un algoritmo "de arriba hacia abajo". Por esta razón, la única manera de escapar al problema de limitar la resolución es variar el parámetro de resolución.

Este método es adecuado para grafos para los cuales el valor de los enlaces explica la importancia de la similitud entre los vértices. Sus diseñadores querían ser asociados con el algoritmo de agrupación un algoritmo de visualización usando el mismo principio matemático. Este enfoque unificado hace posible evitar inconsistencias entre el resultado del proceso de agrupación y la representación gráfica de este resultado.

Naturalmente, Pajek también ofrece el algoritmo de visualización VOS. Funciona sobre el principio de la optimización de la función de calidad denominada mapeo VOS. Dada la proximidad de los dos métodos de detección, no es ciertamente impensable utilizar la asignación VOS para representar un grafo particionado de acuerdo con el método de Louvain.

Ir más lejos

Se puede encontrar una comparación de los dos métodos de detección en:
http://mrvar.fdv.uni-lj.si/pajek/community/LouvainVOS.htm

Los detalles sobre el uso de estos métodos con Pajek también se pueden encontrar en el sitio: parametrización, evaluación de la calidad de la partición, representación gráfica del resultado.

Desde la interfaz gráfica de Pajek, un acceso directo al software VOSviewer ofrece la posibilidad de obtener rápidamente una representación elegante de la partición.

A continuación se muestra un ejemplo de los datos de colaboración científica holandesa (Fuente: Web of Science 2006-2008):




Referencias


  1. V. Blondel, J.-L. Guillaume, R. Lambiotte, et E. Lefebvre, « Fast unfolding of communities in large networks », Journal of Statistical Mechanics, vol. 2008, no 10, sept. 2008.
  2. Hay muchos otros métodos para detectar comunidades. Para obtener una visión general de las: S. Fortunato, « Community detections in graphs », Physics and Society, vol. 2010, no 486, p. 75-174.
  3. S. Fortunato et M. Barthélemy, « Resolution limit in community detection », Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no 1, p. 36-41, janv. 2007.
  4. V. Blondel, G. Krings, et I. Thomas, « Régions et frontières de téléphonie mobile en Belgique et dans l’aire métropolitaine bruxelloise », Brussels studies, no 42, oct. 2010.
  5. P. De Meo, E. Ferrara, G. Fiumara, et A. Provetti, « Generalized Louvain method for community detection in large networks », under review, 2011. URL: http://www.emilio.ferrara.name/wp-content/uploads/2011/07/isda2011-k-path.pdf}
  6. R. Rotta et A. Noack, « Multilevel local search algorithms for modularity clustering », Journal of Experimental Algorithmics, vol. 16, no 2.3, 2011.
  7. L. Waltman, N. J. van Eck, et E. C. M. Noyons, « A unified approach to mapping and clustering of bibliometric networks », Journal of Infometrics, vol. 4, no 4, p. 629-635, oct. 2010.


martes, 12 de septiembre de 2017

Algoritmos de agrupamientos guiados por centralidad

"Sigan al líder": Un agrupamiento guiado por centralidad y su aplicación al Análisis de Redes Sociales

Qin Wu, Xingqin Qi, Eddie Fuller, y Cun-Quan Zhang


The Scientific World Journal
Resumen
Dentro de la teoría de grafos y del análisis de redes, la centralidad de un vértice mide la importancia relativa de un vértice dentro de un grafo. La centralidad juega un papel clave en el análisis de redes y ha sido ampliamente estudiada utilizando diferentes métodos. Inspirado en la idea de la centralidad de los vértices, se propone una novedosa agrupación guiada por la centralidad (CGC). Diferente de los métodos clásicos de agrupación que suelen elegir el centro inicial de un grupo de forma aleatoria, el algoritmo de agrupación CGC comienza a partir de un "LEADER" -un vértice con el puntaje de centralidad más alto- y se agrega un nuevo "miembro" al mismo grupo que el "LEADER"cuando se satisface algún criterio. El algoritmo CGC también admite la superposición de miembros. Se presentan los experimentos en tres conjuntos de datos de redes sociales de referencia y los resultados indican que el algoritmo CGC propuesto funciona bien en la agrupación de redes sociales.


1. Introducción

Clustering es un proceso de partición de un conjunto de datos en subconjuntos significativos para que todos los datos en el mismo grupo son similares y los datos en diferentes grupos son disimilares en algún sentido. Es un método de exploración de datos y una forma de buscar patrones o estructura en los datos que son de interés. El clustering tiene amplias aplicaciones en ciencias sociales, biología, química y ciencias de la información. Una revisión general del análisis de conglomerados se puede encontrar en muchas referencias como [1 - 4].

Los métodos de agrupación comúnmente utilizados son agrupación particional y agrupación jerárquica. Los algoritmos partiales normalmente determinan todos los clústeres a la vez. El algoritmo de clustering de K-means [5] es un agrupamiento particional típico. Dado el número de racimos (digamos k), el procedimiento de K-significa la agrupación es como sigue. (i) Generar aleatoriamente k puntos como centros de agrupación y asignar cada punto al centro de agrupación más cercano. (ii) Recalificar los nuevos centros de agrupación. (iii) Repita los dos pasos anteriores hasta que se cumpla algún criterio de convergencia. Las principales ventajas del algoritmo de K-means son su simplicidad y velocidad que le permite funcionar en grandes conjuntos de datos. Sin embargo, no produce el mismo resultado con cada ejecución, ya que los clústeres resultantes dependen de las asignaciones al azar iniciales. Y el número de clústeres tiene que ser predefinido.

La agrupación jerárquica es aglomerante o divisiva. Los algoritmos aglomerativos comienzan con cada elemento como un clúster separado y dos clusters separados por la distancia más corta se combinan sucesivamente. La mayoría de los algoritmos de agrupación jerárquica son aglomerados, como SLINK [6] para cantar enlace y CLINK [7] para el enlace completo. El divisivo comienza con un gran grupo y las divisiones se realizan recursivamente a medida que se desplaza por la jerarquía. El agrupamiento jerárquico crea un árbol jerárquico de clústeres, que se denomina dendrograma. La forma en que los elementos se agrupan se muestra claramente en el dendrograma.

En los últimos años, el análisis de redes sociales ha ganado mucha atención. El análisis de redes sociales es el estudio de las relaciones sociales en términos de redes. Una red social suele ser modelada como un grafo dirigido o un grafo no dirigido. El conjunto de nodos del grafo representa a miembros individuales. El conjunto de aristas en el grafo representa la relación entre los individuos, como la amistad, la coautoría, etc. Un problema fundamental relacionado con las redes sociales es el descubrimiento de clusters o comunidades. Porter et al. [8] resumió diferentes métodos de agrupación para la agrupación de redes sociales. Wu y Huberman [9] propusieron encontrar comunidades basadas en nociones de caídas de voltaje a través de redes. Girvan y Newman [10] propusieron descubrir la estructura de la comunidad basada en la interrelación de intermediario. Newman [11] propuso encontrar la estructura de la comunidad basada en los vectores propios de las matrices. Clauset et al. [12] propuso un método basado en la modularidad para encontrar la estructura de la comunidad en redes muy grandes.

En este trabajo, un nuevo algoritmo de agrupación jerárquica se propone para la agrupación de redes sociales. Los métodos clásicos de agrupamiento, como K-means, usualmente eligen centros de agrupación de forma aleatoria, y los algoritmos de agrupación jerárquica usualmente comienzan a partir de dos elementos con la distancia más corta. A diferencia de estos métodos, este trabajo elige el vértice con puntaje de centralidad más alto como punto de partida. Si se hace algún análisis en conjuntos de datos de redes sociales, uno puede notar que en cada comunidad, normalmente hay algún miembro (o líder) que desempeña un papel clave en esa comunidad. De hecho, la centralidad es un concepto importante [13] dentro del análisis de redes sociales. Los puntajes de alta centralidad identifican a los miembros con mayor importancia estructural en una red y se espera que estos miembros desempeñen papeles clave en la red. Basándose en esta observación, este trabajo propone comenzar a agrupar desde el miembro con mayor puntuación de centralidad. Es decir, un grupo se forma a partir de su "líder", y un nuevo "miembro" se agrega a un grupo existente basado en su relación total con el grupo. El procedimiento principal es el siguiente. Elija el vértice con el puntaje de centralidad más alto que no esté incluido en ningún grupo existente y llame a este vértice como "LEADER". Se crea un nuevo grupo con este "LEADER". Agregue repetidamente un vértice a un grupo existente si el siguiente criterio es satisfecho: la densidad del grupo recién extendido está por encima de un umbral dado.

El documento está organizado de la siguiente manera. En la Sección 4 se describen los diferentes resultados de las pruebas del nuevo algoritmo en algunos conjuntos de datos de referencia de la red social comparados con la verdad del terreno y algunos métodos tradicionales. Las conclusiones se hacen en la Sección 5.


2. Medidas de centralidad

La centralidad es uno de los conceptos más ampliamente estudiados en el análisis de redes sociales. Dentro de la teoría de grafos y del análisis de redes, la centralidad de un vértice mide la importancia relativa de un vértice dentro del grafo. Por ejemplo, cuán importante es una persona dentro de una red social o qué tan bien se utiliza una carretera dentro de una red urbana. Durante los últimos años, se han propuesto varias medidas de la centralidad de un vértice. La medición de la centralidad, como la centralidad de los grados, la interconexión y la centralidad de los vectores propios, están entre las más populares.

La centralidad de grados es la medida de centralidad más simple. Dada un grafo G, denote el conjunto de vértices de G como V (G), y entonces el grado centralidad para cualquier v ∈ V (G) se define como

   (1)

donde d (v) es el grado de y | V (G) | es el número de vértices en G.

La centralidad de grados considera solamente la topología local de la red. Puede interpretarse como una medida de influencia inmediata, en oposición al efecto global en la red [14].

La centralidad intermedia para cualquier v ∈ V (G) se define como


(2)

donde s, v, tV (G), σ st es el número de trayectos más cortos de s a t, y σ st (v) es el número de trayectos más cortos de s a t que pasan a través del vértice v.

La centralidad de la intermediación es una de las medidas de centralidad más populares que consideran la estructura global de la red. Caracteriza cuán influyente es un vértice en la comunicación entre pares de vértices [15].

El puntaje de centralidad de vectores propios del i-ésimo vértice de la red se define como la i-ésima componente del vector propio correspondiente al valor propio más alto de la siguiente ecuación característica:

Ax = λx
(3)

donde A es la matriz de adyacencia de la red, λ es el autovalor más grande de A, y x es el autovector correspondiente. Simula un mecanismo en el que cada vértice afecta a todos sus vecinos simultáneamente [16].

La centralidad del vector propio es una especie de centralidad de grado extendido que es proporcional a la suma de las centralidades de los vecinos del vértice. Un vértice tiene un gran valor de puntuación de centralidad de vectores propios bien si está conectado a muchos otros vértices o si está conectado a otros que tienen una elevada centralidad de vectores propios [17].

Debido a que las diferentes medidas de centralidad se basan en diferentes aspectos de una red, las puntuaciones de centralidad final y la clasificación de los nodos en la red pueden ser diferentes. La diferencia se discutirá en la Sección 4.

3. Agrupamiento guiado por la centralidad

En esta sección, se introducen algunas notación y terminología y se presenta el algoritmo de agrupación guiada por centralidad (CGC).

Dado un conjunto de datos de entrada, el conjunto de datos es modelado como un grafo ponderado G = (V, E, w). V es el conjunto de vértices. Cada vértice en V representa un elemento en el conjunto de datos. | V (G) | representa el número de vértices en G (o elementos en el conjunto de datos). E es el conjunto de enlaces. Cada enlace representa una relación entre un par de elementos. w es la función de peso de enlace. w (u, v) y w (e) denotan el peso del enlace e entre dos vértices uyv. Si no hay enlace entre dos vértices uyv, entonces w (u, v) = 0. Si el grafo es un grafo no ponderado, entonces

w(uv)={1,0,if  uvE(G),if  uvE(G).

Sea C un subgrafo de G, la densidad del subgrafo C se define como

density(C)=2eE(C)w(e)  |V(C)|(|V(C)|1),if  |V(C)|>1.
(5)
La densidad del subgrafo C podría ser considerada como la semejanza del intracluster. Un buen agrupamiento debe tener una alta similitud intracluster y una baja semejanza intercluster. Si todos los nodos en C pertenecen al mismo grupo, entonces la densidad (C) debe ser grande.
Como se discutió en la Sección 2, la centralidad de un vértice mide la importancia relativa del vértice dentro de la red. Uno podría esperar que después de la agrupación, cada grupo tiene un centro y el centro tiene una puntuación relativa alta centralidad. Por otro lado, si un algoritmo de agrupamiento se inicia desde el vértice (llamado "LEADER") con una alta puntuación de centralidad, se esperaría que los vértices con conexión estrecha con el LEADER se agruparan. El resultado del agrupamiento tendrá alta intrasimilaridad y baja intersimilaridad. Esta es la motivación del algoritmo CGC. Denote la puntuación de centralidad del vértice v en el grafo G como puntuación (v). Para cualquier conjunto S, denote el número de elementos en S como | S |.

Para cualquier vértice vV (C), la contribución de v a C se define como

contribution(v,C)=uV(C)w(uv)  |V(C)|.
(6)

Un vértice v ∉ V (C) se llama vecino de C si hay un vértice uC tal que uv ∈ E (G). El vértice v se llama vecino candidato de C si v satisface las tres condiciones siguientes:

(a) v es un vecino del subgrafo C;
(b) existe un vértice u ∈ V (C), tal que

  • w(u,v)αmax{w(e)eE(G)},if  |V(C)|=1,contribution(v,C)>βdensity(C),if  |V(C)|>1;
    (7)
  • (c)
    score(v) < max⁡{score(u) | u ∈ C}.
El conjunto de todos los vecinos candidatos del subgrafo C se denota como N(C).
La condición (a) dice que un vértice debe ser un vecino del subgrafo C para ser considerado como agrupado en el grupo actual C. La condición (b) es controlar la densidad del subgrafo C de modo que la densidad no disminuya demasiado después de que el vecino candidato se agrega al subgrafo C. La condición (c) dice que solo se consideran aquellos vértices con puntaje de centralidad inferior al puntaje de centralidad de algún vértice en C. Es decir, si un vértice v ∈ N (C) tiene mayor puntuación de centralidad que cualquier vértice en C, entonces el vértice v debe haber sido agrupado en otro grupo, por lo que v no se agrupará en el grupo C. α y β son utilizado para controlar el agrupamiento de modo que la densidad del nuevo subgrafo no disminuirá demasiado después de que un vecino candidato sea agregado al subgrafo C. En otro papel [18], probamos que si α = 0.8 y β = 1 - (1 / (2 * (| V (C) | +1))), entonces la densidad del nuevo subgrafo con un conjunto de vecinos candidatos añadido al subgrafo C no disminuirá más de 1/3.
La estructura general del algoritmo CGC se muestra en el Algoritmo 1. Los tres pasos principales son AGRUPACIÓN, FUSIÓN y CONTRACCIÓN.


Algoritmo CGC

Los detalles del paso GROUPING se muestran en el Algoritmo 2. El algoritmo GROUPING crea un nuevo grupo desde el vértice con el puntaje de centralidad más alto que todavía no se ha agrupado en ningún grupo. Y este vértice se llama centro (o líder) del nuevo grupo. Denotan este vértice como el centro del grupo C i actual. Entonces el siguiente vértice se elige del vecino candidato conjunto N(C i) con la mayor contribución a C i.


Algoritmo GROUPING 

En el algoritmo CGC, cada vértice se permite pertenecer a más de un grupo. Así que después del paso GROUPING, los diferentes grupos pueden tener algunos elementos superpuestos. Si el número de elementos superpuestos en dos grupos excede algún umbral, es mejor combinar todos los vértices de los dos grupos en un nuevo grupo más grande. Se aplica el siguiente criterio para determinar si se deben fusionar dos grupos. Dado que existen dos grupos, digamos C i y C j, si C i y C j satisfacen el siguiente criterio, entonces C i y C j se combinan en un grupo:

|CiCj|min{|Ci|,|Cj|}12.
(8)

Es decir, si el tamaño de la superposición de dos grupos es mayor que la mitad del tamaño del más pequeño de los dos grupos, los dos grupos se combinan en un grupo. El algoritmo MERGING (ver Algoritmo 3) describe los detalles sobre cómo combinar dos grupos.

Algoritmo MERGING

Después del paso de MERGING, cada grupo C i  se contrae en un nuevo vértice v i. Si hay un enlace entre dos grupos C i  y C j, entonces habrá un enlace v i v j  en el grafo contraído. El peso del enlace, w(v iv j), se calcula de la siguiente manera:

w(vi,vj)=eE(Ci,Cj)w(e)  |V(Ci)||V(Cj)|,
(9)
donde E(C iC j) es el conjunto de enlaces que se cruzan, E(C iC j) = {xy : x ∈ V(C i), y ∈ V(C j), x ≠ y}.

Algoritmo CONTRACTION 

4. Resultados y discusión

Para evaluar la eficacia del algoritmo CGC, tres conjuntos de datos de referencia sobre el análisis de redes sociales se ponen a prueba. Los tres conjuntos de datos de referencia y los resultados del agrupamiento se describen en las secciones 4.1, 4.2 y 4.3. La centralidad de intermediación se utiliza para calcular las puntuaciones de centralidad en el algoritmo CGC. Los resultados del algoritmo CGC se comparan con la verdad del terreno y los resultados del algoritmo Girvan-Newman [10]. El algoritmo Girvan-Newman es uno de los algoritmos más populares para detectar comunidades en sistemas complejos. Las comunidades se detectan calculando las centralidades de interlineado de enlace de todos los enlaces y eliminando el enlace con el valor de intermediación más alto recursivamente.

Para probar si las medidas de centralidad influyen en los resultados, se aplican diferentes medidas de centralidad al algoritmo de CGC de forma independiente y los resultados del agrupamiento se comparan en la Sección 4.4. Todos los tres conjuntos de datos se pueden descargar desde el sitio web de Newman [19].

4.1. Club de Karate de Zachary

El conjunto de datos del club de karate de Zachary es un conjunto de datos típico que se utiliza para probar el algoritmo de agrupación en el análisis de redes sociales. Es una red social de amistades entre 34 miembros de un club de karate en una universidad estadounidense [20]. Zachary registró la interacción del club de karate en la universidad durante tres años. La red social de relaciones en el club de karate de Zachary se muestra en la Figura 1. El nodo 1 representa al instructor del club y el nodo 34 representa al presidente del club. Durante la observación, hubo un incipiente conflicto entre el instructor y el presidente. Y el conflicto posteriormente condujo a una separación formal del club en dos organizaciones: un grupo es los partidarios del instructor y el otro grupo son los partidarios del presidente. Los grupos de verdad del suelo se denotan como puntos rojos y cuadrados azules en la Figura 1. Los puntos rojos denotan los partidarios del instructor y los cuadrados azules denotan a los partidarios del presidente.

Figura 1
La red social del club de karate de Zachary. Los puntos rojos denotan los partidarios del instructor y los cuadrados azules denotan los partidarios del presidente. La curva discontinua es la partición por el algoritmo CGC.

Cuando se aplica el algoritmo Girvan-Newman a este conjunto de datos, el nodo 3 se clasifica erróneamente. La partición por el algoritmo CGC se muestra como la curva discontinua en la Figura 1, que es exactamente la misma que la verdad del terreno. La figura 2 es el dendrograma correspondiente al resultado del algoritmo CGC. Otra observación importante es que cuando se utiliza la centralidad de intermediación, el nodo con las puntuaciones de centralidad de mayor intermediación es el nodo 1 y el segundo más alto es el nodo 34, que son el instructor y el presidente, los verdaderos líderes de los dos grupos.


Figura 2

El dendrograma del conjunto de datos del club de karate por el algoritmo CGC.

4.2. Red social de delfines

El conjunto de datos de redes sociales de delfines es otro conjunto de datos representativo para probar la precisión de los algoritmos de agrupamiento. Es una red social de frecuentes asociaciones entre delfines en una comunidad en Doubtful Sound, Nueva Zelanda [21]. La red social de los delfines se presenta en la Figura 3. Hay 62 vértices y 159 enlaces en la red. Los vértices representan a los delfines nariz de botella, y los enlaces entre los vértices representan asociaciones entre los pares de delfines que ocurren con más frecuencia de lo esperado por el azar. Durante el curso del estudio, los delfines se dividieron en dos grupos después de la partida de un miembro clave (representado como el triángulo amarillo en la Figura 3) de la población.

Figura 3
La red social de los delfines. La curva discontinua indica la división de la red en dos grupos de igual tamaño encontrados por el método estándar de partición espectral, y la curva sólida representa la división encontrada por el método basado en la modularidad por Newman [11].

Los grupos de verdad del suelo están representados por las formas de los vértices de la Figura 3. Los vértices representados como cuadrados están en un grupo y los vértices representados como puntos y triángulo están en el otro grupo. La curva discontinua representa la división de la red en dos grupos de igual tamaño encontrados por el método estándar de partición espectral propuesto por Newman [11]; 11 de los 62 delfines están mal clasificadas. La curva sólida representa la división encontrada por el método basado en la modularidad por Newman [11]; 3 de 62 delfines están mal clasificadas. Cuando se aplica el algoritmo Girvan-Newman a este conjunto de datos, 2 de los 62 delfines se clasifican erróneamente. Cuando el algoritmo CGC se aplica a la red social del delfín, divide a los delfines en dos grupos, que es exactamente igual que la verdad del suelo. El dendrograma correspondiente producido por el algoritmo CGC se muestra en la Figura 4.



Figura 4
El dendrograma del conjunto de datos Dolphin por el algoritmo CGC.

4.3. Red Social de Libros Políticos

El tercer ejemplo es un mapa de redes sociales de libros políticos basado en patrones de compra del vendedor de libros en línea Amazon.com. Este conjunto de datos es proporcionado por Krebs [22]. Y los grupos de diferentes libros se muestran en la Figura 5. Los 105 nodos representan 105 libros sobre la política estadounidense. Cada libro es manualmente etiquetado como liberal, neutral o conservador. De manera correspondiente, los tres tipos de libros se ilustran utilizando tres formas diferentes: triángulos para libros neutros, puntos para libros conservadores y cuadrados para libros liberales, como en la figura 5. Por simplicidad, los 105 libros se denominan 1 a 105 en lugar de libro nombres. Dos libros están vinculados en la red social si fueron frecuentemente cotizados por el mismo cliente. La figura 5 muestra la clasificación de la verdad del suelo para los 105 libros.

Figura 5

La partición verdadera de la tierra de los libros políticos. Triángulos para libros neutrales, puntos para libros conservadores y cuadrados para libros liberales.

Para ver los resultados de agrupamiento basados en la información de compra de libros, el algoritmo Girvan-Newman [10] y el algoritmo CGC se aplican independientemente a la matriz de adyacencia de los libros políticos. Cuando el algoritmo de Girvan-Newman se aplica a la matriz de adyacencia de la red social, 17 libros (2, 3, 6, 8, 19, 29, 30, 47, 49, 52, 53, 59, 70, 77, 104 y 105) están mal clasificadas. El resultado de agrupamiento del algoritmo de Girvan-Newman se muestra en la Figura 6. Cuando se utiliza la centralidad de interconexión y el algoritmo CGC se aplica al mismo conjunto de datos, sólo 16 libros (1, 5, 7, 19, 29, 47, 49, 53 , 59, 65, 66, 68, 69, 77, 78 y 86) se clasifican erróneamente. El resultado de agrupamiento del algoritmo CGC se muestra en la Figura 7.

Figura 6
El resultado de agrupamiento de los libros políticos por el algoritmo de Girvan-Newman. Rojo para libros neutrales, azul para libros conservadores y negro para libros liberales.
Figura 7
El resultado agrupamiento de los libros políticos por el algoritmo CGC. Rojo para libros neutrales, azul para libros conservadores y negro para libros liberales.

4.4. Agrupación con diferentes medidas de centralidad


Como se mencionó en las secciones anteriores, la puntuación de centralidad de un nodo en una red podría ser visto como la importancia de un nodo en la red. Y la importancia de los nodos podría ser ordenada por sus puntuaciones de centralidad de grandes a pequeños. Cuando se aplican diferentes medidas de centralidad al mismo conjunto de datos, el ordenamiento de los nodos puede ser diferente.

El propósito de esta subsección es probar si el nodo de agrupamiento inicial influirá en el resultado de agrupación final y comparará la efectividad de la medida de centralidad diferente cuando se combina con el algoritmo de CGC. En esta subsección, la centralidad de grados, la centralidad de valores propios y la centralidad de interconexión se aplican independientemente al algoritmo CGC. Y los mismos tres conjuntos de datos que en las secciones 4.1, 4.2 y 4.3 se utilizan en los experimentos.

La Tabla 1 enumera el número de nodos mal clasificados cuando se aplican diferentes mediciones de centralidad al algoritmo CGC. A partir de la tabla, se pudo observar que el nodo inicial inicial influye en los resultados finales. Para el conjunto de datos del club de karate de Zachary, las tres medidas de centralidad producen resultados perfectos. La centralidad del grado funciona mejor que la centralidad del valor propio en el conjunto de datos del delfín. Pero en el conjunto de datos del libro político, el grado de centralidad es peor que la centralidad de los valores propios. En general, la medida de centralidad de intermediación funciona mejor con el algoritmo CGC.

Club de Karate DelfinesLibros políticos
Grado0117
Eigenvalue0216
Intermediación0016
Tabla 1
El número de miembros mal clasificados por el algoritmo CGC basado en diferentes medidas de centralidad.

5. Conclusiones

En este trabajo, se discute la importancia de la puntuación de centralidad de vértices en una red y se propone un método de agrupamiento guiado por centralidad. El algoritmo CGC inicia el proceso de agrupación en un vértice con la puntuación de centralidad más alta, que es un líder potencial de una comunidad. El algoritmo CGC se aplica a varios conjuntos de datos de redes sociales de referencia. Los resultados experimentales muestran que el algoritmo CGC funciona bien en la agrupación de redes sociales.

Las mediciones de centralidad pueden influir en los resultados del algoritmo CGC. El criterio de grado sirve como una medida muy local para la centralidad, mientras que la centralidad entre centralidades y la búsqueda de centralidad de valores propios busca "líderes" globales de todas las redes. Los resultados del experimento muestran que la centralidad de intermediación funciona mejor que las otras dos medidas de centralidad para el algoritmo CGC.

Uno puede notar que en la Figura 4, un solo nodo, como los nodos 45, 47, 12 y 60 en el nivel más bajo, se agrupa en dos grupos diferentes. De hecho, es razonable que algún individuo pertenezca a dos grupos diferentes. Digamos, por ejemplo, que algunas personas pueden estar afiliadas a dos o más organizaciones. De hecho, permitir que un objeto se agrupe en dos o más grupos es una de las propiedades del algoritmo CGC, lo que hace que el algoritmo CGC diferente de otros algoritmos de agrupación.
El algoritmo CGC es un algoritmo de agrupamiento jerárquico. Una dirección para la investigación futura sería aplicar la idea guiada por la puntuación de centralidad a otros métodos de agrupamiento como el agrupamiento de K-means. Con suerte, también producirá resultados de agrupación prometedores.

Referencias


  1. Milligan G. Encyclopedia of Statistical Sciences. New York, NY, USA: Wiley; 1998.
  2. Härdle WK, Simar L. Applied Multivariate Statistical Analysis. Berlin, Germany: Springer; 2003.
  3. Hansen P, Jaumard B. Cluster analysis and mathematical programming. Mathematical Programming B. 1997;79(1–3):191–215.
  4. Jain AK. Data clustering: 50 years beyond K-means. Pattern Recognition Letters. 2010;31(8):651–666.
  5. MacQueen J. Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability; 1967; University of California Press; pp. 281–297.
  6. Sibson R. Slink: an optimally efficient algorithm for the single-link cluster method. Computer Journal. 1973;16(1):30–34.
  7. Defays D. An efficient algorithm for a complete link method. Computer Journal. 1977;20(4):364–366.
  8. Porter MA, Onnela J-P, Mucha PJ. Communities in networks. Notices of the American Mathematical Society. 2009;56(9):1082–1097.
  9. Wu F, Huberman BA. Finding communities in linear time: a physics approach. European Physical Journal B. 2004;38(2):331–338.
  10. Girvan M, Newman MEJ. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America. 2002;99(12):7821–7826. [PMC free article] [PubMed]
  11. Newman MEJ. Finding community structure in networks using the eigenvectors of matrices. Physical Review E. 2006;74(3)036104 [PubMed]
  12. Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Physical Review E. 2004;70(6):6 pages.066111 [PubMed]
  13. Wasserman S, Faust K. Social Network Analysis: Methods and Applications. 1st edition. Vol. 8. New York, NY, USA: Cambridge University Press; 1994. (Structural Analysis in the Social Sciences).
  14. Freeman LC. Centrality in social networks conceptual clarification. Social Networks. 1978;1(3):215–239.
  15. Freeman LC. A set of measures of centrality based on betweenness. Sociometry. 1977;40(1):35–41.
  16. Bonacich P. Power and centrality: a family of measures. American Journal of Sociology. 1987;92(5):1170–1182.
  17. Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physical Review E. 2004;69(2)026113 
  18. Ou Y, Zhang C-Q. A new multimembership clustering method. Journal of Industrial and Management Optimization. 2007;3(4):619–624. 
  19. http://www-personal.umich.edu/~mejn/netdata/
  20. Zachary WW. An information flow model for conflict and fission in small groups. Journal of Anthropological Research. 1977;33:452–473.
  21. Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: can geographic isolation explain this unique trait? Behavioral Ecology and Sociobiology. 2003;54(4):396–405.
  22. Krebs V. http://www.orgnet.com/