ARS 101: Redes de narcos en Gephi

"Venta de drogas": Análisis de Redes con Gephi (Tutorial)

Ouseful,.info

A través de un vínculo de referencia Check Yo Self: 5 Things You Should Know About Data Science (Author Note) al criticar mapeo de tweets sin más análisis ( "Si estás haciendo grafos en Gephi de tweets, es probable que estés haciendo más análisis de marketing que análisis de ciencia de datos y corténla!. por favor. no lo puedo aguantar más. ... de qué sirve a alguien tener grafos de tweets y no hacerle análisis a ellos? "), me encontré con el blog [sin curso] Analytics Made Skeezy de John Foreman:

Analytics Made Skeezy es un blog falso. Cada post es parte de una narrativa más grande diseñada para enseñar una variedad de temas de análisis mientras se mantiene interesante. El uso de una sola narrativa me permite contrastar diferentes enfoques dentro del mismo mundo falso. Y en última instancia, eso es lo que este blog es acerca de: enseñar al lector cuándo usar ciertas herramientas analíticas.

Rebotando a través de ejemplos descritos en algunos de los puestos hasta la fecha, Even Wholesale Drug Dealers Can Use a Little Retargeting: Graphing, Clustering & Community Detection in Excel and Gephi no es sorprendente que me haya llamado la atención. Ese puesto se describe, en forma narrativa, cómo utilizar Excel para preparar y dar forma a un conjunto de datos para que pueda ser importado en Gephi como un archivo CSV de imitación y luego ejecutar a través de estadística de la modularidad de Gephi; el conjunto de datos aumentada clase modularidad puede ser exportado de los datos de laboratorio Gephi y re-presentado en Excel, con lo cual el uso juicioso de la columna de clasificación y formato condicional se usa para tratar de generar algún tipo de conocimiento acerca de los racimos / grupos descubiertos en los datos - al parecer, "Gephi puede aspirar un poco por darnos ese tipo de visión a veces. Depende del grafo y lo que estamos tratando de hacer ". Y además:

Si usted tenía un gran conjunto de datos que se preparó en un grafo de vecinos más cercanos recortado, tener en cuenta que visualizándolo en Gephi es sólo por diversión. No es necesario para la penetración real, independientemente de lo que los montones de presentaciones de tweets-extensión-como se visualiza-en-Gephi podrían decirle (amordáceme). Sólo tiene que hacer la pieza de detección de la comunidad. Se puede utilizar para ese Gephi o las bibliotecas que utiliza. R y Python ambos tienen un paquete llamado igraph que hace estas cosas también. Lo que usted utiliza, sólo tiene que obtener las tareas de la comunidad de su gran base de datos para que pueda funcionar cosas como el análisis agregado sobre ellos a la inteligencia brotan de cada grupo.

No estoy necesariamente de acuerdo con la implicación de que a menudo necesitamos hacer algo más que mirar a cuadros bonitos en Gephi para dar sentido a un conjunto de datos; pero sí creo que también podemos utilizar Gephi de una manera activa para mantener una conversación con los datos, generando algún tipo de ideas preliminares a cabo sobre el conjunto de datos que entonces podemos explorar más a fondo el uso de otras técnicas analíticas. Entonces, ¿qué voy a tratar de hacer en el resto de este post es ofrecer algunas sugerencias acerca de una o dos maneras en las que podríamos utilizar Gephi para comenzar a conversar con el mismo conjunto de datos descrito en el puesto Narcotraficante Cambio de destino. Antes de hacerlo, sin embargo, le sugiero que lea el post original y tratar de llegar a algunas de sus propias conclusiones acerca de lo que los datos podrían estar diciéndonos ...

...

¿Listo? En resumen, el conjunto de datos original ( "Inventario") es una lista de "ofertas", con columnas relativas a los dos tipos de cosas: 1) cualidad de un acuerdo; 2) una columna por un distribuidor que señala si ellos tomaron ese trato. entonces se genera una matriz de cliente / cliente y el coseno similitud entre cada cliente calculado (nota: otras métricas de distancia están disponibles ...) indicando la medida en la que participó en acuerdos similares. La selección de los tres vecinos más similares a los de cada cliente crea un "grafo de vecinos más próximos recortado", que se munged en un formato de datos CSV-parecida a la Gephi puede importar. Gephi se utiliza entonces para hacer un análisis visual muy rápida / superficial (y con descuento), y ejecutar el algoritmo de detección de la modularidad / agrupación.

Entonces, ¿cómo iba yo he atacado este conjunto de datos (Nota: IANADS (no soy un científico de datos ;-)

Una forma sería tratarlo desde el principio como definir un grafo en el que los distribuidores están conectados a los oficios. Utilizando una versión ligeramente ordenado de la ficha de inventario 'del conjunto de datos original en el que me quita la primera filas (metadatos) y la última (totales), y ajustado uno de los nombres de columna para eliminar los corchetes (no creo que le gusta Gephi soportes en los nombres de atributo?), he utilizado la siguiente secuencia de comandos para generar una versión GraphML con formato de sólo un grafo de este tipo.

.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#Python script to generate GraphML file import csv #We're going to use the really handy networkx graph library: easy_install networkx import networkx as nx import urllib #Create a directed graph object DG=nx.DiGraph() #Open data file in universal newline mode reader=csv.DictReader(open("inventory.csv","rU")) #Define a variable to act as a deal node ID counter dcid=0 #The graph is a bimodal/bipartite graph containing two sorts of node - deals and customers #An identifier is minted for each row, identifying the deal #Deal attributes are used to annotate deal nodes #Identify columns used to annotate nodes taking string values nodeColsStr=['Offer date', 'Product', 'Origin', 'Ready for use'] #Identify columns used to annotate nodes taking numeric values nodeColsInt=['Minimum Qty kg', 'Discount'] #The customers are treated as nodes in their own right, rather than as deal attributes #Identify columns used to identify customers - each of these will define a customer node customerCols=['Smith', 'Johnson', 'Williams', 'Brown', 'Jones', 'Miller', 'Davis', 'Garcia', 'Rodriguez', 'Wilson', 'Martinez', 'Anderson', 'Taylor', 'Thomas', 'Hernandez', 'Moore', 'Martin', 'Jackson', 'Thompson', 'White' ,'Lopez', 'Lee', 'Gonzalez','Harris', 'Clark', 'Lewis', 'Robinson', 'Walker', 'Perez', 'Hall', 'Young', 'Allen', 'Sanchez', 'Wright', 'King', 'Scott','Green','Baker', 'Adams', 'Nelson','Hill', 'Ramirez', 'Campbell', 'Mitchell', 'Roberts', 'Carter', 'Phillips', 'Evans', 'Turner', 'Torres', 'Parker', 'Collins', 'Edwards', 'Stewart', 'Flores', 'Morris', 'Nguyen', 'Murphy', 'Rivera', 'Cook', 'Rogers', 'Morgan', 'Peterson', 'Cooper', 'Reed', 'Bailey', 'Bell', 'Gomez', 'Kelly', 'Howard', 'Ward', 'Cox', 'Diaz', 'Richardson', 'Wood', 'Watson', 'Brooks', 'Bennett', 'Gray', 'James', 'Reyes', 'Cruz', 'Hughes', 'Price', 'Myers', 'Long', 'Foster', 'Sanders', 'Ross', 'Morales', 'Powell', 'Sullivan', 'Russell', 'Ortiz', 'Jenkins', 'Gutierrez', 'Perry', 'Butler', 'Barnes', 'Fisher'] #Create a node for each customer, and classify it as a 'customer' node type for customer in customerCols:     DG.add_node(customer,typ="customer") #Each row defines a deal for row in reader:     #Mint an ID for the deal     dealID='deal'+str(dcid)     #Add a node for the deal, and classify it as a 'deal' node type     DG.add_node(dealID,typ='deal')     #Annotate the deal node with string based deal attributes     for deal in nodeColsStr:         DG.node[dealID][deal]=row[deal]     #Annotate the deal node with numeric based deal attributes     for deal in nodeColsInt:         DG.node[dealID][deal]=int(row[deal])     #If the cell in a customer column is set to 1,     ## draw an edge between that customer and the corresponding deal     for customer in customerCols:         if str(row[customer])=='1':             DG.add_edge(dealID,customer)     #Increment the node ID counter     dcid=dcid+1 #write graph nx.write_graphml(DG,"inventory.graphml")

El grafo que estamos generando (descarga .graphml) tiene una estructura básica que se ve algo como lo siguiente:



Lo que quiere decir, en este ejemplo cliente C1 efectúe un único acuerdo, D1; el cliente C2 participó en cada trato, D1, D2 y D3; y el cliente C3 participó de ofertas D2 y D3.

Al abrir el archivo grafo en Gephi como un grafo dirigido, se obtiene un recuento del número de operaciones reales existían a partir del recuento de enlaces:



Si se corre la estadística media de grado, podemos ver que hay algunos nodos que no están conectados a otros nodos (es decir, que son o bien se ocupa de ningún comprador o clientes que nunca han participado en un trato):



Podemos ver estos nodos utilizando un filtro:



También podemos utilizar el filtro para otro lado, para excluir las ofertas no aceptadas, y luego crear un nuevo espacio de trabajo que contiene sólo las ofertas que fueron tomados, y los clientes que compraron en ellos:



El selector de espacio de trabajo es en la parte inferior de la ventana, en el lado derecho:



(Hmmm ... por alguna razón, el grafo no filtrado se exporta para mí ... todo el grafo era. Un error? Toqueteando con filtro de Componente Gigante, a continuación, exportar, a continuación, ejecutar el filtro de componentes gigante en el grafo exportado y cancelación parecía fijar cosas ... pero algo no está funcionando bien?)

Ahora podemos empezar a probar algunos análisis visual interactiva. En primer lugar, vamos a exponer los nodos utilizando un algoritmo de diseño fuerza dirigida (ForceAtlas2) que trata de situar los nodos de manera que los nodos que están conectados están situados cerca uno del otro, y los nodos que no están conectados se mantienen separados (imaginar cada nodo como tratando de repeler a los otros nodos, con los enlaces tratando de tirar de ellos juntos).



Nuestra percepción visual es muy bueno para la identificación de las agrupaciones espaciales (véase, por ejemplo, los principios de la Gestalt, que conducen a muchos un truco de diseño y un cubo de pistas sobre cómo se burlan de datos, con exclusión de una manera visualmente significativa ...), pero ¿son realmente significativo ?

En este punto de la conversación que estamos teniendo con los datos, probablemente me llamo en una estadística que trata de colocar grupos de nodos conectados en grupos separados de modo que pudiera colorear los nodos en función de su pertenencia a un grupo: la estadística de modularidad:



La estadística de la modularidad es un algoritmo aleatorio, por lo que puede obtener diferentes (aunque muy similares) resulta cada vez que lo ejecute. En este caso, se descubrió seis agrupaciones o grupos de nodos interconectados posibles (a menudo, un grupo es una miscelánea ...). Podemos ver qué grupo cada nodo era lugar en aplicando una coloración de reparto



Vemos cómo las agrupaciones modularidad ampliamente mapa en que las agrupaciones visuales revelados por el algoritmo de diseño ForceAtlas2. Pero los grupos se refieren a algo significativo? ¿Qué pasa si nos volvemos las etiquetas de?



El grupo verde parece referirse a operaciones de malezas, los rojos son X, metanfetamina y ketamina ofertas, y amarillo para las cabezas de coque. Así que las ofertas no parecen agruparse en torno a diferentes tipos de trato.

Entonces, ¿qué más podríamos ser capaces de aprender? ¿La dimensión de manera operacional en un acuerdo por separado a cabo en todos los nodos (nulos en esta dimensión se relaciona con los clientes)?



Tendríamos que saber un poco más acerca de cuáles podrían ser las consecuencias de "listo para el uso", pero a simple vista nos dan una sensación al del cluster en el extremo izquierdo está dominado por las operaciones con un gran número de clientes (hay un montón de blancos nodos / cliente) y el cluster relacionados Coca-Cola de la derecha tiene un buen número de oficios (los nodos verdes) que no están listos para su uso. (Una pregunta que viene a la mente mirando esa área es: ¿existen clientes que parecen ir a por no listo para su uso oficios, y lo que podría decirnos esto sobre ellos si es así?)

Otra cosa que podríamos mirar a es el tamaño de las operaciones, así como cualquier descuento asociados. Coloreemos los nodos utilizando la herramienta de partición de acuerdo con el tipo de nodo (nombre de atributo es "típico" - nodos son ofertas (rojo) o clientes (aqua)) y luego el tamaño de los nodos de acuerdo para hacer frente a tamaño utilizando la pantalla de clasificación:



Las ofertas "fritas" pequeñas en el grupo de la mano izquierda. Mirando de nuevo a la agrupación de Coca-Cola, donde hay una mezcla de ofertas de pequeñas y grandes, otra pregunta que podríamos presentar distancia se encuentra "son los clientes que optan por allí, ya sea para los comercios grandes o pequeños?"

Volvamos al color original (a través de la partición La modularidad de color, tenga en cuenta que la asignación aleatoria de colores podría cambiar a partir del conjunto color original; botón derecho del ratón que permite volver a asignar al azar a los colores; al hacer clic en un cuadrado de color le permite color Seleccione por mano) y el tamaño de los nodos de grado de salida (es decir, la suma total de los enlaces salientes de un nodo - recuerde, el grafo se describió como un grafo dirigido, con los enlaces que van desde las transas a los clientes):



entonces he dimensionado las etiquetas para que sean proporcionales al tamaño de los nodos:






El tamaño nodo / etiqueta muestra que se ocupa tenían un montón de compradores. De calibrado por el grado de salida muestra el número de ofertas de cada cliente participó en:



Esta es una visión bastante desordenado ... volviendo al panel Diseño, podemos usar el diseño de expansión para estirarse todo el diseño, así como la Etiqueta ajusta la herramienta para sacudir nodos de modo que las etiquetas no se superponen. Observe que también puede hacer clic en un nodo para arrastrarlo por, o un grupo de nodos mediante el aumento de la "campo de visión" del cursor del ratón:



Así es como me rearmé el diseño mediante la ampliación de la disposición después ajustando las etiquetas ...:



(Una de las cosas que podría estar tentado a hacer es filtrar los usuarios que sólo participan en uno o dos o ofertas, tal vez como un wau de la identificación de los clientes habituales, por supuesto, un usuario sólo puede participar en una sola, pero muy grande trato, así que tendríamos que pensar cuidadosamente acerca de lo que eran en realidad la pregunta pidiendo a la hora de hacer una elección. por ejemplo, también puede estar interesado en la búsqueda de clientes que realizan grandes operaciones poco frecuentes, lo que requeriría una estrategia de análisis diferente.)

En la medida en que va, esto no es realmente muy interesante - lo que podría ser más convincente sería datos en relación con quien trataba con quién, pero que no está disponible inmediatamente. Lo que debemos ser capaces de hacer, sin embargo, es ver lo que los clientes están relacionados en virtud de participar de las mismas ofertas, y ver qué ofertas están relacionados en virtud de haber tratado a los mismos clientes. Podemos quizá chico nosotros mismos pensando que podemos ver en el grafo cliente-acuerdo, pero podemos ser un poco más riguroso de dos en la construcción de dos nuevos grafos: uno que muestra enlaces entre ofertas que comparten uno o más clientes comunes; y uno que muestra enlaces entre clientes que comparten una o más de las mismas ofertas.



Recordando la grafo /bipartito / "bimodal" arriba:



Eso significa que debemos ser capaces de generar grafos unimodales a lo largo de las siguientes líneas:



D1 está conectado a través de D2 y D3 C2 cliente (es decir, existe un enlace entre D1 y D2, y otro enlace entre D1 y D3). D2 y D3 se unen entre sí a través de dos rutas, C2 y C3. Así podemos ponderar el enlace entre D2 y D3 de ser más pesado, o más importante, que el enlace entre ambos D1 y D2, D1 y D3 o.

¿Y para los clientes?



C1 está conectado a través de C2 acuerdo D1. C2 y C3 están conectados por un enlace ponderada más pesado que refleja el hecho de que ambos participaron en ofertas D2 y D3.

Usted se espera que sea capaz de imaginar cómo más complejos grafos de cliente-acuerdo podría colapsar en grafos al cliente en el cliente o el acuerdo de reparto donde hay grupos de clientes (u ofertas) basado en el hecho de que múltiples, desconectado (o sólo muy débilmente conectada) hay conjuntos de ofertas que no comparten ningún clientes comunes en absoluto, por ejemplo. (A modo de ejercicio, trate de dar con algunos grafos cliente-acuerdos y luego "colapso" a los grafos del cliente del cliente o contrato de acuerdo, que estén desconectados componentes.)

Entonces, ¿podemos generar grafos de este tipo utilizando Gephi? Bueno, da la casualidad que podamos, con la función de proyección multimodo Networks. Para empezar vamos a generar un par de espacios de trabajo que contienen el grafo original, menos las ofertas que no tenían clientes. Al seleccionar uno de estos espacios de trabajo, que ahora puede generar el grafo de acuerdo de reparto (vía común de los clientes) :



Cuando corremos la proyección, el grafo se proyecta sobre un grafo de oferta-oferta:



El espesor de los enlaces describe el número de clientes dos ofertas compartidos.

Si se corre la estadística de la modularidad sobre el grafo de acuerdos -acuerdos y el color del grafo por la partición de la modularidad, podemos ver cómo las ofertas se agrupan en virtud de tener clientes compartidos:



Si a continuación, vamos a filtrar el grafo de espesor en el enlace de manera que sólo se muestran los enlaces con un grosor de tres o más (tres clientes compartidos) podemos ver algunos cómo algunos de los tipos de trato mirada como si se agrupan en torno a determinadas comunidades sociales (es decir, se suministran a la misma serie de personas):



Si ahora vamos a la otra área de trabajo que hemos creado que contiene el grafo original (menos ofertas insatisfechas), podemos generar la proyección cliente-cliente:



Ejecutar la estadística de la modularidad y recolour:



Si bien hay mucho que decir para el mantenimiento de la disposición espacial de manera que podamos comparar las diferentes parcelas, podríamos tener la tentación de volver a ejecutar el algoritmo de diseño para ver si el que se destacan las asociaciones estructurales más claramente? En este caso, no hay mucha diferencia:



Si corremos el diámetro de la herramienta de red, podemos generar algunas estadísticas de red a través de esta red cliente-cliente:



Si ahora por tamaño los nodos de centralidad de intermediación, el tamaño de las etiquetas de los nodos proporcionales, y el uso de las herramientas de expandir / etiqueta de diseño de solapamiento de ajustar la pantalla, esto es lo que obtenemos:



Thompson parece ser un personaje interesante, que abarca los diversos grupos ... pero lo que en realidad está ofertas participando en? Si volvemos al grafo del cliente-acuerdo orignal, podemos utilizar un filtro para ver el ego:



Para buscar grupos sociales reales, podemos filtrar la red basada en el peso de enlace, por ejemplo, para mostrar sólo los enlaces por encima de un determinado peso (es decir, el número de ofertas compartidos), y luego dejar caer este conjunto en un nuevo espacio de trabajo. Si corremos el estadístico de Grado Medio, se puede calcular el grado de los nodos en este grafo, y el tamaño de los nodos en consecuencia. La retransmisión del grafo nos muestra algunas redes sociales corse basado en un número significativo de operaciones compartidas:



Esperemos que ahora que está empezando a "ver" cómo podemos empezar a tener una conversación visual con los datos, preguntas diferentes de la misma en base a cosas que estamos aprendiendo sobre él. Si bien es posible que tenga que mirar realmente a los números (y pestaña Laboratorio de Datos de Gephi nos permite hacer eso), me parece que la exploración visual puede proporcionar una forma rápida de orientación (orientador?) Usted mismo con respecto a un determinado conjunto de datos, y conseguir una sentir por el tipo de preguntas que pueden formularse de la misma, preguntas que bien podría implicar una consideración detallada de los mismos números reales. Pero para empezar, el recorrido visual a menudo funciona para mí ...

PS Hay un enlace al archivo de grafo de aquí, así que si quieres probar explorar por sí mismo, puede hacerlo :-)

Scale Model usa ARS para sacar (acabadamente) tu perfil online

Este emprendimiento puede analizar cualquier persona es la personalidad en línea en menos de un minuto

Avery Hartman - Business Insider




CEO Peter Margulies del Scale Mode

Poner a prueba el software del Scale Model es como conseguir una mirada terriblemente precisa en su personalidad en línea.

La tecnología de la Scale Model analiza usted o de su compañía de red - al igual que las personas, los temas y lugares a los que hablan con frecuencia o está conectado a - con la idea de que una red se puede decir un montón de información útil, que puede ayudar a encontrar la mayor parte redes de influencia o "influenciadores" populares dentro de una comunidad y ayuda a orientar mejor a las personas a través de los esfuerzos de marketing.

Si eso suena un poco filosófica, eso es porque lo es. Pero también es muy técnico, y el equipo detrás del Scale Model ha sido cabezas hacia abajo desde el Año Nuevo la reconstrucción de su producto. El Scale Model lanzó su producto original en 2015 mayo, que fue dirigido principalmente a la publicidad de Twitter, pero la compañía se dio cuenta de que había más que podría hacer con su tecnología y giró a principios de 2016. La compañía puso en marcha una nueva y mejorada versión beta en julio , y ahora, está listo para entrar a vivir.

Scale Model es una empresa Betaworks, el estudio de emprendimiento que se puso en marcha empresas como Giphy y Chartbeat e invirtió en Tumblr, Hunt producto, y Everlane. Fue fundada por Gilad Lotán, el jefe científico de datos de la compañía, y Margulies se unió al equipo hace un año. Scale Model dice que lo hizo alrededor de $ 30.000 en ingresos antes del lanzamiento.

Las 'redes importan'

Si bien no soy cliente objetivo del Scale Model - el software está destinado a marcas y empresas, no necesariamente individuos - Me decidí probarlo y me sorprendió lo que supo de mí.

Entré en mi mango Twitter - aunque también se puede introducir una palabra clave o hashtag - y la tecnología de peinado a través de mi cuenta y creé una carta de colores, interactiva de mi comunidad.

El grafo resultante me describió en pocas palabras.


Modelo gráfico del Scale Model

Mis burbujas de colores describen todos los hitos más importantes de mi vida: Trabajo en mi papel de la universidad, The Daily Orange, la interinato en el US Today, asistiendo a la Universidad de Syracuse, viviendo en la ciudad de Nueva York y Pittsburgh, y que incluso incluyen mi hashtag favorito todo el tiempo, #Buffalove.

Esto es sólo una pequeña faceta de lo que es capaz de Scale Model, y sólo el principio de que la compañía tiene previsto llevar la tecnología.

Peter Margulies, CEO de la compañía, dijo a Business Insider que, si bien el primer paso es el lanzamiento de esta herramienta de marketing, el siguiente paso es la construcción de la tecnología que puede analizar los datos internos de la empresa.

Eso podría ser valiosa para una empresa como la yesca, dijo, lo que tiene grandes cantidades de datos de usuario. La tecnología de Scale Model podría analizar los datos para encontrar patrones, identificar conexiones o similitudes entre los usuarios, o para manchar las comunidades más pequeñas de las personas.

Pero hay usos más amplios para el software, así, dijo.

 "La tecnología podría utilizarse para analizar el debate de las armas o derechos de la mujer", dijo Margulies. "La lente a través del cual se consume la información se basa únicamente en la red, y el nudo en torno a lo que estamos construyendo es la idea de que las redes son importantes. Analizando la estructura de una red a la que puede decir mucho acerca de las personas en la red de lo que vuelvas a decir acerca de ellos mismos ".

Alejándose del enfoque de "rociar y rezar '

Margulies admite que hay un montón de herramientas como esta ya en el mercado, y que se está lanzando en un espacio lleno de gente.

Twitter y Facebook ya ofrecen herramientas de análisis y de anuncios que puede decir mucho acerca de los usuarios. Pero esas herramientas sólo cuentan los usuarios acerca de sus propias audiencias y seguidores. Margulies dice del Scale Model puede ayudar a encontrar comunidades que ya existen - como "madres bloggers" que están buscando productos para el hogar orgánicos, por ejemplo - y aprovechar esas redes externas audiencia actual de la compañía.

"Hay una gran cantidad de fatiga comprador en este espacio," dijo. "Pero hay marcas que dan cuenta de la forma en que el mundo se está moviendo, que está lejos de 'spray y rezan' - como, 'vamos a enviar el mismo mensaje a 100 millones de personas."

El Scale Model ofrece su tecnología en tres niveles diferentes: básico, que cuesta $ 99 al mes, le da acceso a algo similar a lo que he intentado anteriormente. A medida que suben en niveles de precios, se puede acceder a más funciones como un motor que detecta tendencias en las comunidades que siguen, o más herramientas de organización. El nivel de Pro cuesta $ 599 por mes y el nivel de la empresa cuesta $ 1899 por mes.

El objetivo, dijo Margulies, es que cualquier persona a partir de una pequeña empresa y para una gran corporación puede utilizar la tecnología para obtener más información sobre las personas que les gustaría conectarse.

ARS: La red criminal de Al Capone

Como ciencia de las redes ha desenterrado las relaciones superpuestas del crimen organizado en Chicago de Al Capone
Blog LSE



La fascinación pública por el crimen organizado no es nueva. En una nueva investigación que estudia las relaciones sociales de la delincuencia organizada en Chicago en la década de 1920, Chris M. Smith y Andrew V. Papachristos fueron capaces de tomar ventaja de esta fascinación con la disponibilidad de miles de notas y documentos en red criminal de Al Capone. Mediante la aplicación de análisis de redes para las relaciones criminales en las bandas de Capone, encontramos que multiplicidad - cuando dos personas tienen más de una relación - era una parte rara pero muy relevante de la red era de la prohibición de Chicago. Su investigación resaltar las formas en que multiplicidad vínculo entre el mundo terrenal y el mundo superior - un proceso que organiza la delincuencia en la sociedad.

La organización criminal de Al Capone existía antes de los días de Facebook, Twitter y de CompStat, pero la continuación y la prominencia de su sindicato se basó en el poder de las redes sociales. Para analizar el papel de las redes sociales en el crimen organizado, tomamos la ciencia de la red - un enfoque computacional de vanguardia que los mapas y las relaciones entre las medidas de la gente - y lo aplicamos a la prohibición era de Chicago. Hace casi un siglo, los EE.UU. prohibió la producción y distribución de alcohol bajo la 18ª Enmienda. Este experimento social, conocida como la Ley Seca, duró sólo 14 años, pero tuvo la consecuencia a largo plazo de fortalecimiento de la delincuencia organizada en todos los EE.UU., especialmente en ciudades como Chicago. Nuestro estudio reciente muestra cómo varios tipos de relaciones formadas y red criminal de Al Capone sostenidos.

Capone y sus compinches no dejaron ningún rastro de migas digital de datos en sus relaciones sociales; De hecho, la naturaleza de la delincuencia organizada exigió secreto, mucho antes que existiera una organización como Wikileaks. Afortunadamente para nuestros propósitos, una fascinación pública con la riqueza de Capone, moxie, y la violencia que data de la década de 1920 significó que miles de páginas de documentos relacionados con el crimen organizado de Capone se conservan en los archivos de Chicago. Se combinaron los datos grandes que piensan con el trabajo de archivo escuela detective-como el viejo con Al Capone como nuestro informante. Accedimos a más de 5.000 páginas de documentos históricos como investigador notas, documentos legales, cartas y recortes de periódico de archivos de formas de la Comisión del Delito de Chicago, el Archivo Nacional, el FBI y el IRS. cajas polvorientas y las páginas que contenían desmoronadas pepitas de información sobre el Al Capone, sus amigos, y los amigos de sus amigos.



Hemos organizado la información en cada caso individual, y la relación en una base de datos relacional, y nuestro análisis reveló 1.030 personas cuyas actividades criminales directa o indirectamente conectados con Al Capone. Sin embargo, la red de crimen organizado también contenía las relaciones personales, tales como miembros de la familia y las amistades y las relaciones legítimas que eran completamente legal pero fácilmente corruptibles, como las empresas copropietarios, asociaciones políticas, sindicales o asociaciones. El éxito en el crimen organizado requiere saber cuándo y dónde ocurrirán ataques, asegurando que los pilotos de cabeza del sindicato no estuvieron presentes durante esas incursiones, a sabiendas de que los agentes tendrían un soborno, y que garanticen que los fiscales nunca tuvieron pruebas suficientes para condenar. El éxito financiero en el crimen organizado permitido nuevas inversiones que van desde pequeñas empresas, tales como pistas de carreras de perros y tiendas de limpieza en seco, a las donaciones a las campañas políticas, y estas inversiones abierto nuevas esferas legítimas a las personas del crimen organizado.

La propiedad a la red de multiplicidad es esencial para la comprensión de las relaciones en el crimen organizado. Multiplicidad se produce cuando existe más de un tipo de relación entre dos personas. Por ejemplo, los compañeros de trabajo que también son amigos tienen relaciones múltiplex porque tienen al menos dos tipos distintos de relaciones entre ellos. Multiplicidad es una característica de gran alcance de las redes, ya que añade profundidad a las relaciones sociales y al mismo tiempo aumentando así el precio del fracaso relación. En el ejemplo múltiplex de compañeros de trabajo que también son amigos, el trabajo puede verse afectada si los amigos se meten en un desacuerdo.

Figura 1 - Relaciones No-múltiples y múltiples entre pares



La multiplicidad era una propiedad poco frecuente, pero muy relevante de la red era de la prohibición de Chicago. Nuestro estudio revela que sólo el 10 por ciento de las relaciones entre los individuos del crimen organizado contenía algo más que la actividad criminal, sino que estas relaciones se superponen múltiples eran esenciales para la operación del crimen organizado. La figura 2 muestra el mismo grupo de 1.030 individuos del crimen organizado y cada configuración representa los tres tipos muy diferentes de las relaciones entre ellos. Las parcelas del panel inferior derecho sólo el 10 por ciento de las relaciones a través de las tres redes que eran múltiples cada línea que simboliza al menos dos de los tres tipos de relaciones posibles.

Figura 2 - Las redes criminales, personales, legítimos, y múltiples en principios de 1900 el crimen organizado de Chicago


Nota: Figura impreso originalmente en Smith y Papachristos (2016). Los individuos con cero relaciones en cada red son de color gris claro; individuos que tenían relaciones en cada red son de color negro.

A pesar de que multiplicidad era raro en el crimen organizado, la superposición penal, personal y relaciones legítimas demostrado que la gente tenía que confiar entre sí durante las situaciones de riesgo y los negocios turbios, incluso cuando la corrupción y la violencia eran herramientas de trabajo. Cuando los grupos de contrabandistas ordinarias, propietarios de burdeles, y los corredores de apuestas organizadas y departamentos de policía infiltrado, tribunales, sindicatos y oficinas políticas a través de la superposición de las relaciones, el crimen organizado desarrollarse e integrarse en la sociedad en general. De hecho, argumentamos que la intersección de las redes criminales, legítimos y personales fue donde tuvo lugar el crimen organizado en Chicago. Llegamos a la conclusión de que a pesar de que no era multiplicidad omnipresente en el crimen organizado, multiplicidad pegado los mundos bajos fondos y superior juntas por encima y más allá de las personalidades de gángsteres famosos como Al Capone y asociaciones generales entre los grupos étnicos. Cuando las redes y las acciones se tambalean en dominios inciertos, no regulados, o de riesgo, confiar en sus vecinos curvados pueden muy bien ser crítico, incluso si confía en sólo unos pocos de ellos.

Nuestros resultados tienen implicaciones para el estudio de la delincuencia organizada y el estudio de las redes sociales de manera más amplia. En relación con el crimen organizado, nuestros resultados ponen de manifiesto la multiplicidad maneras une el bajo mundo y el mundo superior - un proceso que organiza la delincuencia en la sociedad y, en concreto, las redes de prohibición institucionalizadas dentro de la ciudad de Chicago. La rareza de multiplicidad pone de manifiesto la dificultad de localizar los puentes de confianza cuando no se puede confiar en cualquier ladrón, vecino, o un político, incluso cuando multiplicidad trajo los ámbitos de la delincuencia organizada en conjunto.

Este artículo está basado en el trabajo “Trust Thy Crooked Neighbor: Multiplexity in Chicago Organized Crime Networks” en American Sociological Review.

Mapeo de la red cerebral de una mosca

El primer mapeo 3-D de la red cerebral de una mosca de la fruta
MIT Technology Review

Mapeo de la estructura de la red 3-D del cerebro de una mosca es un gran paso adelante. Pero tuvieron que pasar 1.700 horas-hombre para completar, lo que significa que el trabajo humano será un importante cuello de botella para futuros avances.

Emerging Technology from the arXiv

Un objetivo importante de la neurociencia es comprender la estructura de enlaces entre las neuronas que componen el cerebro: en otras palabras, para construir un preciso mapa en 3-D de la red neuronal del cerebro.

Los investigadores han hecho progresos significativos con diversos tipos de técnicas de imagen de alta resolución. Por ejemplo, unir moléculas fluorescentes en las neuronas puede mostrar su estructura, y las imágenes del microscopio electrónico de secciones del cerebro también puede revelar la estructura a nivel neuronal.

Todas estas técnicas tienen una limitación importante. Las imágenes muestran que producen cambios en la intensidad de la imagen. Pero estas variaciones a continuación deben interpretarse para inferir la posición y forma de las neuronas reales. Este último paso es una tarea difícil cuando las neuronas y las conexiones entre ellas se cuentan por miles y millones.





Lo que se necesita es una mejor manera de crear un diagrama de cableado en 3-D del cerebro, una especie de esqueleto de las conexiones neuronales.

Hoy en día, que se hace posible gracias a la labor de Ryuta Mizutani y amigos de la Universidad de Tokai, en Japón. Estos chicos han reutilizado una técnica para producir modelos de esqueleto similar al de las moléculas y lo utilizó para mapear las neuronas en el cerebro de una mosca de la fruta. El resultado es el primer modelo en 3-D de esta red de neuronas.

El trasfondo de todo esto radica en la bioquímica. Los bioquímicos se enfrentan a un problema similar cuando crean modelos en 3D de moléculas complejas. Comienzan mediante la creación de un cristal de la molécula de interés. Luego zap con rayos X y medir el patrón de difracción de esta forma, una técnica conocida como cristalografía de rayos x.

Pero hay un problema. Los rayos X son difractados por la nube de electrones que rumores en torno a los átomos en la molécula. Así que los datos reflejan los cambios en la densidad de electrones dentro de la molécula. Las posiciones reales de los átomos tienen que inferirse de estos datos. Cuando la estructura es compleja, esto no es una tarea simple.

Los químicos tienen una gran cantidad de experiencia con esto. Desde hace algunos años, se han utilizado un enfoque de modelado por computadora para resolver el problema. Funciona mediante la estimación de la posición de un átomo en el espacio de tres dimensiones, la colocación de un nodo en ese lugar en el modelo, y luego conectarlo por un alambre virtual a la posición estimada de la siguiente átomo, y así sucesivamente. De este modo, el software se acumula un modelo de alambre virtual de la molécula.

Ahora Mizutani ha reutilizados este software para determinar la posición 3-D y la forma de las neuronas. Esto es más complicado debido a que las neuronas no son objetos puntuales como los átomos, sino objetos en forma de líneas que se pueden torcer y curva de manera compleja.

El equipo recoge sus datos utilizando una técnica llamada tomografía de rayos x. Ellos pickle un cerebro de la mosca en un tinte de plata, bombardear con rayos X, y luego medir la forma en que los rayos X son dispersados ​​en varias direcciones. Esto produce un mapa en 3-D intensidad de la imagen de la forma de plata en las neuronas absorber los rayos x.

El siguiente paso es la clave: el uso de los datos para estimar la posición y forma de las neuronas reales. Mizutani y lugar co los datos en un espacio de tres dimensiones de 840 por 1.250 por 1.200 voxels. Utilizan las intensidades de absorción de rayos x para estimar si una neurona está presente en particular voxel. Luego se construyen un modelo de alambre mediante la estimación de la forma en la neurona se extiende hacia cualquiera de los voxels adyacentes.

Por supuesto, el modelo tiene que comprobar que la red resultante es compatible con la que dos neuronas adyacentes no se interpretan como una sola neurona prolongado, por ejemplo. Así que el software comprueba continuamente la naturaleza de la red resultante, en busca de posibles anomalías. Cualquier anomalía que no puede resolver se deja por un operador humano para solucionarlo.

Este modelo tiene una resolución de alrededor de 600 nanómetros, y muestra unas 100.000 neuronas, que el modelo se resuelve en unos 15.000 huellas. Fue un esfuerzo importante para el equipo. "Se necesitaron 1.700 horas-hombre para construir el modelo de esqueleto", dicen.

Pero los resultados son claramente vale la pena. La técnica produce el primer modelo de alambre de 3-D de un hemisferio del cerebro de la mosca en el que la posición y la forma de cada neurona se asignan mediante coordenadas cartesianas en 3-D.

Este modelo muestra una amplia gama de estructuras neuronales conocidas-el modelo de trazado 360 procesos neuronales separadas. Pero también reveló una serie de estructuras desconocidas que son claramente importantes. "Estos resultados sugieren que las neuronas que no se pueden clasificar en grupos estructurales deben desempeñar un papel importante en las funciones del cerebro, aunque sus estructuras casi no han sido investigados," decir Mizutani y co.

Esto apunta a algún trabajo interesante por delante, tal vez con menor longitud de onda de rayos X que producen datos de mayor resolución.

Sin embargo, los datos adicionales no serán fáciles de manejar, dado que el lote actual requiere tanto trabajo. "La reconstrucción de [a mayor resolución] red cerebral parece ser prohibitivamente costoso en términos de carga de trabajo humana," decir Mizutani y co.

El análisis de datos es un importante cuello de botella, y se necesitan desesperadamente mejores técnicas automatizadas de construcción de modelos. Una clara oportunidad para los científicos de la computación con un poco de tiempo en sus manos.

Ref: arxiv.org/abs/1609.02261 : Three-Dimensional Network of Drosophila Brain Hemisphere

1609 02261

Lire plus de publications sur Calaméo

Encontrando comunidades por caminos aleatorios en redes científicas

Mapas de caminos aleatorios en redes complejas revelan estructura de comunidades
Martin Rosvall *, † y Carl T. Bergstrom *, ‡


Editado por Brian Skyrms, Universidad de California, Irvine, CA, y aprobado el 10 de diciembre de 2007 (recibido por opinión 21 julio, 2007)
PNAS

Para comprender la organización multipartito de los sistemas biológicos y sociales a gran escala, se introduce un enfoque teórico de información que revela la estructura de la comunidad en las redes ponderados y dirigidas. Utilizamos el flujo probabilidad de caminos aleatorios en una red como un sustituto de los flujos de información en el sistema real y se descomponen la red en módulos mediante la compresión de una descripción del flujo de probabilidad. El resultado es un mapa que tanto simplifica y pone de relieve las regularidades en la estructura y sus relaciones. Presentamos el método al hacer un mapa de la comunicación científica como se refleja en los patrones de citación de> 6.000 revistas. Descubrimos una organización multicéntrica con campos que varían mucho de tamaño y el grado de integración en la red de la ciencia. A lo largo de la columna vertebral de la red, incluyendo la física, la química, la biología molecular y la medicina-flujos de información bidireccional, pero el mapa revela un patrón direccional de la cita de los campos aplicados a las ciencias básicas.
Palabras claves: compresión, agrupación, teoría de la información, mapeo de ciencia, bibiometría

Los sistemas biológicos y sociales se diferencian, multipartito, integrada y dinámica. Los datos acerca de estos sistemas, ahora disponibles en escalas sin precedentes, a menudo se esquematizan como redes. Tales abstracciones son de gran alcance (1, 2), pero aún así como abstracciones siguen siendo muy compleja. Por tanto, es útil para descomponer la miríada de nodos y enlaces en módulos que representan a la red (3-5). Una representación convincente retendrá la información importante acerca de la red y reflejar el hecho de que las interacciones entre los elementos de los sistemas complejos son ponderados, direccional, interdependientes y conductora. Buenas representaciones tanto simplificar y poner de relieve las estructuras subyacentes y las relaciones que representan; son mapas (6, 7).

Para crear un buen mapa, el cartógrafo debe alcanzar un delicado equilibrio entre la omisión de las estructuras importantes de simplificación y oscureciendo las relaciones significativas en un aluvión de detalles superfluos. Los mejores mapas transmiten una gran cantidad de información, sino que requieren ancho de banda mínimo: los mejores mapas son también buenas compresiones. Al adoptar un enfoque teórico de la información, podemos medir la eficiencia con un mapa representa la geografía subyacente, y podemos medir la cantidad de detalles que se pierde en el proceso de simplificación, lo que nos permite cuantificar y resolver compensación del cartógrafo.

Mapas de redes y teoría de la codificación

En este artículo, utilizamos mapas para describir la dinámica a través de los enlaces y nodos en redes dirigidas, con pesos que representan las interacciones locales entre las subunidades de un sistema. Estas interacciones locales inducen un flujo de todo el sistema de información que caracteriza el comportamiento del sistema completo (8-12). En consecuencia, si queremos entender cómo la estructura de la red se refiere al comportamiento del sistema, tenemos que entender el flujo de información en la red. Por lo tanto, identificamos los módulos que componen la red mediante la búsqueda de una descripción eficiente de grano grueso de cómo los flujos de información en la red. Un grupo de nodos entre los cuales fluye la información rápida y fácilmente se pueden agregar y se describe como un único módulo bien comunicado; los vínculos entre los módulos de captura de las vías de flujo de información entre dichos módulos.

Sucinta que describe el flujo de información es un problema de codificación o compresión. La idea clave en la teoría de la codificación es que un flujo de datos puede ser comprimido por un código que explota regularidades en el proceso que genera la corriente (13). Utilizamos un paseo aleatorio como un proxy para el flujo de información, debido a que un paseo aleatorio utiliza toda la información en la representación de la red y nada más. Por lo tanto, proporciona un mecanismo predeterminado para generar una dinámica de un diagrama de red solo (8).

Tomando este enfoque, se desarrolla un código eficiente para describir un camino aleatorio en una red. de esta manera nos muestran que la búsqueda de estructura de la comunidad en las redes es equivalente a resolver un problema de codificación (14-16). Ejemplificamos este método al hacer un mapa de la ciencia, sobre la base de cómo fluye la información entre las revistas científicas por medio de citas.

Describiendo una trayectoria en una red. Para ilustrar lo que la codificación tiene que ver con la creación de mapas, consideremos el siguiente juego de comunicación. Supongamos que usted y yo sabemos que la estructura de una red ponderada, indica. Nuestro objetivo es elegir un código que nos permitirá describir de manera eficiente caminos de la red que surgen de un proceso de paseo aleatorio en un lenguaje que refleja la estructura subyacente de la red. ¿Cómo debemos diseñar nuestro código?
Si la compresión máxima fuera el único objetivo, podríamos codificar el camino en o cerca de la velocidad de la entropía del proceso de Markov correspondiente. Shannon mostró que se puede lograr esta velocidad mediante la asignación a cada nodo un diccionario única de las transiciones salientes (17). Sin embargo, la compresión no es nuestro único objetivo; aquí, queremos que nuestro lenguaje para reflejar la estructura de la red, queremos que las palabras que utilizamos para hacer referencia a las cosas en el mundo. El enfoque de Shannon no hacer esto por nosotros, porque cada palabra de código tendría un significado diferente dependiendo de donde se utiliza. Comparación de mapas: mapas útiles asignar nombres exclusivos a las estructuras importantes. Por lo tanto, buscamos una manera de describir o que codifica el paseo aleatorio en el que las estructuras importantes de hecho conservan nombres únicos. Veamos un ejemplo concreto. Higo. 1A muestra una red ponderada con n = 25 nodos. El espesor de enlace indica la probabilidad relativa de que un paseo aleatorio atravesará cualquier enlace en particular. Sobrepuesto en la red es una realización específica de 71 pasos de un camino aleatorio que vamos a utilizar para ilustrar nuestro juego de comunicación. En la Fig. 1, se describe este paseo con niveles crecientes de compresión (B-D), que explotan más y más de las regularidades en la red.

Fig. 1.La detección de las comunidades mediante la compresión de la descripción de los flujos de información en las redes. (A) Queremos describir la trayectoria de un paseo aleatorio en la red de tal manera que las estructuras importantes tienen nombres únicos. La línea naranja muestra una trayectoria muestra. (B) Un enfoque básico es dar un nombre único a cada nodo de la red. El código de Huffman ilustrado aquí es una forma eficaz para hacerlo. Los 314 bits de la red mencionados en los apartados describen la trayectoria de la muestra en A, a partir de 1.111.100 para el primer nodo en la caminata en la esquina superior izquierda, 1100 para el segundo nodo, etc., y terminando con 00011 para el último nodo en la caminata en la esquina inferior derecha. (C) Una descripción de dos niveles del paseo aleatorio, en el que los principales grupos reciben nombres únicos, pero los nombres de los nodos dentro de los grupos se vuelven a utilizar, los rendimientos en promedio un 32% más corta descripción para esta red. Los códigos de nombres de los módulos y los códigos utilizados para indicar una salida de cada módulo se muestran a la izquierda y la derecha de las flechas bajo la red, respectivamente. El uso de este código, podemos describir el pie en A por los 243 bits de muestra debajo de la red en C. Los tres primeros bits 111 indican que el paseo se inicia en el módulo rojo, el código 0000 especifica el primer nodo en la caminata, etc. (D) de informes sólo los nombres de los módulos, y no los lugares dentro de los módulos, proporciona un granulado grueso eficiente de la red.

Codificación de Huffman. Un método sencillo de dar nombres a los nodos es el uso de un código de Huffman (18). códigos de Huffman ahorrar espacio mediante la asignación de palabras de código cortas a eventos u objetos comunes y largas palabras de código a los raros, tanto como las palabras comunes son cortas en los idiomas hablados (19). Higo. 1B muestra una codificación Huffman sin prefijo para nuestra red de ejemplo. Cada palabra de código especifica un nodo en particular, y las longitudes de palabra de código se derivan de las frecuencias de visita nodo ergódicos de un paseo aleatorio infinitamente largo. Con el código de Huffman representada en la Fig. 1B, que son capaces de describir la específica pie 71-paso en 314 bits. Si en lugar de haber elegido un código uniforme, en la que todas las palabras de código son de igual longitud, cada palabra de código sería  25 = 5 bits de longitud y se habrían necesitado 71 · 5 = 355 bits para describir el pie.
Aunque en este ejemplo se asigna palabras de código reales a los nodos con fines ilustrativos, en general, no vamos a estar interesado en las palabras de código sí mismas, sino en el límite teórico de la forma concisa podemos especificar la ruta. Aquí, invocamos el teorema de Shannon fuente de codificación (17), lo que implica que cuando se utiliza n palabras de código para describir los n estados de una variable aleatoria X que se producen con frecuencias pi, la duración media de una palabra de código puede ser inferior a la entropía de la variable aleatoria X, y: h (x) = log -Σ1n pi (pi). Este teorema nos proporciona el aparato necesario para ver que, en nuestra ilustración Huffman, el número medio de bits necesarios para describir un solo paso en el camino aleatorio estará limitada hacia abajo por la entropía H (P), donde P es la distribución de la visita frecuencias a los nodos de la red. Definimos este límite inferior de la longitud del código para ser L. Por ejemplo, L = 4,50 bits por paso en la Fig. 1B.

Destacando funciones importantes. Adaptación de la longitud de palabras de código a las frecuencias de su uso nos da palabras de código eficientes para los nodos, pero no mapa. El mero hecho de asignar nombres de longitud apropiada a los nodos hace poco para simplificar o resaltar aspectos de la estructura subyacente. Para hacer un mapa, tenemos que separar las estructuras importantes de los detalles insignificantes. Por lo tanto, dividir la red en dos niveles de descripción. Nos reservamos nombres únicos para objetos a gran escala, los grupos o módulos que se identifican dentro de nuestra red, pero reutilizamos los nombres asociados con los detalles de grano fino, los nodos individuales dentro de cada módulo. Este es un enfoque familiar para la asignación de nombres a los objetos en los mapas: la mayoría de ciudades de Estados Unidos tienen nombres únicos, pero los nombres de calles son reutilizados de una ciudad a otra, de modo que cada ciudad tiene una calle principal y una obra de Broadway y la avenida Washington y así sucesivamente . La reutilización de los nombres de las calles rara vez causa confusión, porque la mayoría de las rutas se mantengan dentro de los límites de una sola ciudad.
Una descripción de dos niveles permite describir la ruta en menos bits que podríamos hacer con una descripción de un nivel. Nos aprovechamos de la estructura de la red y, en particular, sobre el hecho de que un caminante aleatorio es estadísticamente probable que pasen largos periodos de tiempo dentro de ciertos grupos de nodos. Fig. 1C ilustra este enfoque. Damos a cada grupo un nombre único, pero utilizamos un código de Huffman para nombrar los nodos dentro de cada grupo. Una palabra clave especial, el código de salida, se elige como parte de la codificación Huffman dentro de la agrupación e indica que el pie abandona el clúster actual. El código de salida siempre es seguido por el "nombre" o código del módulo del nuevo módulo en el que el pie se mueve [ver información de apoyo (SI) para más detalles]. Por lo tanto, asignar nombres únicos a las estructuras de grano grueso (las ciudades en la metáfora de la ciudad), sino reutilizar los nombres asociados con los detalles de grano fino (las calles de la metáfora de la ciudad). El ahorro es considerable; en la descripción de dos niveles de la Fig. 1C el límite L es de 3,05 bits por paso en comparación con 4,50 para la descripción de un nivel.

En esto radica la dualidad entre la búsqueda de la estructura de la comunidad en las redes y el problema de codificación: encontrar un código eficiente, buscamos una partición módulo M de n nodos en módulos m con el fin de reducir al mínimo la descripción duración prevista de un paseo aleatorio. Mediante el uso de la partición de módulo M, la longitud media de descripción de un solo paso está dado por

Esta ecuación se compone de dos términos: la primera es la entropía del movimiento entre los módulos, y la segunda es la entropía de los movimientos dentro de los módulos (donde en salida del módulo también se considera un movimiento). Cada uno es ponderada por la frecuencia con la que se produce en la partición particular. Aquí, q↷ es la probabilidad de que el paseo aleatorio cambia módulos en cualquier paso dado. H (𝒬) es la entropía de los nombres de los módulos, es decir, la entropía de las palabras de código subrayadas en la figura. 1D. H (𝒫i) es la entropía de los movimientos dentro del módulo, incluyendo el código de salida para el módulo i. El peso p  es la fracción de movimientos dentro del módulo que se producen en el Módulo I, más la probabilidad de módulo de E tal que Σi = 1 m = 1 + pq↷ (ver SI para más detalles) que sale.

Para todos, pero las redes más pequeñas, no es factible para comprobar todas las particiones posibles para encontrar el que minimiza la longitud de la descripción en el mapa ecuación (Ec. 1). En su lugar, se utiliza la búsqueda computacional. Primero calculamos la fracción de tiempo que cada nodo es visitado por un andador al azar utilizando el método de la potencia, y el uso de estas frecuencias de visita, se explora el espacio de posibles particiones usando un algoritmo de búsqueda codiciosa determinista (20, 21). Refinamos los resultados con un enfoque de recocido simulado (6) utilizando el algoritmo de calor al baño maría (ver SI para más detalles).

La Fig. 1D muestra el mapa de la red, con los descriptores dentro del módulo se desvanecieron; aquí los objetos significativos se han puesto de relieve y los detalles se han filtrado de distancia.

En aras de la simplicidad visual, la red ilustrativa en la Fig. 1 ha ponderado pero los enlaces no dirigidos. Nuestro método se desarrolló más en general, de manera que podamos extraer información de redes con enlaces que se dirigen, además de ser ponderados. La ecuación mapa sigue siendo el mismo; sólo el camino que nos proponemos describir debe ser ligeramente modificado para lograr ergodicidad. Se introduce una pequeña τ "probabilidad de teletransporte" en el paseo aleatorio: con τ probabilidad, el proceso salta a un nodo de azar en cualquier lugar de la red, que convierte nuestra aleatoria andador en el tipo de "persona que practica surf al azar" que impulsa el algoritmo PageRank de Google (22 ). Nuestros resultados de la agrupación son muy robustos a la elección particular de la pequeña fracción τ. Por ejemplo, siempre que τ <0,45 la partición óptima de la red en la Fig. 1 sigue siendo exactamente el mismo. En general, cuanto más significativa las regularidades, las más altas τ puede ser antes de teletransporte frecuentes inunda la estructura de la red. Elegimos τ = 0,15 que corresponde a el factor de amortiguamiento conocida d = 0,85 en el algoritmo PageRank (22).

Mapeo de flujo en comparación con maximización de la modularidad 

La forma tradicional de identificación de la estructura de la comunidad en las redes dirigidos y ponderados ha sido simplemente hacer caso omiso de las direcciones y los pesos de los enlaces. Pero tales enfoques descartan valiosa información acerca de la estructura de la red. Mediante la cartografía el flujo de todo el sistema inducida por las interacciones locales entre nodos, mantenemos la información sobre las direcciones y los pesos de los enlaces. También reconocemos su interdependencia en las redes inherentemente caracterizados por los flujos. Esta distinción hace que sea interesante comparar nuestro enfoque basado en los flujos con los enfoques topológicos recientes basados ​​en la optimización de la modularidad que también hace uso de la información sobre el peso y la dirección (23-26). En su forma más general, la modularidad para una partición dada de la red en módulos M es la suma del peso total de todos los enlaces en cada módulo, menos el peso esperado

Aquí, el wii es el peso total de enlaces que inician o terminan en el módulo I, Wiin y se wiout la in- total y el peso fuera de los enlaces en el Módulo I, y w es el peso total de todos los eslabones de la red. Para estimar la estructura de la comunidad en una red, la Ec. 2 se maximiza sobre todas las posibles asignaciones de nodos en cualquier número de módulos m. Ecs. 1 y 2 reflejan dos sentidos diferentes de lo que significa tener una red. La primera, que perseguimos aquí, se encuentra la esencia de una red en los patrones de flujo que su estructura induce. Este último sitúa efectivamente la esencia de la red en las propiedades topológicas de sus enlaces (como lo hicimos en la ref. 16).

¿Esta distinción conceptual hace ninguna diferencia práctica? Higo. La figura 2 ilustra dos redes simples para los que la ecuación mapa y la modularidad dan diferentes partitionings. Los ponderados, enlaces dirigidos muestran en la red de la figura. 2A inducir un patrón estructurado de flujo con tiempos largos de persistencia en el flujo, y limitada entre los cuatro grupos, como se subraya en la izquierda. La ecuación mapa recoge en estas regularidades estructurales, y por tanto la longitud de la descripción es mucho más corto para la división en la Fig. 2A Izquierda (2,67 bits por paso) que para la figura. 2A derecha (4,13 bits por paso). La modularidad es ciego a la interdependencia en las redes caracterizadas por flujos y por lo tanto no se puede recoger en este tipo de regularidad estructural. Sólo cuenta los pesos de los enlaces, en grados, y fuera de grado en los módulos, y por lo tanto prefiere dividir la red como se muestra en la Fig. 2A derecho con la relación de mucho peso dentro de los módulos.

Fig. 2.
Mapeo de flujo pone de relieve diferentes aspectos de la estructura que lo hace la optimización de la modularidad en redes dirigidos y ponderados. La coloración de los nodos ilustra particiones alternativas de dos redes de muestra. (Izquierda) Las particiones muestran la estructura modular optimizado por la ecuación mapa (mínima L). (Derecha) muestran la estructura de particiones como optimizada por la modularidad (Q máximo). En la red se muestra en A, la partición izquierda minimiza la ecuación mapa porque los tiempos de persistencia en los módulos son de largo; con el peso de los enlaces establecidos en negrilla a dos veces el peso de otros enlaces, un andador azar sin teletransporte tarda una media de tres pasos en un módulo antes de salir. La agrupación de la derecha da una descripción más larga duración debido a un caminante al azar tarda una media de sólo 12/5 pasos en un módulo antes de salir. La agrupación de la derecha maximiza la modularidad ya la modularidad cuenta los pesos de enlaces, en el grado-y el grado de salida de los módulos; la división de la derecha coloca los enlaces fuertemente ponderados en el interior de los módulos. En B, por la misma razón, la partición de la derecha de nuevo maximiza modularidad, pero no tan la ecuación mapa. Debido a que cada nodo es o bien un fregadero o una fuente en esta red, los enlaces no inducen ningún flujo de largo alcance, y los paseos de un solo paso se describen mejor como en la partición izquierda, con todos los nodos del mismo clúster.

En la Fig. 2B, por el contrario, no existe un patrón de flujo extendida en absoluto. Cada nodo es o bien una fuente o un sumidero, y ningún movimiento a lo largo de los enlaces de la red puede exceder más de un paso de longitud. Como resultado, el teletransporte aleatorio dominará (independientemente del tipo de teletransporte), y cualquier partición en múltiples módulos dará lugar a un alto flujo entre los módulos. Para una red tal como en la Fig. 2B, en donde los enlaces no inducen un patrón de flujo, la ecuación mapa siempre particionar la red en un solo módulo. Modularidad, ya que se ve en el patrón en los enlaces y grado a cabo en ejercicio y, separa la red en los grupos que se muestran a la derecha.

¿Qué método se debe utilizar un investigador? Depende de cuál de los dos sentidos de la red, que se describe más arriba, que el investigador está estudiando. Para el análisis de datos de la red donde los enlaces representan patrones de movimiento entre los nodos, los enfoques basados ​​en el flujo, tales como el mapa ecuación son propensos a identificar los aspectos más importantes de la estructura. Para el análisis de datos de la red donde los enlaces no representan flujos pero las relaciones en lugar de pares, puede ser útil para detectar la estructura incluso cuando no existe flujo. Para estos sistemas, métodos topológicos, tales como la modularidad (11) o la compresión basada en clúster (16) pueden ser preferibles.

Mapeo de Comunicación Científica

La ciencia es una actividad humana altamente organizada y paralelo a encontrar patrones en la naturaleza; el proceso de comunicar resultados de la investigación es tan esencial para el progreso como es el acto de llevar a cabo la investigación en el primer lugar. Por lo tanto, la ciencia no es más que un conjunto de ideas, sino también el flujo de estas ideas a través de un sistema social multipartito y altamente diferenciada. flujos de citas entre las revistas dejan entrever este flujo y proporcionar la traza de la comunicación entre los científicos (27-31). Para resaltar los campos importantes y sus relaciones, para descubrir las diferencias y cambios, para simplificar y hacer que el sistema comprensible: necesitamos un buen mapa de la ciencia.

Usando la información de enfoque teórico presentado anteriormente, hacemos un mapa del flujo de citas entre 6.128 revistas en las ciencias (Fig. 3) y las ciencias sociales (Fig. 4). Los 6,434,916 citas en esta red cruzada citación representan un rastro de la actividad científica durante el año 2004 (32). Nuestra correspondencia de los datos en una base diario por diario las citas de artículos publicados en 2004 a artículos publicados en los últimos 5 años. Excluimos las revistas que publican <12 artículos por año y aquellos que no se citan otras revistas dentro del conjunto de datos. También excluimos los únicos tres principales revistas que abarcan una amplia gama de disciplinas científicas: la ciencia, la naturaleza, y Actas de la Academia Nacional de Ciencias; el amplio alcance de estas revistas de otro modo crea una ilusión de las conexiones entre las disciplinas más estrictas, cuando en realidad pocos lectores de los artículos de física en la ciencia también son cercanos a los lectores de los artículos biomédicos en el mismo. Debido a que estamos interesados ​​en las relaciones entre revistas, excluimos también de revistas autocitas.

Fig. 3.Un mapa de la ciencia sobre la base de patrones de citas. Hemos dividido 6.128 revistas conectados por 6,434,916 citas en 88 módulos y 3.024 enlaces dirigidos y ponderados. Por simplicidad visual, solo mostramos los enlaces que el navegante aleatorio atraviesa> 1 / número 5.000 de su tiempo, y sólo se muestran los módulos que se visitan a través de estos enlaces (ver la IS para la lista completa). Debido a la clasificación automática de los nodos y enlaces por parte de la persona que practica surf al azar (22), estamos seguros de que muestra los enlaces y nodos más importantes. Para este nivel de detalle particular, capturamos 98% de los pesos de nodo y el 94% de todo el flujo.

Fig. 4.Un mapa de las ciencias sociales. Las revistas que aparecen en la edición de ciencias sociales 2004 del Journal Citation Reports (32) son un subconjunto de las que se ilustran en la Fig. 3, por un total de 1.431 revistas y 217,287 citas. Cuando hacemos un mapa de este subgrupo por su cuenta, se obtiene un mayor nivel de resolución. Los 10 módulos que corresponden a las ciencias sociales ahora son divididos en 54 módulos, pero por simplicidad solo mostramos enlaces que las visitas surfista azar un mínimo de 1 / número 2.000 de su tiempo junto con los módulos que se conectan (ver la IS para la lista completa ). Para este nivel de detalle particular, capturamos 97% de los pesos de nodo y el 90% de todo el flujo.

A través de la operación de nuestro algoritmo, los campos y los límites entre ellos surgen directamente de los datos de las citas más que de nuestras nociones preconcebidas de la taxonomía científica (véanse las Fig. 3 y 4). Nuestra única contribución subjetiva ha sido sugerir nombres razonables para cada grupo de revistas que el algoritmo identifica: economía, matemáticas, ciencias de la tierra, y así sucesivamente.

El tamaño físico de cada módulo o "campo" en el mapa refleja la fracción de tiempo que un surfista aleatorio pasa siguientes citas dentro de ese módulo. tamaños de los campos varían dramáticamente. La biología molecular incluye 723 revistas que abarcan las áreas de genética, biología celular, bioquímica, inmunología y biología del desarrollo; un surfista aleatorio gasta 26% de su tiempo en este campo, indicado por el tamaño del módulo. Tribología (el estudio de la fricción) incluye sólo siete revistas, en las que un surfista aleatorio gasta 0,064% de su tiempo.

Los enlaces ponderados y dirigidos entre campos representan flujo de citación, con el color y la anchura de las flechas que indican el volumen de flujo. Las pesadas flechas entre la medicina y la biología molecular indican un tráfico masivo de citas entre estas disciplinas. Las flechas apuntan en la dirección de la citación: A → B significa "Una cita B" como se muestra en la tecla. Estos enlaces dirigidos revelan la relación entre las ciencias básicas y aplicadas. Nos encontramos con que la antigua citan este último ampliamente, pero lo contrario no es cierto, como se ve, por ejemplo, con Geotecnología citando geociencias, citando la cirugía plástica, medicina general y sistemas de energía citando física general. El espesor de los bordes del módulo refleja la probabilidad de que un surfista aleatorio dentro del módulo seguirá una citación a una revista fuera del módulo. Estas salidas muestran una gran variación; por ejemplo, el flujo de salida es de 30% en medicina general, pero sólo el 12% en economía.

El mapa revela una estructura similar a un anillo en el que todas las disciplinas principales están conectados entre sí mediante cadenas de citas, pero estas conexiones no siempre son directos porque los campos en los lados opuestos del anillo están unidos sólo a través de campos intermedios. Por ejemplo, aunque rara vez se cita la psicología física general o viceversa, la psicología y la física en general están conectados a través de los estrechos vínculos con y entre la biología molecular y la química intermediarios. Una vez que tenemos en cuenta los pesos de los vínculos entre los campos, sin embargo, se hace evidente que la estructura de la ciencia se parece más a la letra U que como un anillo, con las ciencias sociales en un terminal e ingeniería en la otra, se unió principalmente por una columna vertebral de la medicina, la biología molecular, la química y la física. Debido a que nuestro mapa muestra el patrón de citas a artículos de investigación publicados en los 5 años, lo que representa de Solla Price llama la "frontera de la investigación" (27) en lugar de las interdependencias a largo plazo entre los campos. Por ejemplo, aunque las matemáticas son esenciales para todas las ciencias naturales, el campo de las matemáticas no es central en nuestro mapa porque sólo ciertos subcampos (por ejemplo, áreas de la física y las estadísticas) dependen en gran medida de los más recientes desarrollos en matemáticas puras y contribuyen a cambio de la agenda de investigación en este campo.

 Cuando un cartógrafo diseña un mapa, la escala o alcance del mapa influye en la elección de los cuales se representan objetos. Un mapa regional omite muchos de los detalles que aparecen en un mapa de la ciudad. Del mismo modo, en el enfoque que hemos desarrollado aquí, el tamaño o la resolución adecuada de los módulos depende del universo de los nodos que están incluidos en la red. Si comparamos el mapa de una red a un mapa de un subconjunto de la misma red, esperaríamos ver el mapa del subconjunto revelan divisiones más finas, con módulos compuestos por un menor número de nodos. Higo. 4 ilustra realizan particiones de un subconjunto de las revistas incluidas en el mapa de la ciencia: las 1.431 revistas en las ciencias sociales. La estructura básica de los campos y sus relaciones se mantiene sin cambios, con la psiquiatría y la psicología unido a través de la sociología y la gestión de la economía y la ciencia política, pero el mapa también revela más detalles. Las fracturas de antropología a lo largo de la línea divisoria física / cultural. La sociología se divide en grupos de comportamiento e institucionales. Comercialización separa de gestión. Psicología y psiquiatría revelan un conjunto de sub-disciplinas aplicadas.

El nivel de detalle adicional en el mapa centrado más estrictamente habría sido el desorden en el mapa completo de la ciencia. Cuando diseñamos mapas para ayudarnos a comprender el mundo, tenemos que encontrar ese equilibrio donde eliminamos detalles superfluos, pero destacamos las relaciones entre las estructuras importantes. Aquí, hemos demostrado cómo formalizar el precepto de este cartógrafo utilizando el aparato matemático de la teoría de la información.

ARS Avanzado: Complejo clique

Complejo clique
Wikipedia



El complejo clique de un grafo. Los grupos de tamaño uno se muestran como pequeños discos rojos; grupos de tamaño 2 se muestran como segmentos de líneas negras; grupos de tamaño 3 se muestran como triángulos de color azul claro; y grupos de tamaño 4 o tetraedros se muestran de color azul oscuro.


Los complejos cliques, complejos de bandera, e hipergrafos conformales son objetos matemáticos que están relacionados estrechamente con la teoría de grafos y la topología geométrica que cada uno describen camarillas (subgrafos completos) de un grafo no dirigido.

El complejo clique  X(G) de un grafo no dirigido G es un complejo simplicial abstracto (es decir, una familia de conjuntos finitos cerrados bajo la operación de toma de subconjuntos), formada por los conjuntos de vértices en las camarillas de G. Cualquier subconjunto de una camarilla es en sí misma una camarilla, por lo que esta familia de conjuntos cumple con el requisito de un complejo simplicial abstracto en el que cada subconjunto de un conjunto en la familia también debe estar en la familia. El complejo clique también puede ser visto como un espacio topológico en el que cada camarilla de k vértices está representado por un simplex de dimensión k - 1. El 1-esqueleto de X (G) (también conocido como el grafo subyacente del complejo) es un grafo no dirigido con un vértice por cada conjunto de 1 elemento en la familia y un enlace para cada conjunto de 2 elementos en la familia; es isomorfo a G. [1]

Los complejos clique son también conocidos como complejos de Whitney. Una triangulación Whitney o triangulación limpio de un colector (manifold) de dos dimensiones es una incrustación de un grafo de G en el colector de tal manera que cada cara es un triángulo y cada triángulo es una cara. Si un grafo G tiene una triangulación Whitney, debe formar un complejo de célula que es isomorfo al complejo Whitney de G. En este caso, el complejo (visto como un espacio topológico) es homeomorfo al colector subyacente. Un grafo G tiene un complejo clique de 2 colectores (manifold), y puede ser incrustado como una triangulación Whitney, si y sólo si G es localmente cíclico; esto significa que, para cada vértice v en el grafo, el subgrafo inducido formado por los vecinos de v forma un solo ciclo. [2]

Complejo de independencia

El complejo independencia I (G) de un grafo G se forma de la misma manera como el complejo camarilla de los conjuntos independientes de G. Es el complejo camarilla del grafo complemento de G.

Complejo de bandera

En un complejo simplicial abstracto, un conjunto S de vértices que no es en sí parte del complejo, pero de tal manera que cada par de vértices en S pertenece a algún simplex en el complejo, que se llama un simplex vacío. Mikhail Gromov define la condición de no-Δ ser la condición de que un complejo no tienen simplices vacías. Un complejo bandera es un complejo simplicial abstracto que no tiene simplices vacías; es decir, que es la condición no-Δ un complejo de Gromov satisfacer. Cualquier complejo bandera es el complejo de su camarilla 1-esqueleto. Por lo tanto, los complejos y los complejos bandera camarilla son esencialmente la misma cosa. Sin embargo, en muchos casos puede ser conveniente definir un complejo bandera directamente de algunos datos distintos de un grafo, en lugar de indirectamente como el complejo clique de un grafo derivado de los datos. [3]

Conforme de hipergrafo

El grafo primario G (H) de un hipergrafo es el grafo en el mismo conjunto de vértices que tiene como sus enlaces los pares de vértices que aparecen juntos en la misma hiperenlace. Un hipergrafo se dice que es conforme si cada camarilla máxima de su grafo es un hipernelace primitivo, o equivalentemente, si cada camarilla de su grafo primario está contenida en alguna hiperenlace. [4] Si se requiere el hipergrafo sea descendente cerrado (por lo que contiene todos los hiperenlaces que se contienen en algunos hiperenlaces) entonces el hipergrafo es conforme con precisión cuando se trata de un complejo de bandera. Esto se relaciona el lenguaje de hipergrafos al lenguaje del complejo simplicial.

Ejemplos y aplicaciones

La subdivisión baricéntrica de cualquier complejo C de células es un complejo de bandera que tiene un vértice por célula de C. Una colección de vértices de la subdivisión baricéntrica formar un simplex si y sólo si la colección correspondiente de células de C forman una bandera (una cadena en el inclusión de pedido de las células). [3] En particular, la subdivisión barycentric de un complejo celular en un 2-colector da lugar a una triangulación Whitney del colector.

El complejo orden de un conjunto parcialmente ordenado se compone de las cadenas (subconjuntos totalmente ordenado) del orden parcial. Si cada par de algún subconjunto es en sí mismo ordenó, entonces todo el subconjunto es una cadena, por lo que los complejos satisface la condición de la orden de no-Δ. Se puede interpretar como el complejo camarilla del grafo de la comparabilidad de la orden parcial. [3]

El complejo de empardamiento (matching complex) de un grafo consiste en los conjuntos de enlaces ninguno de cuyos pares comparten un punto final; de nuevo, esta familia de conjuntos satisface la condición de no-Δ. Puede ser visto como el complejo camarilla del grafo complemento del grafo de líneas del grafo dado. Cuando el complejo juego se denomina sin ninguna representación grafo concreta como contexto, significa el complejo juego de un grafo completo. El complejo juego de un grafo bipartito completo K_m,n es conocida como un complejo de tablero de ajedrez. Es el clique de del grafo complemento del grafo de una torre, [5] y cada uno de sus simplices representa una colocación de torres en un tablero de m × n de ajedrez de tal manera que no hay dos de las torres atacan entre sí. Cuando m = n ± 1, las formas complejas de tablero de ajedrez una pseudo-colector.

El complejo Vietoris-Rips de un conjunto de puntos en un espacio métrico es un caso especial de un complejo clique, formado a partir del grafo de disco unidad de los puntos; Sin embargo, cada complejo clique X(G) puede ser interpretada como el complejo Vietoris-Rips de la métrica camino más corto en el grafo subyacente G.

Hodkinson y Otto (2003) describen una aplicación de hipergrafos conformales en la lógica de las estructuras relacionales. En ese contexto, el grafo de Gaifman de una estructura relacional es el mismo que el grafo subyacente del hipergrafo que representa la estructura, y una estructura esté vigilado si corresponde a un hipergrafo conformal.

Gromov mostró que un complejo cúbico (es decir, una familia de hipercubos intersección cara a cara) forma un CAT (0) espacio si y sólo si el complejo está simplemente conectado y el enlace de cada vértice forma un complejo bandera. Una reunión compleja cúbica estas condiciones a veces se llama una cubicación o un espacio con paredes. [1] [6]

Referencias

1. Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R., Surveys on Discrete and Computational Geometry: Twenty Years Later (PDF), Contemporary Mathematics, 453, Providence, RI: AMS, pp. 49–86.
2. Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0-444-87489-5.
3. Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation, 15 (5–6): 875–885, arXiv:math.GT/0309036, doi:10.1142/S0218196705002669.
4. Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B., Handbook of Geometric Topology, Elsevier, pp. 373–422.
5. Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics, 9: R17.
6. Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358.
7. Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", The Bulletin of Symbolic Logic, 9 (3): 387–405, doi:10.2178/bsl/1058448678.
8. Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258: 123–135, doi:10.1016/S0012-365X(02)00266-2.
9. Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.