Teorema de la amistad: En ciertas redes hay siempre un amigo de todos

Grafo de la Amistad

Wikipedia



En el campo matemático de la teoría de grafos, el grafo de amistad (o grafo de molino de viento holandés o n-fan) F_n es un grafo no dirigido planar con 2n + 1 vértices y 3n enlaces. [1]

El grafo de amistad F_n se puede construir uniendo n copias del grafo de ciclo C3 con un vértice común. [2]

Por construcción, el grafo de amistad F_n es isomorfo al grafo de molino de viento Wd(3,n). Es la unidad de distancia con circunferencia 3, diámetro 2 y radio 1. El gráfico F₂ es isomorfo al grafo de mariposa.

Teorema de la amistad

El teorema de amistad de Paul Erdős, Alfréd Rényi y Vera T. Sós (1966) [3] afirma que los grafos finitos con la propiedad de que cada dos vértices tienen exactamente un vecino en común son exactamente los grafos de amistad. De manera informal, si un grupo de personas tiene la propiedad de que cada par de personas tiene exactamente un amigo en común, entonces debe haber una persona que sea amiga de todos los demás. Sin embargo, para los grafos infinitos, puede haber muchos grafos diferentes con la misma cardinalidad que tienen esta propiedad. [4]

Mertzios y Unger dieron una prueba combinatoria del teorema de la amistad. [5] Craig Huneke dio otra prueba. [6] Alexander van der Vekens reportó una prueba formal en Metamath en octubre de 2018 en la lista de correo de Metamath. [7]

Etiquetado y coloración.

El gráfico de amistad tiene el número cromático 3 y el índice cromático 2n. Su polinomio cromático se puede deducir del polinomio cromático del gráfico de ciclo C₃ y es igual a .

El grafo de amistad F_n es elegante si y solo si n es impar. Es elegante si y solo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4). [8] [9]

Cada grafo de amistad es factor-crítico.

Teoría de grafos extremos

De acuerdo con la teoría de los grafos extremos, cada grafo con suficientes enlaces (en relación con su número de vértices) debe contener un ${\displaystyle k}$-fan como subgrafo. Más específicamente, esto es cierto para un grafo de n vértices si el número de enlaces es



donde es si k es impar y si si k es par. Estos límites generalizan el teorema de Turán sobre el número de bordes en un gráfico sin triángulos, y son los mejores límites posibles para este problema, ya que para un número menor de bordes existen gráficos que no contienen k-fan.

Referencias

1. Weisstein, Eric W. "Dutch Windmill Graph". MathWorld.
2. Gallian, J. A. (January 3, 2007), "Dynamic Survey DS6: Graph Labeling" (PDF), Electronic Journal of Combinatorics, DS6, 1-58. 
3. Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235. 
4. Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976),  "There are ${\displaystyle \scriptstyle 2^{\aleph _{\alpha }}}$ friendship graphs of cardinal ${\displaystyle \scriptstyle \aleph _{\alpha }}$", Canadian Mathematical Bulletin, 19 (4): 431–433, doi:10.4153/cmb-1976-064-1.
5. Mertzios, George; Walter Unger (2008), "The friendship problem on graphs" (PDF), Relations, Orders and Graphs: Interaction with Computer Science
6. Huneke, Craig (1 January 2002), "The Friendship Theorem", The American Mathematical Monthly, 109 (2): 192–194, doi:10.2307/2695332, JSTOR 2695332 
7. Alexander van der Vekens, Friendship Theorem (#83 of "100 theorem list") (11 October 2018) https://groups.google.com/forum/#!msg/metamath/j3EjD6ibhvo/ZVlOD3noBAAJ 
8. Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978), "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976), Colloq. Intern. du CNRS, 260, CNRS, Paris, pp. 35–38, MR 0539936.
9. Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978), "On a combinatorial problem of antennas in radioastronomy", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, pp. 135–149, MR 0519261. 
10. Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B, 64 (1): 89–100, doi:10.1006/jctb.1995.1026, MR 1328293.

Métricas para comparar grafos

Métricas para la comparación de grafos: una guía para profesionales

Peter Wills, Francois G. Meyer
Arxiv




La comparación de la estructura del grafo es una tarea ubicua en el análisis de datos y el aprendizaje automático, con diversas aplicaciones en campos como neurociencia, seguridad cibernética, análisis de redes sociales y bioinformática, entre otros. El descubrimiento y la comparación de estructuras como las comunidades modulares, los clubes ricos, los centros y los árboles en los datos de estos campos permite comprender los mecanismos generativos y las propiedades funcionales del grafo.



A menudo, dos grafos se comparan mediante una medida de distancia por pares, con una pequeña distancia que indica similitud estructural y viceversa. Las opciones comunes incluyen distancias espectrales (también conocidas como distancias λ) y distancias basadas en afinidades de nodo. Sin embargo, aún no se ha realizado ningún estudio comparativo de la eficacia de estas medidas de distancia para discernir entre topologías de grafos comunes y diferentes escalas estructurales.
En este trabajo, comparamos las métricas de los grafos y las medidas de distancia de uso común, y demostramos su capacidad para discernir entre las características topológicas comunes que se encuentran tanto en los modelos de grafos aleatorios como en los conjuntos de datos empíricos. Presentamos una imagen a escala múltiple de la estructura del grafo, en la que se considera el efecto de la estructura global y local sobre las medidas de distancia. Hacemos recomendaciones sobre la aplicabilidad de diferentes medidas de distancia al problema de datos de grafos empíricos basados ​​en esta vista de escala múltiple. Finalmente, presentamos la biblioteca NetComp de Python que implementa las distancias de los grafos utilizados en este trabajo.

1904 07414

Estandarizando la forma de presentar visualizaciones de red

Un estándar para presentar visualizaciones de red.

Mathieu Jacomy | Reticular



Acabo de asistir a un examen sobre mapeo de controversias en la Universidad de Aalborg, donde, entre otras cosas, los estudiantes interpretaron visualizaciones de Gephi de diferentes tipos (relacionadas con la imagen de arriba). Había redes de páginas de Wikipedia sobre la crianza de los hijos. Los estudiantes fueron bastante buenos a pesar de los problemas comunes sobre cómo hablar de redes. El ejercicio es difícil, y no esperamos que la mayoría de los estudiantes lo dominen en el momento del curso (en este caso, 3 semanas a tiempo completo). Sin embargo, es cierto que, en mi opinión, existe una forma estándar de presentar la visualización de su red. Me di cuenta de que sería útil compartir mi opinión informada sobre cómo presentar su red.

Permítanme primero abordar dos posibles malentendidos.

1. No se trata de tu método. Hay infinitas cantidades de diseños de investigación válidos que involucran la visualización de redes. No soy la policía divertida. No voy a discutir cuáles son buenas o malas.
2. No se trata de evaluar la calidad del diseño. Ese es un tema muy válido, tengo mucho que decir al respecto y es algo crucial que me viene a la mente al leer algo como "el estándar de oro para la visualización de redes". Sin embargo, no es lo que quiero decir aquí.

Lo que quiero abordar en esta publicación es qué aspectos debe cubrir, en qué orden y, lo que es más importante, cómo debe cubrirlos. Si alguna vez se sintió perdido en un laberinto argumentativo al presentar su red, quédese conmigo.

Pero antes de comenzar a sugerir lo que debe decir y cómo, debo presentar lo que considero las cuatro capas clave de cualquier discurso en una visualización de red. Me tomaré el tiempo de detallarlos, por el momento solo mencionaré su existencia con la imagen de abajo. Si está familiarizado con el trabajo de Bruno Latour, puede reconocer una cadena de referencia. De lo contrario, comprenderá en el camino: la clave es reconocer las traducciones entre las capas.

Que deberias decir

Asumimos la situación clásica: estás presentando mapas de red hechos por ti mismo. Usted sabe todo lo que hay que saber sobre el proceso, desde la recolección hasta el refinado y la visualización. Tienes alguna experiencia en el tema. Su audiencia comienza con una pregunta muy abierta como "¿Puede decirnos de qué se trata?".

1. Declarar el propósito del trabajo.

Indique el tema primero, sus preguntas de investigación, si tiene alguna, y / o lo que intentó lograr.

Puede ser muy corto pero sigue siendo importante.

Nunca visualizamos una red por el simple hecho de visualizar una red. Siempre hay un motivo subyacente. Interpretar una red nunca es simple y usted y su público corren el riesgo de perderse en el proceso. Indicar hacia dónde te diriges proporciona una ayuda de bienvenida para orientarte.

2. Describe lo que traduce la visualización.

Explique de manera concisa el proceso que ha llevado a la visualización. Es una cadena con muchos pasos que requiere claridad. Use los términos apropiados y haga que cada paso lleve al siguiente explícito.

Hay dos estrategias válidas para narrar esto, dependiendo de la situación:

1. Describa el proceso en un orden pseudo cronológico, desde la recolección hasta la visualización.
2. Comience con el objeto físico (la hoja impresa, la pantalla ...) y vaya hacia su origen.

Elige lo que te haga sentir cómodo. Es posible que desee aprovechar esta ocasión para explicar el proceso, o lo ha hecho antes y desea ir directo al punto. En ambos casos hay una serie de elementos que debe proporcionar.

Debe explicar los pasos clave del proceso y usar los términos apropiados para hablar sobre cada uno de ellos. Aquí usaré la estrategia número 2, es decir. para narrar los pasos a partir del objeto físico y de ir hacia arriba a través del proceso. Habría variaciones dependiendo de su diseño de investigación, solo asumiré la situación común descrita en la mayoría de los tutoriales de Gephi.

En pocas palabras, cada paso del proceso es una de las cuatro capas que introduje anteriormente. Cada capa está traduciendo la capa justo debajo, y el objetivo es hacer que cada traducción sea explícita.

Describe cómo la imagen traduce la red.

La imagen o mapa es el objeto físico que ofrece empíricamente a su audiencia para comprender su trabajo (junto con sus explicaciones, por supuesto). Debes explicar de dónde viene todo lo visible en la imagen. En un escenario típico esto sería, por ejemplo:

• La imagen ha sido producida mediante la visualización de una red.
• Los círculos están representando los nodos. Todos los nodos han sido representados.
• Las líneas representan los enlaces. Todos los enlaces también han sido representados.
• Los textos son etiquetas de nodos, solo mostramos los más importantes.
• El tamaño de cada círculo representa el grado del nodo.
• El color de cada ronda representa la categoría del nodo.
• El grosor de una línea representa el ponderador del enlace.
• El color de las líneas se ha establecido en un gris claro para evitar el exceso de saturación visual.
• La colocación de los nodos se ha decidido mediante un algoritmo que analiza sus conexiones, sin considerar otros atributos como su categoría.
• La leyenda precisa el código de color de las categorías de nodos y la escala del grosor del enlace.

Explica cómo funciona el diseño

El algoritmo de diseño debe ser explicado. En el caso de Force Atlas 2 y muchos otros, los puntos importantes son:

• El diseño coloca los nodos solo en función de sus enlaces, ignora todos los atributos.
• Funciona de forma iterativa al hacer que todos los nodos se rechacen entre sí y los nodos conectados se atraigan entre sí. Por diseño converge a un equilibrio que depende de las posiciones de inicio aleatorias.
• La proyección resultante se dice isotópica: no tiene ejes específicos y se puede girar o voltear sin perder sus características. Se supone que se debe interpretar en términos de distancias relativas.

En caso de que se utilicen dichos ajustes, también merecen ser mencionados:

• Gravedad: una fuerza adicional limita la propagación de los nodos, lo que genera un sesgo menor, pero permite optimizar el espacio durante la visualización.
• Prevenga la superposición: la ubicación de los nodos se ha ajustado para que no se superpongan, lo que genera un sesgo menor pero optimiza la legibilidad durante la visualización.

Nota: no creo que valga la pena formalizar una capa adicional, aquí una proyección matemática a un espacio 2D, aunque sea lo que realmente hacemos.

Describe cómo la red traduce los datos de origen.

La red o grafo es la lista de nodos y la lista de enlaces utilizados como una estructura de datos en un software como Gephi. La red se traduce visualmente por la imagen, pero no es la imagen. De manera similar, a menudo traduce datos menos refinados, pero no es esa información.

Debes explicar qué representan los nodos y los enlaces. En otros términos, debe describir cómo se relacionan con los datos sin procesar (ver más abajo). Por ejemplo:

• Los nodos representan palabras mencionadas al menos 10 veces, excluyendo una lista de palabras de parada (stop words).
• Los enlaces representan co-ocurrencia, es decir, cuando aparecen dos palabras en el mismo documento.
• El peso de los enlaces representa en cuántos documentos aparecen las palabras juntas.

Explicar cómo los datos de origen se refieren al mundo empírico.

Debe explicar de dónde provienen los datos de origen y cómo se seleccionaron. La elección de los datos para estudiar a menudo se deriva de un interés en algo preciso en el mundo empírico. Puede ser la paternidad, #blacklivesmatter, diseño nórdico ... Sea cual sea su tema o sus preguntas de investigación, proporcionó un marco interpretativo de los datos de origen, por ejemplo, porque ciertos elementos se utilizan como representantes para obtener información sobre su objeto de interés original.

Podría ser, por ejemplo, mencionar que estaba interesado en un tema relacionado con cuestiones de género, pero por razones prácticas tenía que ser lo suficientemente específico, lo que lo llevó a elegir el tema de la crianza de los hijos que ya se ha descrito en Wikipedia.

3. Interpreta tu mapa de red

Ahora que su audiencia sabe de qué se trata todo esto, puede analizar el contenido de su mapa de red. Su interpretación consistirá en una serie de afirmaciones que se basarán primero en la imagen y atravesarán las capas hasta el mundo empírico, si es posible.

Hay muchas formas de organizar tu interpretación. Puede consultar las sugerencias que Tommaso Venturini, Debora Pereira y yo hemos propuesto para el análisis visual de la red. No abriré esa discusión aquí. Lo único importante es la esencia de cualquier argumento de ese tipo: expone las características de la red que son visibles en la imagen y argumenta que estas características se originan en los datos de origen de una manera que permite decir algo sobre el mundo empírico. Este camino interpretativo es largo, lo sé. Lamentablemente, tal es la situación a la que te enfrentas. La ciencia es dura.

Siempre debe ser claro acerca de las traducciones cuando hace sus puntos. Este es el único truco. Ten éxito en esto, y dominarás la interpretación de la red. Hacer un buen punto tiene que ver con encontrar su camino a través de las capas. Aunque es difícil. Dedicaré el resto de este post a desglosar esa pregunta.

Como deberias decirlo

Pon atención al vocabulario.

El pan y la mantequilla de tus argumentos son las conexiones lógicas entre los muchos elementos que convocarás. Hay tanto que decir que ni siquiera lo intentaré. Sin embargo, siempre comienza con el uso del vocabulario adecuado. Esta pregunta es crítica aquí porque, como veremos, usar los términos apropiados es su mejor defensa contra las líneas argumentativas traicioneras que lo llevarán a un laberinto de falacias.

Cada capa tiene su vocabulario específico, comencemos revisando esto.

Imagen / mapa

El siguiente vocabulario es apto para describir la imagen:

• Círculo, forma, línea, texto
• Colores, claros, oscuros.
• Gran pequeño
• Cerca, lejos
• Ocupado / denso / lleno / áreas ocupadas, agujeros, espacios en blanco
• Centro, periferia (de la imagen, de una zona…).

NO LO USE para describir la imagen en sí: nodo, enlace, hipervínculo, página web ...

Red / grafo

El siguiente vocabulario es apto para describir la red:

• Nodo, vértice
• Arista, enlace, conexión
• Peso del nodo / enlace, atributo, modalidad de un atributo
• Grado, grado, grado superior, métricas de centralidad
• Densidad (de un conjunto de nodos)
• Vecinos, hojas (nodos con 1 vecino), huérfanos (0 vecinos)
• Equivalencia estructural (tener los mismos vecinos)
• Distancia geodésica (longitud del camino más corto)
• Clusters (como el resultado de un algoritmo de clustering)
• Modularidad (de un clustering)
• ...

NO LO USE para describir la red: estar cerca o lejos, estar agrupado ...

A menudo querrá hacer conteos simples, como decir que un conjunto de nodos es grande, pequeño o mayor que ... Un conjunto de nodos puede ser un clúster, nodos donde el atributo X toma la modalidad Y, nodos de un grado de X o Más, vecinos de X ...

Fuente de datos

Este paso no siempre es solo un paso en el proceso y puede tomar muchas formas. El punto importante es que los datos siempre se han transformado: se han limpiado, filtrado, refinado ... Hay tantas posibilidades que no puedo ofrecer una visión general. Voy a elegir algunos ejemplos.

Si sus datos en bruto son páginas de Wikipedia, se aplica el siguiente vocabulario:

• página web
• Hipervínculo, enlace de hipertexto
• En enlaces de texto, ver también enlaces.
• ...

Si sus datos en bruto eran un conjunto de documentos en un análisis de co-ocurrencia:

• Documento de texto
• Párrafo, expresión, n-grama, palabra
• Co-ocurrencia
• Frecuencia de término
• ...

Sus datos pueden provenir de una base de datos de patentes, de Twitter o Facebook, de una fuente cualitativa ... Cada uno de estos casos tiene sus propios tipos de objetos, relaciones y vocabulario.

NO LO USE para describir los datos en bruto: nodo, enlace, estar conectado, estar cerca, estar agrupado ...

Mundo empírico

El vocabulario que utiliza cuando se refiere al mundo empírico puede ser:

• Personas, instituciones, actores,…
• Libros, proyectos, ideas,…
• Temas, ámbitos académicos, intereses,…
• Amistad, apuntes, afinidades, ...
• Grupos de pueblos, comunidad, cultura,…
• Notoriedad, influencia, autoridad, relevancia, ...

Cuidado con las metonimias

En la práctica, usted quiere decir "el tamaño de los nodos" y no "el tamaño de las rondas". Bien, pero estás jugando con fuego. Si dominas el ejercicio, puedes usar todo tipo de atajos porque conoces los límites. Un oyente ingenuo puede tener la impresión de que la mayoría de los conceptos son intercambiables y que puede decir indistintamente línea, enlace, lazo o hipervínculo. Está muy mal. Los problemas son reales y puede que te engañes con argumentos falaces y con lógica circular.


"Esto no es un pipa"... Sea claro sobre lo que representa y lo que se representa

La línea para no cruzar se aclara al ver cómo entendemos una metonimia, una forma de hablar en la que nos referimos a algo utilizando un concepto diferente pero estrechamente relacionado. Por ejemplo, "jurar lealtad a la corona" se refiere al soberano y no al objeto físico, por supuesto. Podemos obtener el significado correcto porque no tendría sentido jurar lealtad a una corona literal. El contexto indica si la palabra es metafórica o literal, si hay una metonimia o no. Lo mismo se aplica a nuestros conceptos. En la medida en que los nodos no tienen un tamaño (son entidades de red abstractas), está claro que los "tamaños de nodo" se refieren a "el tamaño de las formas que representan los nodos". En ese sentido, el acceso directo es válido, pero sigue siendo complicado porque usamos la palabra nodo para referirnos a las formas, y este cambio peligroso es la forma en que ocurren los accidentes. La línea de no cruzar es cuando las metonimias se vuelven ambiguas.

Cómo te atrapas en el laberinto de la lógica circular

Primero dice "esos nodos están cerca", que solo puede entenderse como una metonimia para "aquellas formas que representan nodos están cerca", luego dice "por lo que forman un grupo" y ya está pisando el límite prohibido. Como profesor, a menudo le pediré que aclare la ambigüedad, por ejemplo: “¿Puede precisar por qué forman un grupo?”. Ya que conoce el proceso, comprende que la colocación de nodos se debe al algoritmo de diseño, que es de hecho lo que espero. Sin embargo, en este punto, la confusión puede hacer que te adentres en el laberinto de la lógica circular, al responder algo como: "Es un grupo porque el algoritmo de diseño coloca los nodos cerca uno del otro". Bien podría explicar cómo funciona el algoritmo, pero no importa, ya es demasiado tarde. Te has atrapado en una falacia, ¿puedes ver por qué?

El argumento es circular porque establece que los nodos cerrados hacen que los clústeres y los clústeres hagan los nodos cercanos. Desafortunadamente, ser consciente de la circularidad realmente no ayuda. Por mi experiencia, sé que solo te das cuenta de que estás perdido cuando ya es demasiado tarde, si es que alguna vez lo haces. Evitar la falacia no se trata de reconocer la zona prohibida, se trata de no entrar en el laberinto. Se trata de tener una práctica que nunca te ponga en riesgo.

¿Cuál es la práctica segura? En primer lugar, es utilizar el vocabulario adecuado. Pero no puedo ganar la lucha contra la naturaleza humana y hacer que dejes de usar atajos. Así que la práctica segura es sobre el uso de protecciones. Siempre revise la capa donde su argumento es válido. La entrada al laberinto de la lógica circular es donde las metonimias confusas dan lugar a argumentos con desajuste de capas. Pero el desajuste de capas también puede llevar a formas menos dramáticas de malos argumentos que pueden ser muy perjudiciales para usted a pesar de su bajo perfil. Veremos cómo el control de capas ayuda a desacreditarlas.

Malos argumentos

Hay diferentes grados de argumentos erróneos, correspondientes a las diferentes formas en que puede fallar en hacer circular la cadena de referencia de una capa a la siguiente.

Tautología: atrapado en una capa.

El peor tipo de argumento es cuando no hay argumento. Una descripción simple que plantea como un punto. El pintalabios de la retórica sobre el cerdo de la trivialidad. Por ejemplo: "El clúster pro-vida se separa del clúster pro-elección manteniendo una distancia sensible". El argumento es circular: los grupos son distantes porque son distantes. Diagnóstico de este mal argumento como una falla completa para circular fuera de las dos capas superiores, la imagen y la red.



Puede desacreditar dicha declaración comprobando las capas. Hacer un punto implica varios pasos donde las características de una capa están relacionadas con la siguiente. Un argumento apropiado sería algo como esto:

• Los nodos pro-vida y pro-elección aparecen distantes en la imagen.
• Son distantes porque tienen pocas conexiones. Así es como funciona el algoritmo de diseño, pero también podemos ver que hay menos enlaces entre grupos que dentro de cada uno.
• La mayor cantidad de aristas dentro de los grupos muestra que los actores tienden a conectarse con aquellos que son similares a ellos e ignoran a los que son diferentes.
• Este comportamiento revela una oposición entre las dos comunidades.

Naturalización: saltando a conclusiones.

Un tipo de argumento malo pero menos malo es saltar sobre las traducciones, haciendo un punto incompleto. Llamo a esto "naturalización" porque saltar a conclusiones a menudo usa la retórica de la evidencia, como si la visualización fuera una manifestación natural del mundo empírico. Por ejemplo: "los pro-elección se agrupan, mostrando que comparten valores comunes". La conclusión es a veces cierta, pero la argumentación es pobre. Como profesor, me preguntaría de inmediato: "¿puede explicar por qué cree que un grupo de nodos implica compartir valores comunes?", Lo que le brinda la oportunidad de mostrar su capacidad para circular entre las capas o hacer que se dé cuenta de que está perdido. En el laberinto de la argumentación. Algunos estudiantes simplemente usan atajos, y cuando se les pide que descompriman su razonamiento, pueden hacerlo.

Una vez más, la práctica segura es verificar las capas involucradas. En este ejemplo, la proximidad pertenece a la capa de imagen (número 1). Compartir valores comunes pertenece al mundo empírico (número 4). Debes avanzar de capa en capa sin saltar sobre ninguna. Respetar el vocabulario ayuda a no confundir las capas:

• La proximidad de la pro-elección en la visualización ...
• ... proviene de la importante cantidad de enlaces entre los nodos ...
• ... lo que revela que estos actores se conocen y se vinculan entre sí en la web.
• Nuestra hipótesis es que podría ser porque comparten valores comunes.

En este ejemplo, el último punto no es muy convincente, y probablemente es simplemente falso. El formulario es válido pero no el contenido. Eso fue solo un ejemplo, pero sigue siendo cierto que la última traducción, desde los datos de origen al mundo empírico, es la más difícil. Desafortunadamente, también es el más importante.

Correr la ultima milla

Mi último consejo es correr siempre la última milla: sus argumentos deben llevar a conclusiones sobre el mundo empírico, aunque solo sea de manera hipotética. La razón por la que analiza los datos es porque quiere entender algo sobre el mundo y debe demostrar su capacidad para hacerlo.

No correr la última milla es el escollo más trágico porque solo le sucede a los buenos estudiantes, aquellos que llegaron lejos pero no pudieron derrotar al último jefe. La mala argumentación no lo lleva a la última milla, pero puede tener todos sus argumentos válidos y aun así no alcanzar la línea final.

No correr la última milla produce declaraciones analíticamente válidas pero solo sobre los datos. Por ejemplo, no mencionando la argumentación sino solo la conclusión:

• … Por lo tanto, los sitios web gubernamentales ocupan los puestos centrales en el corpus de las ONG.
• … Todas las ONG se citan en la web, excepto las asociaciones humanitarias.
• ... los sitios web de la izquierda radical están bien conectados dentro de la esfera web de la izquierda, pero no forman un grupo, al estar mal conectados entre sí.

Esas afirmaciones pueden ser técnicamente válidas, no explican bien cómo se relaciona con el mundo empírico. El tipo de argumento que espero va un poco más allá, aunque solo sea en forma de hipótesis, por ejemplo:

• ... posiblemente porque muchas ONG dependen de la financiación gubernamental, que a menudo requiere vincularse con las instituciones de financiación.
• ... porque las asociaciones humanitarias compiten por las donaciones, lo que puede llevarlas a no citar a sus competidores.
• ... a pesar de estar reunidos bajo la etiqueta común de "izquierda radical", estos actores no se reconocen entre sí y no forman una comunidad, posiblemente debido a divergencias ideológicas.

Gephi: El grafo cómo herramienta de visualización de datos

El grafo: una parte del "dataviz" explotable para mapear y explorar un sector de actividad

Mathieu BOYER | Cell'IE

"Un buen boceto es mejor que un discurso largo", Napoleón Bonaparte.

En la era de "Big Data" y "Open Data", estas bases de datos masivas presentadas en forma de tabla, se ha vuelto esencial para aplicar consultas, procesos y dispositivos de cálculo para extraer información relevante y nuevos conocimientos. De hecho, sin estas diferentes etapas, es imposible extraer cualquier valor agregado de estas tablas de valores, imponente y nebuloso.

Es entonces cuando tiene lugar la visualización de datos o "dataviz", lo que hace posible traducir una base de datos no digerible e indigestible en una serie de grafos o imágenes interpretables. Finalmente, es un pasaje "de complejidad a simplicidad" que ocurre cuando organizamos los datos en forma gráfica. Esta disciplina no es nueva y se utiliza en varios campos de actividad: inteligencia económica, geografía, marketing, periodismo, inteligencia, comunicación ... Existen cuatro formas de modelos visuales: gráficos cartesianos, cartografía, diagramas de redes. y modelos experimentales. Deseamos abordar aquí una imagen específica de la visualización de datos que se entrega al lector: el grafo.

El propósito de este artículo es visualizar en forma de grafos, la red formada por los enlaces de hipertexto de sitios alrededor de un tema: el sector del hidrógeno en Francia y en Europa. Nuestro objetivo será mapear el paisaje sectorial del hidrógeno para determinar qué actores forman parte de él. Este tema se toma como ejemplo y el enfoque es replicable para otros sectores de actividad.

Un punto metodológico sobre la construcción de un grafo.

Para entender completamente de qué estamos hablando, es importante volver sobre lo que es una grafo y algunos conceptos que extraen información relevante de ella. Puede ir directamente a la parte de explotación del grafo si ya conoce los principios generales.

Un grafo es un conjunto de nodos interconectados y enlaces entre ellos. Aplicados a la web, los nodos representan un sitio web, un actor (tomamos la sociología de la traducción, o teoría de actores de red, en la definición que tenemos de un actor), es decir, un proyecto, una empresa, una asociación, una agencia estatal, una unión ... Los arcos entre los nodos representan los enlaces de hipertexto presentes en los sitios web que rastreamos y que se refieren a otra entidad web del corpus (ellos son sitios web de la red).

La metodología del mapeo web es relativamente simple. Se puede resumir en cinco pasos principales: extracción, procesamiento, análisis, producción y presentación.

Aquí hay algunos elementos para entender la construcción de nuestros grafos.

La elección del crawler

Es necesario elegir un crawler o rastreador al hacer un mapa de la web. Elegimos utilizar Hyphe, una herramienta gratuita desarrollada por Science Po Medialab. Esta opción es la más relevante en nuestra opinión porque es una herramienta gratuita que, a diferencia de otros rastreadores del mismo tipo, ofrece un margen muy grande de Maniobra al usuario. Además, la herramienta tiene características interesantes como agregar etiquetas a sitios o convertir a archivos .xls o .gexf. Sin embargo, tenga en cuenta que se necesitan algunas horas para que Hyphe se apropie completamente Comprender los mecanismos latentes.

Puntos de entrada

El tema tratado con las geográficas: Francia y Europa. Enthesi es necesario dejar dos web sites (puntos de inicio del rastreo): Afhypac y el sitio de FCH JU. El primer sitio es una asociación de referencia en Francia para el sector del hidrógeno. Restaura a los miembros que son sus principales actores del sector del hexágono. FCH JU es una organización europea que financia proyectos europeos de colaboración en torno al hidrógeno. La idea es la de la página "Miembros" de Afhypac para obtener todos los actores principales (su sitio web). En cumplimiento de la FCH JU, la página "Proyecto" incluye todos los proyectos que han sido financiados por la organización desde 2008. Además, hace referencia a los miembros de los diferentes consorcios. Estos vuelven a sitios sus puntos de partida de la cartografía. El rastreador se ha lanzado para aspirar a los bucles de hipertexto de estos sitios.

Recuperar eso, mar y sector de actividad, existen asociaciones, grupos de profesionales, gremios, etc. que tienen un espacio miembro. Estos espacios son muy buenos puntos de partida para captar un sector de actividad que desconocemos o muy poco (el uso de una consulta simple que combina los operadores booleanos en un motor de búsqueda permite encontrar estos actores). También hay que tener en cuenta que para iniciar un rastreo, es necesario definir para cada sitio una página de inicio. Es recomendable iniciar páginas socios / miembros / miembro / etc. donde sea posible

Tratamiento post-rastreo

Uniendo que la herramienta finaliza el primer rastreo, es necesario tratar como lo que Hyphe denomina "la salida", es decir, los nuevos sitios descubiertos. Este tratamiento implica la eliminación de los sitios que pertenecen a la llamada "alta" de la Web (la capa más visible). De este modo, podemos eliminar los sitios web como Amazon, Twitter, YouTube, Apple, Facebook ... De hecho, estas entidades, se han expandido en popularidad, se concentran una gran cantidad de abrazos y se convertirán en nodos centrales de nuestra cartografía. que No tienen nada que ver con el sector del hidrógeno francés o europeo. Solo se complicarían la comprensión del grafo. En general, si hay una tendencia a sufrir cuando se rastrea un conjunto de sitios. Será necesario asegurar sistemáticamente la eliminación de aquellos que no correspondan al tema observado.

Finalización del corpus

Después de definir los sitios que se inclinarán en el corpus, de reiniciar un Rapeo desnudo, es decir, ver solo va a las estacas recién incluidas. Además, es necesario un centro de formación para eliminar la situación. En total, se realiza muy rastreos para constituir el corpus. El rastreo de la última "salida" obtenida de Hyphe hizo posible completar los temibles abrazos. Después de algunos toques finales de los sitios que serán inclinados, el corpus final contiene 539 nodos y 2.885 entrelazados.

Categorización de sitios

El análisis del grafo pasa por una doble categorización de los sitios web presentados en el corpus. Este paso esencial nos permite entender cómo cuidar la web. También disponible, durante la explotación del grafo, divulgar información de otro modo no habría estado disponible. Por lo tanto, hemos optado por clasificar los sitios web según el tipo de actor (categoría 1) y según el país o área geográfica (categoría 2)..

Categoría 1: Tipo de actor	Categoría 2: País o zona geográfica
El sitio es un proyecto. En este caso, en su mayoría proyectos europeos para nosotros.	El sitio es un proyecto y no tiene ninguna aplicación exclusivamente francesa y se llamará Europe 2.
El sitio es una organización de investigación, laboratorio, universidad, escuela, centro técnico o instituto.	El sitio es un proyecto y tiene una aplicación exclusivamente francesa (France 2 en el grafo).
El sitio es una PYME SMI.	Clasificamos como Europa cualquier sitio cuyo objeto no se refiera a una entidad que pertenezca a un país. Ejemplo: El Instituto Eifer, nacido de la colaboración entre EDF y el Instituto Karlsruher de Alemania, se identifica como Europa porque nació de la colaboración de dos países.
El sitio de un gran grupo industrial de una ETI.
El sitio representa una institución financiera o un financiero.
El sitio representa una asociación, un grupo de competitividad o un grupo diverso de actores.	Otros tipos de sitios para los cuales un país es claramente identificable serán nombrados como tales. Por ejemplo, la Universidad de Poitiers se llamará Francia. Tenemos varios países que están representados y todos tendrán sus propios colores cuando los vean.
El sitio es una comunidad territorial, un estado, una agencia / servicio nacional.
El sitio representa a un usuario final de aplicaciones de hidrógeno.
El sitio destaca un evento específico.

En general, debemos pensar en la información que queremos obtener cuando construimos su categorización. Optar por una representación por tipo de actor y país proporciona una visión general del sector. Por estas categorizaciones, emerge una visión relevante del paisaje sectorial (ver explotación del grafo).

Sin embargo, también es posible elegir clasificar por posicionamiento en la cadena de valor del sector (fabricante de baterías, integrador, generador de estaciones, investigación ...). Hay muchas posibilidades que deben ser cuidadosamente pensadas y adaptadas a las especificidades de cada sector / análisis.

Visualización del grafo

Para concluir el grafo, ahora es necesario espacializar los nodos y los enlaces, colorearlos, nombrarlos, aplicarles un tamaño ... Por lo tanto, es necesario crear lo que se puede llamar una interfaz de imagen: es el enriquecimiento de los elementos del grafo que depende de un software de visualización. No es necesario abordar aquí la cuestión de la herramienta que define el universo de posibilidades en la visualización y que puede bloquear o hacer dependiente al usuario. Para diseñar la imagen de la interfaz, usar Gephi, un software de código abierto, parece ser la mejor solución. Este, sin embargo, no es muy intuitivo y sigue siendo relativamente complejo. Aquí hay algunos tutoriales que explican muy bien cómo funciona.

Los nodos del grafo están coloreados de acuerdo con las categorizaciones, lo que da 2 grafos diferentes. A esto se agrega un tercer grafo cuyo color de nodo depende de las agrupaciones / comunidades detectadas automáticamente por el algoritmo de modularidad (o método MCL). La teoría subyacente no se desarrollará, pero aquí hay un documento para aprender más. El tamaño de los nodos no es uniforme y está relacionado con el peso asignado a ellos. Está vinculado al número de enlaces de hipertexto salientes o entrantes para un nodo determinado (cuanto más se cita un sitio, más imponente estará en el grafo).

Estas modificaciones aplicadas, debemos agregar una espacialización para completar el grafo. Hay varias opciones disponibles que dependen del tipo de grafo y lo que desea analizar. Respecto a las 3 grafos, se aplicó la misma espacialización y se llevó a cabo en 2 etapas:

1. Utilizando el algoritmo de Fruchterman Reingold. La salida del grafo final es más interesante cuando este algoritmo se usa de antemano para "airear" el grafo.
2. Utilizando Force Atlas 2, un algoritmo "dirigido por la fuerza" que posiciona cada nodo de acuerdo con los demás. Se aplicó una reducción de la dispersión de los nodos, una gravedad para acercar los nodos, una influencia nula de los enlaces y una prevención de la recuperación (más estética y legible) al grafo.

Así nos dimos cuenta de las 3 grafos siguientes.


Grafo 1: Tipo de categorización del actor.

Leyenda del grafo 1



Grafo 2: categorización por país



Leyenda del grafo 2


Grafo 3: algoritmo de modularidad de categorización

Explotación del grafo

Un principio básico es latente en un mapa de enlaces de hipertexto. Este es el principio de la homofilia, teorizado por Lazarsfeld y Merton en 1954. Menciona lo siguiente: los individuos tienden a conectarse entre sí según sus similitudes. Así, dos actores estarán más fácilmente en contacto si comparten los mismos valores, la misma cultura, la misma clase social, etc. La cartografía web es una extensión de este razonamiento sociológico. Los enlaces de hipertexto materializan las relaciones sociales y el intercambio del mismo sector de actividad (en este caso) explica la conexión entre estas entidades web.

Estas relaciones traducidas por enlaces de hipertexto son proteicas. De hecho, el enlace puede simbolizar una asociación en torno a un proyecto, una relación comercial, una relación accionaria, la pertenencia a una organización, la participación en un evento, etc. Finalmente, es la representación de una conexión que realmente tuvo lugar en algún punto "en tierra". Es sobre la base de este principio que podemos explotar los grafos.

Al analizar el grafo número 1 que clasifica los tipos de estructura, se descubre información sobre la organización del sector y el posicionamiento de los actores:

• Las organizaciones de investigación son numerosas y muy conectadas. Vienen de un grupo (ubicado a la derecha del grafo). La colaboración europea parece manifestarse en torno al sector del hidrógeno y el surgimiento del sector (aún en fase de desarrollo) puede justificar la omnipresencia de estos actores. Sería interesante realizar este trabajo de mapeo en unos pocos años; La sospecha de un hallazgo de una disminución neta puede ser de estos organismos para el beneficio de grandes grupos o de SME-SMI.
• Algunas pymes están mal conectadas. Esto puede explicar el surgimiento del sector y la actividad de las empresas que aún tienen que encontrar su lugar (grupo de sitios alrededor de Afhypac).
• Alrededor de los proyectos europeos (ubicados alrededor del FCH) giran en torno a diferentes organizaciones: SME-SMI, grandes grupos, ETI, asociaciones, organizaciones de investigación ... Después de una breve investigación, esto se explica por los métodos de financiamiento de este tipo de proyecto. De hecho, cuando los diferentes tamaños de estructuras están presentes en un consorcio, la financiación puede ser mayor o más fácilmente aceptada.
• Las organizaciones de financiamiento están fuertemente conectadas y están en el corazón de grupos como ADEME o FCH JU. Esto parece reflejar una necesidad exógena de financiamiento para los actores involucrados en el sector del hidrógeno. Esta idea refuerza un análisis inicial que muestra que este sector está en pleno desarrollo.

Si ahora tomamos la cartografía número 2 clasificando los países, podemos deducir ciertas tendencias:

• Los actores franceses están muy interconectados, pero en su mayor parte están aislados de los actores y proyectos europeos. ¿Es este el signo del retraso en este asunto de Francia en comparación con otros países europeos? Tenga en cuenta que el grafo 3 que colorea los nodos de acuerdo con el algoritmo de modularidad ha identificado muy bien a la comunidad francesa.
• La mitad del grafo (donde la concentración es menor) presenta a los actores franceses que cierran la brecha entre Europa y Francia (ejemplo: CEA, Airliquide, Symbio, Areva H2, McPhy, CNRS entre otros). Por lo tanto, estos jugadores ocupan un lugar importante y estratégico en la escena francesa y europea para el sector del hidrógeno. Estos actores por lo tanto tienen mucho poder. Recuerde que en un mapeo, los actores que hacen el enlace entre 2 o más redes deben considerarse estratégicos. Una empresa tiene mucho interés en acercarse a estos actores si desea estar presente en el panorama del hidrógeno francés y europeo.

Una tendencia importante surge en el grafo número 3:

El clúster europeo alrededor del FCH se puede dividir en 2. Esto es lo que ha presentado el algoritmo de modularidad. Una parte contiene actores más diversos (en verde en el grafo 3) y la otra parte consiste principalmente en proyectos (en púrpura). La parte verde contiene grupos más grandes y ETI, cluster competitivo, SME-SMI (que se superpone con el grafo 1) que puede explicar la división. Por el contrario, el grupo púrpura está fuertemente conectado con las organizaciones de investigación. Sigue siendo bastante complicado explicar esta distinción, pero eso es lo que podemos asumir.

Al estar en la fase de desarrollo, podemos imaginar que se destacan 2 tipos de proyectos:

• Proyectos de aplicación (demostradores);
• Y más proyectos de investigación básica.

Sin embargo, esta división puede hacernos pensar que los proyectos más aplicativos están más fuertemente conectados con el mundo industrial (cluster verde) y, a la inversa, los proyectos más "fundamentales" están en relación con el mundo de la investigación. Si este es el caso, localizar los proyectos de la aplicación se vuelve fácil.

La explotación del grafo también puede ir a través del uso de las métricas inherentes al software de visualización (puntuación de autoridad, centralidad de intermediación ...). Sabemos que la cartografía materializa un conjunto de relaciones sociales. Al combinar esto con métricas matemáticas, podemos obtener otra información. No desarrollaremos el uso de métricas aquí y lo reservaremos para un artículo futuro.

Al analizar completamente los grafos y verificarlos en forma cruzada, es posible dibujar un panorama del sector, sus actores y tendencias, permitiendo que cualquier organización vea con mayor claridad, extraiga información explotable y se abra. pistas estratégicas.

Algunas limitaciones a considerar

Antes de concluir, queríamos advertir al lector de algunas limitaciones en el uso de un mapa web. Éstos son algunos de ellos:

• Ningún grafo es exhaustiva y ninguna muestra una verdad absoluta;
• La web está cambiando rápidamente (cierre de sitios, enlaces muertos, agregando enlaces ...). Es posible que la asignación utilizada aquí ya no sea completamente precisa y cualquier asignación está destinada a evolucionar;
• El vínculo social del que hablamos, transpuesto por el enlace de hipertexto, es construido y complejo. La simple visualización del grafo no permite comprender completamente la profundidad de un enlace. Por lo tanto, es importante hacer una referencia cruzada del mapeo a través de búsquedas de información;
• La web es imperfecta, algunos enlaces y sitios no funcionan, los actores pueden no aparecer y el mapeo puede estar incompleto;
• Nunca se debe sobreinterpretar el grafo y sacar conclusiones precipitadas. Es por eso que preferimos hablar sobre tendencias y por qué abogamos por el aspecto exploratorio del mapeo.

Por lo tanto, es necesario, en nuestra opinión, redoblar la precaución durante un ejercicio como el que acabamos de presentar.

Lo hemos demostrado: el mapeo de enlaces de hipertexto permite observar la dinámica de los actores que pertenecen a un sector determinado. La punta de lanza de este trabajo es el resaltar las principales tendencias en el entorno observado que se pueden movilizar como un ancla. Este mapeo no debe verse como un fin sino como un punto de partida para que una fase de exploración active otros enfoques; Pensamos en particular en el reloj y las estrategias de influencia.

Por ejemplo, considere una empresa que quiere posicionarse en un sector del que sabe muy poco. Este tipo de mapeo podría guiar la selección de socios y relaciones potenciales (con actores autoritarios e influyentes en el sector). También podría identificar fácilmente a las organizaciones que parecen importantes y ponerlas bajo vigilancia para conocer sus direcciones estratégicas.

En resumen, la cartografía es un activo real para una organización. Ahora estamos dando rienda suelta a la imaginación de todos para implementar los pasos adaptados a las necesidades específicas de su estructura utilizando el grafo como soporte.

Fuentes :

• https://www.cairn.info/revue-i2d-information-donnees-et-documents-2015-2-p-38.htm
• https://7bis.files.wordpress.com/2010/08/thoriedesgraphes-091001023741-phpapp011.pdf
• https://www.cairn.info/revue-i2d-information-donnees-et-documents-2015-2-p-38.htm
• https://www.cairn.info/revue-i2d-information-donnees-et-documents-2015-2-p-68.htm
• https://www.cairn.info/revue-i2d-information-donnees-et-documents-2015-2-p-1.htm

Las matemáticas (redes) revolucionan el estudio de la historia

Las matemáticas están revolucionando el estudio de la historia: así es como

Matteo Valleriani
Senior Research Fellow, Max Planck Institute for the History of Science
The conversation


El estudio de la historia tradicionalmente trae a la mente imágenes de archivos oscuros y sinuosos y el olor a polvo; visiones de académicos examinando montones de documentos para descubrir secretos y encontrar la pieza faltante, montones que invariablemente son demasiado pequeños para cubrir el tema y demasiado altos para ser tratados.

Pero gracias a internet, una cantidad casi inconcebible de fuentes está ahora disponible para el historiador. La base de la investigación histórica (manuscritos, libros raros, imágenes y documentos de naturaleza privada y administrativa, como cartas y planes financieros) ahora se puede acceder desde casi cualquier lugar. Y esta mayor cantidad de fuentes históricas disponibles no solo significa que ahora lo sabemos mejor. Significa que ahora, podemos conocerlo de otra manera. Esta cantidad ha afectado la naturaleza de nuestra investigación. No solo ha cambiado los tipos de respuestas que el estudio histórico puede proporcionar, sino también qué preguntas formulamos.

La historia viene en dos sabores. Existe lo que yo llamo microhistoria, y luego está la reconstrucción histórica a largo plazo. El primero se caracteriza por estudios de caso detallados pero espacialmente limitados en el tiempo; el segundo es más bien una reflexión de segundo orden orientada por una hipótesis histórica. Este tipo abarca un largo lapso espacial y temporal, pero está informado por un número limitado de casos de estudio seleccionados.

Esto ha restringido por mucho tiempo el tipo de historia que se puede estudiar. Pero mediante el análisis matemático de grandes conjuntos de datos históricos, es posible integrar los dos enfoques, realizando un análisis profundo de fuentes de forma sistemática y cubriendo largas distancias espaciales y temporales. En el campo de la historia de la ciencia, en el que trabajo, esto nos permite investigar cómo se formaron los sistemas de conocimiento científico que ahora dictan nuestras vidas.

¿Por qué es esto posible? Primero, porque la selección de fuentes contra las cuales se prueban, modifican y, a veces se rechazan, las hipótesis históricas ha aumentado. Pero también porque un número tan grande de fuentes permite la consideración de más perspectivas simultáneamente.


Estos nuevos métodos permiten a los historiadores analizar datos mucho más variados de lo que era posible anteriormente. Pakula Piotr / Shutterstock.com

Una nueva historia

Por ejemplo, los historiadores del conocimiento ahora no solo pueden considerar un corpus de fuentes mucho más grande, como una gran cantidad de tratados científicos del pasado, sino también las fuentes relacionadas con el contexto institucional, económico y social en el que se produjeron tales tratados. Los historiadores han pedido durante mucho tiempo una historia de conocimiento contextualizada, pero hasta ahora, las reconstrucciones históricas a largo plazo solo podían conectar unos pocos ejemplos bien estudiados por medio de hipótesis específicas de naturaleza económica o conceptual.

Pero si un corpus de fuentes mucho más grande puede ser considerado y analizado en detalle, podemos reflexionar más ampliamente sobre los mecanismos de evolución del conocimiento. Esto nos permite avanzar hacia una comprensión más abstracta de nuestro pasado. Podemos hablar sobre los mecanismos de la historia, y otras humanidades, de una manera totalmente nueva e informada.

Una nueva disciplina, las humanidades digitales, surgió para permitir a los académicos administrar esta gran cantidad de información. Las fuentes históricas, sus copias electrónicas y los metadatos bibliográficos están cada vez más inmersos en un marco de anotaciones, ideas y relaciones electrónicamente producidas por los historiadores mientras estudian nuestro patrimonio material e intelectual. Se han creado repositorios apropiados para todos estos datos y se está desarrollando un formato estándar para su preservación y reutilización independientemente de estas plataformas y herramientas.

El acceso abierto a los datos, incluso más que a las publicaciones, se está convirtiendo en un imperativo. La escritura de la historia está llevando a las humanidades a contribuir a esa nueva frontera de la ciencia llamada Big Data.

Historiador-matemáticos

Entonces los historiadores ahora también tienen que entender sus propias matemáticas. Si bien una base de datos nunca es mucho más que una expresión de álgebra aritmética o lineal, la creciente cantidad de datos disponibles exige un enfoque más sofisticado. Al unir fuerzas con la sociología, la escritura de historia está ahora entrando en una nueva fase, caracterizada por la aplicación de algoritmos y flujos de trabajo tomados del campo del análisis de redes sociales.


Un ejemplo de visualización de una red social. Grandjean Martin, CC BY-SA

Los datos históricos están siendo explorados por medio de visualizaciones de gráficos y parámetros de red. En particular, algunos modelos y paquetes permiten a los historiadores simular cómo las redes cambian según las decisiones de los involucrados. Estas simulaciones se basan en hipótesis formuladas por los historiadores y codificadas en los guiones. Un ejemplo de hipótesis podría ser "las diferencias religiosas no representan ningún obstáculo para la comunicación en la sociedad científica".

Por ejemplo, el historiador Ingeborg van Vugt ha utilizado este enfoque de varias capas para explorar las diferentes formas en que circuló la información en la República de las Letras, la comunidad intelectual de larga distancia de finales del siglo XVII y XVIII en Europa y América. Tal investigación nos permite visualizar mejor cómo se desarrolló la Era de la Ilustración, impulsada por estos intelectuales. El siguiente paso podría ser estadísticamente modelar esta red, y así poder continuar con su pregunta de investigación integrando una cantidad de datos aún más amplia.

Un modelo de red para estudios en historia del conocimiento debe considerar un conjunto de datos inusualmente variado. Están los datos de naturaleza social relacionados con personas y organizaciones; relacionado con aspectos materiales de la historia, como la vida de conservación de un libro; y los datos que representan el conocimiento real, el contenido de las fuentes. Estos son tres niveles diferentes de una y la misma red en evolución para los cuales los modelos matemáticos explicativos han sido concebidos raramente y aún menos realizados. Desde esta perspectiva, la escritura de la historia está a punto de desafiar las estadísticas aplicadas.

Aunque el modelado matemático en el marco de la historia está claramente en sus primeros pasos, su introducción ya parece imparable. Esto está creando las condiciones para el surgimiento de una nueva visión, según la cual podríamos desarrollar modelos matemáticos generales para explicar cómo las ideas y el conocimiento cambiaron desde una perspectiva social e histórica. Quizás podríamos incluso utilizar estos modelos en diferentes áreas de investigación científica dedicadas al presente y al futuro. Y en un futuro así, las humanidades y la ciencia exacta comenzarán a usar el mismo lenguaje matemático.

Una historia visual del conocimiento humano, con redes

Galería: magníficas redes que nos ayudan a entender el mundo

Helen Walters | Ideas TED

Como señala el diseñador Manuel Lima en su TED Talk, Una historia visual del conocimiento humano, la red se ha convertido en una forma poderosa de visualizar gran parte de lo que está sucediendo en el mundo que nos rodea. "Las redes realmente encarnan nociones de descentralización, de interconexión, de interdependencia", dice Lima. "Esta forma de pensar es fundamental para nosotros para resolver muchos de los problemas complejos a los que nos enfrentamos hoy en día, desde decodificar el cerebro humano hasta comprender el vasto universo que existe". Aquí, Lima comparte algunos de sus gráficos de red favoritos.

Las fortalezas de las naciones

Esta imagen muestra las conexiones entre las disciplinas científicas como la astrofísica, las matemáticas y la bioquímica. Con base en 800,000 referencias dentro de 760,000 artículos científicos, Lima dice que se siente atraído por el hecho de que el gráfico muestra claramente las conexiones y adyacencias de ciertos dominios científicos. Creado por W. Bradford Paley, Dick Klavans y Kevin Boyack; imagen cortesía de W. Bradford Paley.

Visualizando la Biblia

Este mapa de 2007 de Chris Harrison muestra 63,779 referencias cruzadas encontradas en la Biblia. El gráfico de barras en la parte inferior representa capítulos (cuanto más larga sea la barra, más versículos en el capítulo). Cada referencia cruzada se representa como un solo arco con diferentes colores utilizados para reflejar la distancia entre las referencias. Imagen cortesía de Chris Harrison.

Jardín de flores

Esta visualización de Greg Judelman y Maria Lantin muestra la discusión en línea en un evento en vivo. "La flor es representativa de participantes individuales, y florece a medida que se inician nuevas conversaciones, a la vez que se crean vínculos verdes entre quienes interactúan", dice Lima. "El chat en tiempo real es un tema difícil de representar, y este es un caso interesante para el uso de una metáfora visual innovadora". Imagen cortesía de Greg Judelman.

RISD.tv

Esta imagen de Daniel Peltz, Dennis Hlynsky y Chuan Khoo representa un marco colaborativo para la producción de videos en la Escuela de Diseño de Rhode Island en los Estados Unidos. "Tenga en cuenta que los enlaces no son líneas rectas", dice Lima. "Intentaban crear un tratamiento orgánico y fluido, evocador quizás de la cadena invisible de inspiración entre los videos asociados". Imagen cortesía de Daniel Peltz.

Mapa de la ciencia

Otro gráfico que muestra las conexiones entre las disciplinas científicas, este se basó en la forma en que las personas leen los artículos científicos en línea; sus fabricantes analizaron casi mil millones de interacciones del usuario para hacer el mapa de conexiones. "En el 1300 había árboles de la ciencia; este usa la metáfora de la red para crear enlaces entre dominios entrelazados ", dice Lima. Imagen cortesía de J. Bollen, H. Van de Sompel, A. Hagberg, L. Bettencourt, R. Chute, et al.

yFiles

Aunque esto parece una obra de arte abstracto, en realidad están sucediendo muchas cosas aquí. "Es una biblioteca Java de algoritmos de diseño para gráficos, diagramas y diagramas", dice Lima. "Durante los últimos cinco años, han surgido bibliotecas de codificación que le permiten incluir sus datos y visualizarlos. Es realmente la 'templacionización' del campo ". Imagen cortesía de Roland Wiese.

Círculos de Dewey

Aquí hay otra representación de transferencia de conocimiento, esta vez dentro de la Biblioteca Pública de Seattle. La imagen muestra patrones de alquiler, basados ​​en el sistema de clasificación Dewey Decimal amado por los bibliotecarios en todas partes. Cuanto más grande sea el círculo, más personas tomarán prestados libros o medios en esa categoría. Imagen cortesía de Syed Reza Ali.

Esferas

Este es un tipo bastante típico de visualización de red, dice Lima. "En cuanto al contenido, no es único; muestra los enlaces semánticos entre palabras en español usando un modelo de visualización esférica. Pero me gusta porque está bien ejecutado ". Imagen cortesía de Santiago Ortiz.

Las galaxias se forman a lo largo de los filamentos, como gotitas a lo largo de los hilos de la telaraña

"Muchos artistas están obsesionados con las redes, y este muestra una gran instalación física que muestra que el movimiento no solo está sucediendo en dos dimensiones", dice Lima. "Es tan hermoso; rebotar en una cuerda y toda la red cambia ". Imagen cortesía de Tomas Saraceno.

En silencio

"El artista Chiharu Shiota lleva las cosas a un nivel completamente diferente", dice Lima. "Ella llena estos espacios masivos con hilo negro; a veces incluye objetos o personas en una instalación, y crea redes densas y enrevesadas de lana negra e hilo. Me encanta ver artistas que se ocupan de las redes a su manera ". Imagen cortesía de Artists Rights Society (ARS), Nueva York / VG Bild-Kunst, Bonn.

Usando métricas para detectar fraudes

Detección de fraude utilizando aprendizaje profundo (deep learning) en incrustaciones de grafos y métricas de topología

Graham Ganssle, Ph.D., P.G. || Expero

¿No estás usando grafos todavía? Si no, obviamente no has leído mis otras publicaciones en el blog. Ve a hacer eso, luego instala algo de bondad gráfica, luego regresa aquí. Te veo pronto.



De acuerdo, ahora que eres un experto en grafos, podemos continuar hablando sobre el título de este artículo. Como Andrew Ng señala en su conferencia sobre la aplicación de una función de pérdida de triplete, es común en la literatura de aprendizaje profundo que los títulos sean <dominio de interés> insertados en cualquiera de las secuencias "______ Net" o "Deep ______". En ese espíritu, iba a nombrar este papel Fraude neto o Fraude profundo, pero luego me di cuenta de que la publicación de una publicación de blog de la compañía sobre Fraude profundo probablemente no es la mejor comunicación.

Estoy divagando. Hablemos de detección de fraude.


Figura 1: Un grafo que incluye transacciones financieras corporativas regulares y transacciones financieras fraudulentas.

Lo que realmente queremos es predicción de fraude (y desde allí prevención de fraude), ¿verdad? Sí, pero eso está en una próxima publicación de blog. Hoy hablaremos de atribuir cierto comportamiento a priori a un objetivo de clase binaria, a saber, un objetivo de fraude / notfraud. Veremos dos formas de determinar si una determinada entidad ha realizado o no una actividad fraudulenta, primero utilizando incrustaciones de un grafo y, en segundo lugar, usando varias métricas de topología de un grafo.

Sé lo que estás pensando: si el fraude ya ha sido cometido, ¿a quién le importa? Según este artículo, a todos debería importarles. En 2015, afirma el autor, el costo del etiquetado de fraude falso positivo fue de 118 mil millones de dólares. Eso es mil millones. Con una "b". El costo de los casos reales de fraude fue de solo $ 9 mil millones. No me malinterpreten, nueve mil millones de smackeroos son bastantes, pero es solo el siete por ciento del total de dinero perdido. Etiquetar incorrectamente las transacciones como fraudulento vale tanto como construir una nueva estación espacial internacional. Todos los años. Entonces, sin más digresiones, permítanme mostrarles cómo ahorrar $ 118,000,000,000. (De nada)

Uso de incrustaciones de grafos: Fraude individual

Escenario número uno: desea aumentar la precisión de su herramienta de análisis de fraude de tarjetas de crédito. Primero organizaría sus datos en un grafo, creando instancias de nodos como clientes individuales y comerciantes con propiedades de nodo sobre sus historiales financieros. Construiría enlaces que representen transacciones financieras entre estas entidades con propiedades de nodo, como la marca de tiempo de la transacción y el importe pagado.

Ahora debe incrustar el grafo en un espacio dimensional inferior para que pueda usar un modelo simple para analizarlo. ¿Por qué no insertas directamente tu grafo en tu modelo? Porque las geometrías no son compatibles. Si te interesa la teoría de grafos o la geometría diferencial, léelo para comprender la última oración sobre geometrías. Para aquellos de nosotros que no están dentro de las teorías de graph thingys o different whosits, consideremos como un axioma que tenemos que insertar nuestro grafo.

Aquí hay un grafo con una seria necesidad de incrustación. Como se describió anteriormente, los nodos representan a las personas con tarjetas de crédito y a los comerciantes a quienes les cuelgan el plástico. Tenga en cuenta la compleja estructura tridimensional y la gran cantidad de enlaces, que representan las transacciones financieras.


Figura 2: un grafo antes de la incrustación. Los nodos son titulares de tarjetas de crédito y comerciantes. Los enlaces son transacciones financieras.

Las estrategias de inclusión abundan; algunos son más populares que otros por razones fuera del alcance de este artículo. Mostraré dos más comunes en la imagen siguiente, reducción de dimensionalidad por análisis de componente principal e incrustación espectral por descomposición de valores propios.


Figura 3: la incrustación bidimensional del grafo en la Figura 2. El algoritmo naranja fue PCA, el azul fue incrustación espectral.

Finalmente, estamos listos para construir un modelo. La codificación del grafo incrustado para modelar es tan simple como crear vectores de características a partir de los nodos ahora aplanados. Incluimos las propiedades de nodo (entidad) y enlace (transacción), pero también concatenamos la información de coordenadas incorporada de la imagen anterior. Luego construimos un vector objetivo (o matriz para un régimen objetivo de clase múltiple) de nuestras etiquetas conocidas, activamos nuestra GPU y lo vemos comer.

Uso de métricas de topología: fraude organizacional

Escenario número dos: desea descubrir las organizaciones de lavado de dinero de su base de datos de registros transaccionales. Este problema es un orden de magnitud más interesante que analizar registros transaccionales individuales; en lugar de buscar muestras discretas, estamos interesados ​​en analizar los anillos de interacción financiera. Este es el paradigma en el cual el grafo realmente brilla.

Echa un vistazo a la imagen a continuación. Es un conjunto de empresas que interactúan financieramente. Los colores son representativos de su "comunidad", determinada por un algoritmo de aprendizaje no supervisado. Esta discusión se está acercando peligrosamente al territorio de salsa secreta, así que lo dejo así. La pregunta es, ¿las empresas amarillas están haciendo negocios como de costumbre, o es esta comunidad amarilla realmente un anillo de lavado de dinero?


Figura 4: un grafo de empresas coloreadas por comunidad. ¿Las empresas amarillas en la parte inferior derecha son realmente frentes para un anillo de lavado de dinero?

Paso uno: Combine sus datos en la misma estructura de grafos definida en la sección anterior.

Paso dos: cree un algoritmo inteligente que extraiga subgrafos de interés (las comunidades de color en la imagen anterior) y calcule las métricas de topología para cada comunidad. "Métrica de topología" es un nombre elegante para las descripciones de la geometría del subgrafo en cuestión. Por ejemplo, una métrica de topología popular es number-of-edges; en el subgrafo amarillo tenemos 23 bordes. Existen muchas de estas métricas de topología, y calculamos varias docenas para cada subgrafo.

Paso tres: cree un vector de características de estas métricas de topología para cada subgrafo. Concatenar las propiedades del nodo en otro tipo de forma secreta. Una implementación de ejemplo de esto sería calcular las propiedades de nodo promedio de todos los nodos en el subgrafo.

Paso cuatro: construya un vector objetivo (o matriz para un régimen objetivo de clase múltiple) de nuestras etiquetas conocidas, active nuestra GPU y deje que se horneen.

Envuélvelo ya

Estas técnicas dependen en gran medida de qué tipos de datos están disponibles y la estructura de las entidades que describen estos datos. La implementación debe ser personalizada (o al menos apropiada para el pedido) para cada banco / agencia / investigador interesado en realizar este trabajo. Es probable que el uso de una solución estándar empeore el problema, pero cuando se diseñan e implementan correctamente, estas técnicas pueden ahorrar miles de millones de dólares por año.

PD Sintonícese la próxima semana para obtener una versión más sofisticada de este análisis utilizando una metodología kernelizado llamada Graph graph convolutional network.

P.P.S. La detección de fraude es un problema manejable sin grafo. ¿Desea encontrar estafadores sin volver a manipular su base de datos 100 PB en otro formato? No hay problema. Nosotros hacemos eso, también.