ARS y visualización con Pajek

Análisis y visualización de redes de gran tamaño con el paquete del programa Pajek
Andrej Mrvar y Vladimir Batagekj

Complex Adaptive Systems Modeling 20164: 6
DOI: 10.1186 / s40294-016-0017-8 © Mrvar y Batagekj. 2016

Resumen

Pajek es un paquete de programas para el análisis y visualización de grandes redes (redes que contiene hasta mil millones de vértices, no hay límite, excepto el tamaño de la memoria-en el número de líneas). Ha estado disponible desde hace 20 años. El programa, documentación y material de apoyo se pueden descargar y utilizar de forma gratuita para uso no comercial de su página web: http://mrvar.fdv.uni-lj.si/pajek/



Palabras clave

Pajek Análisis PajekXXL de las redes de gran visualización de las redes
Fondo

Las grandes redes se pueden encontrar en todas partes, por ejemplo, las redes sociales, las conexiones entre las personas (relaciones de parentesco, amistad, Facebook, Twitter, WWW); el comercio entre las organizaciones o países; redes de citación y co-autoría (por ejemplo, obtenido de la Web of Science); llamadas telefónicas; listas en ciencias de la computación de flujo; molécula orgánica en la química (por ejemplo, ADN, las redes de interacción proteína-proteína, la investigación del genoma); conexiones entre las palabras en el texto o diccionarios; las redes de transporte (aerolíneas, calles, ...).

Revisión

Historia

El desarrollo del programa Pajek comenzó en 1996, cuando Andrej Mrvar comenzó su trabajo en su tesis de doctorado sobre el análisis y la visualización de grandes redes de la Facultad de Informática y Ciencias de la Información, Universidad de Ljubljana (asesor prof. dr. Vladimir Batagekj). Aunque Pajek se ha desarrollado ahora por 20 años, sigue siendo el único programa general disponibles en el mercado que pueden manejar grandes redes (redes con hasta un mil millones de vértices; no hay límite, excepto el tamaño de la memoria-del número de líneas). Pajek ahora es utilizado por varias universidades (por ejemplo, de la Universidad de Oxford, la Universidad de California en Irvine, San Diego, Amsterdam ...) y las empresas (por ejemplo, el Deutsche Bundesbank, Volkswagen AG, SPSS Corea, Banco de Inglaterra, Cisco, Basilea Banco de Pagos Internacionales asentamientos, del Departamento de Policía de Kansas City Missouri, Departamento de Policía de Indianápolis ...). Pajek se cita (marzo de 2016) más de 2000 veces en la Web of Science y más de 6000 veces en Google Académico. Las citas se pueden encontrar también en algunas revistas importantes como la naturaleza y la Investigación del Genoma. Pajek fue el ganador de la William D. Richards Jr., Software Award en 2013.

Principales objetivos de Pajek

En el análisis Pajek y visualización de grandes redes se realizan utilizando seis tipos de datos (objetos): red (gráfico); partición (propiedades nominales u ordinales de vértices); vector (propiedades numéricas de vértices); clúster (subconjunto de vértices); permutación (reordenamiento de vértices, propiedades ordinales); y la jerarquía (estructura de árbol general sobre los vértices). De esta manera se organiza ventana principal Pajek (ver Fig. 1 para la instantánea de la ventana principal Pajek).


Fig. 1. Ventana principal Pajek

Los principales objetivos en el diseño de Pajek son:

• apoyar la abstracción por descomposición (recursiva) de una gran red en varias redes más pequeñas que se pueden tratar adicionalmente usando métodos más sofisticados (Batagelj y Mrvar 1998; Batagelj et al., 1999);
• proporcionar al usuario con algunas herramientas de visualización potentes (Batagekj y Mrvar 2002, 2003);
• implementar una selección de algoritmos eficientes (subquadratic) para el análisis de las redes de gran tamaño (Batagekj y Mrvar 2014).

Operaciones

De acuerdo con los objetivos principales, Pajek contiene varias operaciones básicas sobre sus objetos. Pajek no es "un solo programa clic ', algunos usuarios llaman' la calculadora de red '. Esto significa que para obtener algún resultado de varias operaciones básicas deben ser ejecutados en una secuencia. De hecho posibilidad de combinar diferentes operaciones básicas da Pajek un poder especial.

Algunas de estas operaciones básicas disponibles en Pajek incluyen: subredes de extracción; la reducción de partes seleccionadas de las redes; búsqueda de componentes conectados (débil, fuerte, biconexas); la búsqueda de caminos más cortos, k-vecinos, flujo máximo; centralidades de vértices y centralizaciones de redes (grado, cercanía, intermediación, concentradores y autoridades, coeficientes de la agrupación, de Laplace de centralidad) de computación; búsqueda fragmento; la agrupación en las redes (con o sin restricción); corretaje; Los métodos de detección de la comunidad (método de Lovaina y la agrupación VOS); rápida multiplicación red dispersa; censo triádica (Batagekj y Mrvar 2001); agujeros estructurales; islas (en vértices o líneas); contando para tres y cuatro anillos; generando diferentes tipos de redes aleatorias, redes de Petri ejecución, y muchos, muchos otros. Algunas operaciones que son adecuados sólo para redes más pequeñas también están incluidos en Pajek (por ejemplo, Pajek es el único software que incluye modelos de bloques generalizado (Batagekj et al., 2004) -un método sofisticado para dividir redes más pequeñas).

Pajek contiene varias operaciones que permiten las transiciones entre los objetos. En este sentido el análisis de grandes redes se puede realizar con fluidez. Las secuencias de comandos pueden ser definidos como una macro.

Los resultados obtenidos por Pajek (por ejemplo, las particiones y vectores) pueden ser analizados mediante R, SPSS y Excel (varias exportaciones a software estadístico se incluyen en Pajek).

Además de las redes ordinarias (dirigido o no dirigido) Pajek soporta también las redes de dos modos, redes temporales (redes cambiando con el tiempo), redes firmados (redes con líneas positiva y negativa), redes multirelational (varias relaciones definidas en el mismo conjunto de vértices ) y las redes acíclicos. operaciones especiales para este tipo de redes están disponibles, por ejemplo, diferentes métodos para redes de partición (firmado Doreian y Mrvar 1996, 2009, 2014, 2015; Mrvar y Doreian 2009; Doreian et al 2013.); varios métodos para calcular los pesos de recorrido (por ejemplo, SPC, SPLC, y SPNP) y posteriormente la determinación de caminos principales en acíclicos (por ejemplo, cita) ... redes.

Genealogías guardados en formato GEDCOM se pueden cargar en Pajek también. Las relaciones de parentesco pueden representarse como un gráfico Ore, p-grafo bipartito o p-grafo (White et al 1999;. Batagekj y Mrvar 2008). Pajek se aplicó con éxito para el análisis de grandes genealogías (por ejemplo, la búsqueda de volver a vincular los matrimonios).

Además de la norma Pajek existe también una versión especial llamada PajekXXL. PajekXXL es una edición especial del programa Pajek el que el consumo de memoria es mucho menor. Por la misma red dispersa que necesita al menos 2-3 veces menos memoria física que Pajek. Las operaciones que requiere mucha memoria (por ejemplo, la generación de redes aleatorias, extracción, reducción de ...) son por lo tanto mucho más rápido. PajekXXL se utiliza generalmente para grandes redes que no se ajustan a la memoria del ordenador disponible. Después de algunas partes interesantes se encuentran y se extraen, la versión estándar Pajek se puede utilizar para el análisis adicional.

Métodos de visualización

Existen diferentes métodos para la generación automática de esquemas de red disponibles en Pajek. El más importante (se utiliza a menudo) son: optimización Kamada-Kawai, optimización Fruchterman Reingold, mapeo VOS, Pivote MDS, dibujo en capas, la transformación de ojo de pez. Diseños obtenidos por Pajek se pueden exportar a diferentes formatos 2D o 3D de salida (por ejemplo, SVG, EPS, X3D, VOSViewer, Mago, ...). espectadores especiales y editores para estos formatos están disponibles (por ejemplo, inkscape, GSView, instantreality, Rey, ...). El uso de ellos podemos hacer otras modificaciones o diseños de examinarlos en detalle.

Pajek implementaciones de los algoritmos para el drenaje de la red automática se pusieron a prueba en varias competiciones de dibujo gráfico. Andrej Mrvar y Vladimir Batagekj tomaron parte en las competiciones en el período 1995-2005. Sus visualizaciones utilizando el programa Pajek se adjudicaron en conjunto con ocho primeros y tres segundos premios.

Publicaciones

Debido a la amplia utilización del programa de la necesidad de una monografía que describe como "Cómo hacer el análisis de redes con Pajek? 'Se hizo inevitable.

La monografía: Wouter de Nooy, Andrej Mrvar, and Vladimir Batagelj: Exploratory Social Network Analysis with Pajek fue publicado por Cambridge University Press en 2005 (de Nooy et al., 2005). se vendieron alrededor de 6000 ejemplares de la primera edición de la monografía. Alrededor de 2.500 citas de esta publicación se pueden encontrar en Google Académico. Debido a que la Cambridge University Press publicó también la segunda versión revisada y ampliada edición en 2011 (de Nooy et al. 2011). La monografía fue traducido al japonés (Pajek を 活用 し た 社会 ネ ッ ト ワ ー ク 分析) y publicado por la Universidad de Tokio Denki Press en 2009 (de Nooy et al., 2009). Fue traducido al chino por Beijing World Publishing Corporation en 2012, así (蜘蛛: 社会 网络 分析 技术). Entre tanto, la primera edición de China ya se vendió y se publicó la segunda edición china (de Nooy et al. 2012). Ver Fig. 2 para las páginas de portada con enlaces a todas las cinco ediciones de libros.


Fig. 2 Los enlaces a las cinco ediciones de libros. 1. First English Edition, 2. Second English Edition, 3. Japanese Edition, 4. First Chinese Edition, 5.Second Chinese Edition

Ejemplos de visualización con Pajek

En las Figs. se muestran 3, 4, 5, 6 y 7 algunos ejemplos típicos de análisis y visualización de grandes redes que utilizan Pajek. Varios más ejemplos se pueden encontrar en la página web Pajek: http:... // Mrvar FDV uni-lj si / pajek /.

Fig. 3 Regionalización de condados de Estados Unidos obtenidos por el método de detección de la comunidad agrupación VOS (ver imagen también interactiva en SVG:  http://​mrvar.​fdv.​uni-lj.​si/​pajek/​Exports/​uscounties2.​svg)


Fig. 4. La búsqueda de caminos más corto ejemplo: Cambio de "agua" en "vino" en cuatro pasos (cambiando, agregar y quitar una sola letra en cada paso) de la red diccionario de Knuth


Fig. 5. Diferentes formas de vértices en Pajek ( "casa", "hombre" y "mujer"). Versión interactiva: http://​mrvar.​fdv.​uni-lj.​si/​pajek/​Transparent/​ManWomanHouse.​htm


Fig. 6. Grafo simétrico 3D (visualización obtenido por mapeo VOS)


Fig. 7. El parentesco relación (p-grafo) entre dos presidentes de Estados Unidos (George Bush y Franklin Delano Roosevelt)

Discusión

Una de las consecuencias del desarrollo de 20 años en tecnologías de la información y la comunicación es la disponibilidad de gran cantidad de datos. Algunas personas llaman a este fenómeno Big Data. Ahora una gran cantidad de datos ya está disponible en un formato electrónico legible por ordenador. Los investigadores han reconocido el poder de reunir y analizar dichos datos. La necesidad de programas de computadora para analizar y visualizar grandes volúmenes de datos se convierte en inevitable. Lo mismo sucede en el área de análisis de redes sociales. Ahora podemos generar grandes redes de diferentes recursos electrónicos. Ejemplos típicos de este tipo de redes son las redes de coautoría (Batagelj y Mrvar 2000) y las citas obtenidas de la Web of Science. Pajek-programa para el análisis y visualización de grandes redes se discute en el papel.

Áreas de aplicación

Como se ha mencionado en apartados anteriores grandes redes podrían encontrarse en cualquier lugar. paquete de programas Pajek tiene varias áreas de aplicación, incluyendo: análisis de cualquier tipo de redes sociales (. Facebook, Twitter, redes en las organizaciones (Škerlavaj et al 2010), redes de relaciones internacionales, relaciones de parentesco, ...); redes de citación y co-autoría; las redes de interacción proteína-proteína; las redes de transporte, redes arqueológicos, ... Algunas personas lo utilizan también sólo como una herramienta de visualización para la visualización de cualquier tipo de redes.

Conclusión

Pajek está en constante desarrollo. Para obtener más información sobre Pajek comprobar su página web. Para aquellos que quieran aprender Pajek: Varios libros, manuales, artículos y muestras están disponibles. Se enumeran en la sección de referencias.

Referencias

• Batagelj V, Mrvar A (1998) Pajek—a program for large network analysis. Connections 21(2):47–57
• Batagelj V, Mrvar A (2000) Some analyses of Erdos collaboration graph. Soc Netw 22:173–186 MathSciNet View Article
• Batagelj V, Mrvar A (2001) A subquadratic triad census algorithm for large sparse networks with small maximum degree. Soc Netw 23:237–243View Article 
• Batagelj V, Mrvar A (2002) Pajek—analysis and visualization of large networks. Lecture notes in computer science vol 2265, Springer-Verlag, pp 477–478 
• Batagelj V, Mrvar A (2003) Pajek—analysis and visualization of large networks. In: M Juenger, P Mutzel (eds) Graph drawing software. Springer (series mathematics and visualization), pp 77–103 
• Batagelj V, Mrvar A (2008) Analysis of kinship relations with Pajek. Soc Sci Comput Rev 26(2):224–246 View Article 
• Batagelj V, Mrvar A (2014) Pajek. In: R Alhajj, J. Rokne (eds) Encyclopedia of social network analysis and mining. Springer, Heidelberg, pp 1245–1256 
• Batagelj V, Mrvar A, Zaveršnik M (1999) Partitioning Approach to visualization of large graphs. Lecture notes in computer science vol 1731. Springer-Verlag, pp 90–97 
• Batagelj V, Mrvar A, Ferligoj A, Doreian P (2004) Generalized blockmodeling with Pajek. Advances in methodology and statistics, vol 1. FDV, Ljubljana, pp 455–467 
• de Nooy W, Mrvar A, Batagelj V (2005) Exploratory social network analysis with Pajek. Cambridge University Press, New York View Article 
• de Nooy W, Mrvar A, Batagelj V (2009) Pajek を活用した社会ネットワーク分析, Tokyo Denki University Press, Tokyo 
• de Nooy W, Mrvar A, Batagelj V (2011) Exploratory social network analysis with Pajek: revised and expanded, 2nd edn. Cambridge University Press, New York View Article
• de Nooy W, Mrvar A, Batagelj V (2012) 蜘蛛 : 社会网络分析技术. Beijing World Publishing Corporation, Beijing
• Doreian P, Mrvar A (1996) A partitioning approach to structural balance. Soc Netw 18:149–168 View Article
•  Doreian P, Mrvar A (2009) Partitioning signed social networks. Soc Netw 31:1–11View Article MATH
• Doreian P, Mrvar A (2014) Testing two theories for generating signed networks using real data. Advances in Methodology and Statistics, vol 11. FDV, Ljubljana, pp 31–63 
• Doreian P, Mrvar A (2015) Structural balance and signed international relations. J Soc Struct 16 
• Doreian P, Lloyd P, Mrvar A (2013) Partitioning large signed two-mode networks: problems and prospects. Soc Netw 35:178–203 View Article 
• Mrvar A, Doreian P (2009) Partitioning signed two-mode networks. J Math Sociol 33:196–221View Article MATH
• Škerlavaj M, Dimovski V, Mrvar A, Pahor M (2010) Intra-organizational learning networks within knowledge-intensive learning environments. Interact Learn Environ 18:39–63 View Article 
• White DR, Batagelj V, Mrvar A (1999) Analysis of kinship relations with Pajek. Soc Sci Comput Rev 17(3):245–274View Article