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 v 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, t ∈ V (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  uv∈E(G),if  uv∉E(G).

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

density(C)=2∑e∈E(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 v ∉ V (C), la contribución de v a C se define como

contribution(v,C)=∑u∈V(C)w(uv)  |V(C)|.

(6)

Un vértice v ∉ V (C) se llama vecino de C si hay un vértice u ∈ C 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) ∣ e∈E(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:

|Ci∩Cj|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 i, v j), se calcula de la siguiente manera:

w(vi,vj)=∑e∈E(Ci,Cj)w(e)  |V(Ci)|∗|V(Cj)|,

(9)

donde E(C i, C j) es el conjunto de enlaces que se cruzan, E(C i, C 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	Delfines	Libros políticos
Grado	0	1	17
Eigenvalue	0	2	16
Intermediación	0	0	16

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/