Mostrando entradas con la etiqueta redes. Mostrar todas las entradas
Mostrando entradas con la etiqueta redes. Mostrar todas las entradas

sábado, 15 de septiembre de 2018

Excel para solucionar el problema de la ruta más corta en redes

El problema de la ruta más corta

Excel Easy


Formular el modelo | Prueba y error | Resuelve el modelo

Utilice el solucionador en Excel para encontrar la ruta más corta desde el nodo S al nodo T en una red no dirigida. Los puntos en una red se llaman nodos (S, A, B, C, D, E y T). Las líneas en una red se llaman arcos (SA, SB, SC, AC, etc.).

Formular el modelo


El modelo que vamos a resolver se ve de la siguiente manera en Excel.

Problema de ruta más corta en Excel

1. Para formular este problema de ruta más corta, responda las siguientes tres preguntas.

a. ¿Cuáles son las decisiones que se tomarán? Para este problema, necesitamos Excel para saber si un arco está en la ruta más corta o no (Sí = 1, No = 0). Por ejemplo, si SB es parte de la ruta más corta, la celda F5 es igual a 1. De lo contrario, la celda F5 es igual a 0.

b. ¿Cuáles son las limitaciones de estas decisiones? El flujo neto (salida de flujo - entrada de flujo) de cada nodo debe ser igual a Suministro / Demanda. El nodo S solo debe tener un arco de salida (flujo neto = 1). El nodo T solo debería tener un arco entrante (flujo neto = -1). Todos los otros nodos deben tener un arco de salida y un arco de entrada si el nodo está en la ruta más corta (Flujo neto = 0) o no tiene flujo (Flujo neto = 0).

c. ¿Cuál es la medida general de rendimiento para estas decisiones? La medida general de rendimiento es la distancia total de la ruta más corta, por lo que el objetivo es minimizar esta cantidad.

2. Para que el modelo sea más fácil de entender, nombre los siguientes rangos.

Nombre del rango Celdas
From B4:B21
To C4:C21
Distance D4:D21
Go F4:F21
NetFlow I4:I10
SupplyDemand K4:K10
Total Distancia F23

3. Inserta las siguientes funciones.



Explicación: Las funciones SUMAR.SI calculan el flujo neto de cada nodo. Para el nodo S, la función SUMAR SUMA los valores en la columna Ir con una "S" en la columna De. Como resultado, solo las celdas F4, F5 o F6 pueden ser 1 (un arco de salida). Para el nodo T, la función SUMAR SUMA los valores en la columna Ir con una "T" en la columna Para. Como resultado, solo las celdas F15, F18 o F21 pueden ser 1 (un arco entrante). Para todos los demás nodos, Excel busca en la columna Desde y Hasta. La distancia total es igual al subproducto de Distance y Go.

Prueba y error


Con esta formulación, resulta fácil analizar cualquier solución de prueba.

1. Por ejemplo, el camino SBET tiene una distancia total de 16.



No es necesario usar prueba y error. A continuación describiremos cómo se puede usar Excel Solver para encontrar rápidamente la solución óptima.

Resuelve el modelo


Para encontrar la solución óptima, ejecute los siguientes pasos.

1. En la pestaña Datos, en el grupo Analizar, haga clic en Solucionar.



Nota: no puede encontrar el botón Solver? Haga clic aquí para cargar el complemento Solver.

Ingrese los parámetros del solucionador (sigue leyendo). El resultado debe ser consistente con la imagen de abajo.



Tiene la opción de escribir los nombres de rango o hacer clic en las celdas de la hoja de cálculo.

2. Ingrese TotalDistance para el objetivo.

3. Haga clic en Min.

4. Ingrese Ir para cambiar las celdas variables.

5. Haga clic en Agregar para ingresar la siguiente restricción.



6. Marque 'Hacer que las variables no restringidas sean no negativas' y seleccione 'Simplex LP'.

7. Finalmente, haz clic en Resolver.

Resultado:



La solución óptima:



Conclusión: SADCT es el camino más corto con una distancia total de 11.

domingo, 14 de enero de 2018

Base de datos de redes online Colorado Index of Complex Networks

Base de datos online Colorado Index of Complex Networks


Si necesitan conjuntos de redes para testeos, experimentación o enseñanza se puede recurrir a la Colorado Index of Complex Networks. Se puede buscar por domino, propiedades de los grafos, tamaño, y muchas condiciones más. Gracias a la Universidad de Colorado!


sábado, 25 de noviembre de 2017

Teoría de redes ayuda a lidiar con Big Data

La gran idea detrás de Big Data

ADAM FRANK  - National Public Radio



La teoría de redes tiene cientos de aplicaciones, dice el físico Adam Frank.



Matjaz Slanic / Getty Images / iStockphoto


En la primavera de 2009, el virus H1N1 / 09, conocido como "gripe porcina", dio el salto de los cerdos a las personas y comenzó a reclamar sus primeras víctimas.

Temiendo el comienzo de una pandemia mundial de gripe porcina, los aterrorizados funcionarios de salud comenzaron a planificar lo peor. La clausura de los principales aeropuertos del mundo se convirtió en la opción nuclear de su arsenal: la última esperanza para detener el virus llega a límites de contagio imparables.

Eso, sin embargo, fue antes de que dos científicos italianos demostraran que el encofrado del sistema de transporte aéreo podría retrasar el temido umbral epidémico por, como máximo, unas pocas semanas (mientras que también conduce al caos económico).

Los investigadores que proporcionaron esta información crucial no eran médicos sino físicos. Más importante aún, las matemáticas que implementaron fueron las mismas que usan diariamente los investigadores de los gigantes de "Big Data" como Facebook, Google y la NSA. También fue la misma matemática utilizada por científicos de todo el mundo que estudian el genoma humano, las eficiencias de las redes eléctricas verdes, la economía del comercio mundial y un centenar de otras aplicaciones. Era la matemática de un nuevo tipo de ciencia cuya promesa había que sopesar contra el lado oscuro de Big Data, con todas sus implicaciones para la vigilancia y el control.

Es una ciencia llamada teoría de redes.

Durante más de 400 años, la ciencia ha transformado el mundo una y otra vez al descubrir nuevas adiciones a su censo de "cosas". Los descubrimientos de gérmenes microscópicos, de campos electromagnéticos, de genes y de quarks nos introdujeron a jugadores nuevos e inimaginables en el escenario cósmico.

A medida que encontramos nuestro camino en un mundo conformado por Big Data, no es la gran cantidad de información que reunimos, sino las redes que iluminan las que son la más reciente adición al índice de cosas de la ciencia. Eso es lo que hace que las redes sean la gran idea detrás de Big Data.

Pero, ¿qué son las redes y cómo encajan en nuestra cultura basada en datos? Una red es solo una entidad donde las conexiones entre las partes son más importantes que las partes mismas. Todos tenemos una experiencia íntima con las redes en la red de relaciones personales que se expande de usted a sus amigos y sus amigos, y así sucesivamente - la red social Facebook lo hizo de manera explícita. Pero los genes de los que depende la vida también forman una red donde la expresión de un gen depende de la actividad de otros. Las cadenas alimentarias interconectadas en ecología son redes de múltiples depredadores que se alimentan de múltiples capas de presas. La cadena de comercio mundial también es una red donde el comercio representa conexiones entre negocios y naciones.

Las redes están en todas partes en la naturaleza y la sociedad. Pero antes de que las computadoras nos concedieran el poder de recopilar, almacenar y analizar cantidades astronómicas de datos, Big Data, estábamos ciegos ante su penetración y su poder para dar forma al mundo.

El laberinto parecido a un espagueti de rutas aéreas que se encuentra en la parte posterior de su revista de a bordo le da una pista visual de por qué las redes (en este caso, la red de transporte aéreo) son difíciles de estudiar. Representan una propiedad que los científicos llaman complejidad. Cuando todo está conectado con todo lo demás, eso es complejidad, y crea problemas perversamente difíciles.

Las redes y su complejidad desafían la inclinación de la ciencia por el reduccionismo, por dividir los fenómenos en partes más pequeñas. Pero al ver las redes en términos de sus propios elementos esenciales, los científicos todavía han encontrado una manera de abrazar su holismo inherente. No importa cuán complejo sea, cada red es solo una colección de nodos (es decir, puntos) y conexiones (líneas).

El poder de esta abstracción es algo que cada habitante de la ciudad ya entiende a través de los mapas de tránsito, como los del metro de Londres. Las estaciones se convierten en puntos vinculados por líneas que representan diferentes rutas de tren. En 1931, Henry Beck desarrolló los primeros mapas abstractos de la red de metro después de muchos intentos fallidos de combinar una representación del sistema del metro con la geografía real de Londres. Beck finalmente se dio cuenta de que la geografía no les importaba a los jinetes. Al tratar de llegar desde Liverpool St. a Gloucester Rd., Solo la arquitectura de los enlaces entre las estaciones es importante.

La geografía importa menos que la "netografía". Esta es una lección fundamental para todas las redes y el primer paso para reconocerlas como una entidad nueva y distinta para que la ciencia explore.

Kevin Bacon entiende netografía. En la década de 1990, el juego "Six-Degrees of Kevin Bacon" relacionó al actor con cualquier otro jugador de Hollywood basado en las películas en las que aparecía, y enlazaba con actores en común de las películas. El juego Bacon se originó a partir de famosos experimentos tempranos con redes sociales que muestran que estás conectado con cualquier otro ciudadano de EE. UU. en solo seis enlaces.

Explicar este fenómeno de "seis grados de separación" fue una de las primeras victorias de Network Theory. Utilizando las matemáticas para representar nodos y conexiones, científicos como Steven Strogatz descubrieron cómo unos pocos atajos (como personas que se reúnen al azar en un tren) permiten que las redes se conviertan en mundos pequeños (sí, ese es un término técnico). Estos accesos directos reducen enormemente la cantidad de saltos necesarios para ir desde cualquier lugar de la red a cualquier otro lugar. En ese sentido, "es un mundo pequeño" no es solo un coloquialismo. Es una ley universal de estas "cosas" llamadas redes, así como la gravedad es una ley universal de las cosas llamada materia.

Las redes del mundo real son tan complejas, sin embargo, que los modelos matemáticos abstractos por sí solos solo van tan lejos. Aquí es donde Big Data entra en la historia, con el rápido crecimiento de Internet en la década de 1990. Con cada clic entre páginas web, cientos de millones de personas comenzaron a establecer pistas que los científicos podrían utilizar para finalmente mapear el comportamiento real de redes complejas. Al explorar estos enormes conjuntos de datos, los investigadores encontraron sorprendentes nuevas leyes sobre cómo se comportan las redes del mundo real. Una clave fue el descubrimiento de nodos superconectados que llamaron "centros". El aeropuerto O'Hare es un centro súper conectado en la red de transporte aéreo, al igual que Andy Warhol era un centro neurálgico en la red de arte de la ciudad de Nueva York.

Utilizando la primera generación de Big Data de Internet, investigadores como el físico Albert-László Barabási de Northeastern descubrieron centros que controlan el comportamiento de todas las grandes redes, desde la regulación de proteínas hasta las páginas web.

"La naturaleza evolucionó la red metabólica para las células durante más de 4 mil millones de años", dice Barabasi, "pero esa misma arquitectura surgió en la World Wide Web después de solo una década".

Diferentes redes, mismas leyes.

El encanto esencial de la ciencia siempre ha sido la oportunidad de comprender el mundo en un nivel fundamental. Para físicos como yo, esto ha significado estudiar las entidades más básicas del mundo, como las partículas subatómicas. Pero suba más en la escala de estructuras del mundo, desde moléculas a células y sociedades, y las "cosas" se vuelven más complejas y, finalmente, imposiblemente difíciles de describir de esta manera. Nadie está lo suficientemente loco como para intentar predecir la respuesta social a un terremoto al describir los átomos en sus víctimas. Reducir el todo a sus partes tiene límites. La teoría de redes ofrece un camino diferente, y eso es lo que lo hace tan emocionante.

Ver el mundo a través de la lente de la teoría de redes ofrece a los científicos una poderosa perspectiva de arriba hacia abajo. Mantiene la promesa de que podríamos encontrar leyes elegantes y matemáticas para dominios como el comportamiento del cerebro o el movimiento de la sociedad, dominios que solían estar fuera del alcance de tales descripciones. La Teoría de la Red promete ideas de un tipo que antes eran imposibles, y ya está cumpliendo esa promesa de una manera que puede ofrecer asistencia real a un mundo plagado de más de 7 mil millones de habitantes.

Es Network Science que permite a Alessandro Vespignani, uno de los investigadores que condujo el innovador estudio H1N1, cumplir con el reto de los Centros para el Control y la Prevención de Enfermedades de predecir con precisión la extensión anual de los brotes de gripe. Dichas predicciones de gripe mes a mes, imposibles en el pasado, pueden permitirle a los CDC un mejor tiempo de producción y distribución de vacunas. El politólogo David Lazer de Harvard está utilizando ideas similares para desarrollar herramientas que supervisen el comportamiento de las redes de telefonía celular tras las emergencias como el atentado de Boston Marathon. Al observar cómo se ilumina la red durante un desastre, es posible atravesar la niebla de la confusión e identificar exactamente dónde deben responder los primeros en responder a sus recursos. El rápido desarrollo de la comprensión de las redes también ha permitido a biólogos como Neo Martinez en la Universidad de Arizona, mapear la respuesta de todo un ecosistema al colapso de una sola especie. Los resultados de Martínez tienen la promesa de manejar con precisión las pesquerías frente al cambio climático y el agotamiento de los recursos con una agudeza que puede poner orden a su complejidad perversa.

Como científico, es imposible ignorar la perspectiva verdaderamente revolucionaria. La Teoría de la Red se abre no solo al mundo natural (el dominio tradicional de los físicos) sino también al mundo que hemos creado: el orden social y las tecnologías de las que depende. Pero como ciudadano, estoy profundamente preocupado por las implicaciones más oscuras inherentes a los recursos de Big Data en los que se basa esta nueva ciencia. Estamos obteniendo herramientas que pueden hacer que el mundo no solo sea menos humano, sino menos humano.

Sin embargo, equilibrar tales dualidades en una revolución científica no es nuevo. A finales del siglo XX, no sabíamos nada de los átomos o sus componentes. Penetrar en el mundo atómico nos llevó a las maravillas electrónicas diarias que ahora damos por sentadas. También nos permitió construir armas nucleares de inconcebible poder destructivo cuyo legado todavía nos persigue.

La teoría de la red es quizás la primera ciencia verdadera y universal que emerge de nuestra revolución digital. Nos ha dado una forma fundamentalmente nueva de comprender cómo se construye el mundo. Nos está mostrando que toda la vida existe en y a través de redes, cuya red de conexiones parpadea, parpadea y pulsa con energía e información.

A medida que se expanda ese conocimiento y se entiendan sus implicaciones, el miedo debe equilibrarse con una discusión informada.

martes, 21 de julio de 2015

Redes de lenguaje en redes sociales

Cuando más grande no es mejor
Por R.L.G. | Berlin - The Economist


¿Cómo calificaría usted a las lenguas "importantes"? Si se le pregunta los ordene, muchas personas comienzan con Inglés, pero después de eso son reacios a ir más allá. Cuán importante, se preguntan. Un enfoque sería mirar a la gente y el dinero: sin duda una lengua es importante si se habla de un montón de gente, en los países con gran riqueza (y es de suponer, por lo tanto, poder).

Pero en diciembre llegó un nuevo enfoque. Un grupo de estudiosos * acercó a la tarea por primera mirando cómo las lenguas se conectan entre sí, en lugar de verlas de forma aislada. Entonces decidieron ver si esto era un buen predictor de la cantidad de gente famosa hablaban una lengua dada. Si una lengua está bien conectado con los demás (un lenguaje de "hub" con muchos bilingües), sus hablantes tienden a ser famosa. Y los nombres de los idiomas conectados resultan ser bastante interesante.

Para encontrar vínculos entre las lenguas, los investigadores crearon una "red global de lenguaje" (GLN) de tres maneras diferentes (véase el gráfico). Uno era editores de Wikipedia: un wikipedista bilingüe que edita artículos en árabe y en Inglés que cuenta como el fortalecimiento de los lazos entre el árabe y el Inglés. El segundo era Twitter: usuarios que habían twitteado al menos seis frases completas en un segundo idioma se trataron como fortalecer el vínculo entre esos dos idiomas. El tercero era un, más formal métrica antigua: traducción libro. La UNESCO, la organización cultural de las Naciones Unidas, mantiene una base de datos de libros traducidos, y cada uno de los 2,2 millones de traducciones se contó como un bono fortalecimiento de los dos idiomas. (Estos bonos, por supuesto, son asimétricos: algunas lenguas tienen más libros traducidos de ellos que a ellos y viceversa.)




Las redes resultantes son notables en muchos aspectos. Inglés es fundamental para todos ellos. Pero con muchos otros idiomas, su conectividad tiene poco que ver con el poder moderno de su país de origen. Tome la red implica libro-traducción. Los datos provienen de 1979-2011, por lo que Rusia es un nodo importante en la red. No sólo se tradujeron libros entre ruso y otros idiomas de la antigua Unión Soviética (Armenia, kirguís y el letón, dicen), pero el ruso se conecta de manera significativa a las lenguas del sur y el sudeste de Asia y el Medio Oriente. El contraste con Wikipedia y Twitter, que sesgar mucho más moderno, es sorprendente: ruso repente se convierte en un nodo periférico.

China, también, es periférica en las redes de los autores. En la red de libro-traducción, el idioma más hablado del mundo está aislado, conectado principalmente a otras lenguas chinas más unos pocos en el sudeste de Asia, en particular vietnamitas. Esto puede tener sentido dado el marco temporal de la base de datos de libros de traducción, sesgado a décadas antes espectacular ascenso de China. Pero China también es un jugador poco en Twitter, como resultado de la popularidad de Sina Weibo, un servicio similar a Twitter competir, en China. Lo mismo puede decirse de la Wikipedia: aquí china está mejor conectado un poco, pero todavía es mucho menor que su tamaño o el PIB podría predecir, posiblemente gracias a la existencia de una Wikipedia-como Baidu Baike enciclopedia colaborativa.

La conclusión es clara: las grandes lenguas no son necesariamente global, y viceversa. El árabe y el hindi-dos otros idiomas con cientos de millones de hablantes son los periféricos como el chino y el ruso. Los grandes nodos en las redes, además de Inglés son predecibles: francés, español y alemán, sobre todo. Los dos primeros fueron arrojados con éxito a lo largo y ancho por el colonialismo. Alemán tiene siglos de prestigio en la ciencia, la filosofía y la literatura, a pesar de los fracasos de los esfuerzos coloniales de Alemania.

Sin embargo, estos resultados deben ser manejados con cuidado, señalan los autores. El documento no dice nada acerca de las cualidades inherentes de cualquier lengua, o la astucia de sus hablantes. César Hidalgo, uno de los autores, señala que el artículo es realmente acerca de las élites. Los bilingües con tiempo para editar la Wikipedia no son personas normales, ni son los traductores de libros (o incluso los usuarios bilingües de Twitter). Pero lo hacen jugar un papel desmesurado en la transmisión de la cultura a través de fronteras. El principal hallazgo del estudio es que las personas son más propensos a convertirse en mundialmente famosa (medida, en parte, en las personas con las entradas de Wikipedia en al menos 25 idiomas) si hablan uno de los idiomas más en red. Persona más brillante del mundo puede ser un representante de la etnia hmong o náhuatl, pero el camino a la fama conduce a través de otros idiomas.

Hay una naturaleza "¿qué más se puede esperar?" Para el papel descomunal de las lenguas occidentales en tres productos occidentales nacido: la industria del libro-publicación masiva, Wikipedia y Twitter. Pero los resultados siguen siendo significativa: Twitter es de importancia mundial realmente (sólo pide a los mulás iraníes o el ex presidente de Túnez). Sina Weibo y VK (de Rusia Facebook) no lo son. Su naturaleza hecha en casa puede ser un motivo de orgullo, sin duda mantiene censores feliz, pero también significa reducir la influencia cultural de un país.

Para el estudiante de idiomas, la naturaleza en red de las lenguas plantea un dilema interesante: en caso de que aprender un lenguaje popular entre las élites globales? La tradición de aprendizaje del francés todavía se ve como una buena apuesta aquí. ¿O hay que aprender un idioma cuyo número de bilingües trotamundos es pequeño en relación a su importancia? La oferta y la demanda dice que esto será valioso. Este es el caso real para aprender chino: no porque es el idioma mundial en aumento, pero debido a que no-es-al menos por cierto todavía no. Dada enorme papel de China en la economía mundial, el número de extranjeros con fluidez en chino es todavía demasiado pocos.

"Links que hablan: La red de idioma global y su asociación con la fama mundial," por Shahar Ronen, Bruno Gonçalves, Kevin Z. Hu, Allesandro Vespignani, Steven Pinker y César Hidalgo, Actas de la Academia Nacional de Ciencias, diciembre 2014