Mostrando entradas con la etiqueta Excel. Mostrar todas las entradas
Mostrando entradas con la etiqueta Excel. 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.

jueves, 9 de junio de 2016

Importando datos de Excel a Gephi

Datos de Excel y laboratorio de datos de Gephi
Bowdoin DCSI



Mi objetivo para esta entrada de blog es explicar la forma de organizar los datos en una hoja de cálculo de Excel (que se guarda como un archivo de valores separados por comas o CSV) para importar en Gephi para la visualización y análisis de nodos (elementos individuales representados como puntos) y bordes (relaciones representadas por las líneas conectivo) en una red. Mi explicación asume la familiaridad con los tutoriales basados ​​en archivos Gephi .gexf preparados (la extensión de los archivos legibles por Gephi) de los datos de Les Miserables o Facebook. Asumo que mi lector está pensando ahora en la aplicación de análisis de redes para su propia investigación.

Los nuevos usuarios de Gephi pueden no tener ninguna familiaridad con los archivos XML, .gexf mark-up, o cualquier otro código para organizar los datos, pero todavía pueden encontrar uso en Gephi. Excel es típicamente una aplicación más fácil de usar para este tipo de organización, y la mayoría de las bases de datos de Microsoft Access (por ejemplo) se puede convertir en un libro de Excel (.xls) o directamente a un archivo .csv. Las explicaciones se parte de una comprensión básica de almacenamiento, la copia y la ordenación de datos en Excel. Los principios de organización se describen a continuación se pueden aplicar a cualquier aplicación que utilice para generar la tabla .csv archivos que va a utilizar en Gephi. Otros formatos compatibles y su funcionalidad se pueden encontrar en el sitio de Gephi.

Estoy utilizando las capturas de mis propios datos de investigación sobre los libros en la biblioteca de Galileo Galilei para ayudar a demostrar los tipos de información cada columna debe contener. A continuación se muestra una captura de pantalla de una hoja de cálculo en el libro de Excel que he utilizado para organizar todas mis notas relacionadas con el proyecto:



Hay muchas hojas de cálculo que figuran en la barra de pestañas en la parte inferior de la pantalla para los diferentes tipos de información que tengo para el proyecto. Es importante destacar que un archivo .csv sólo conserva la información en la hoja de cálculo activa ( "Por autor" en este caso, la pestaña en blanco) y no va a salvar las otras hojas. Es importante copiar la información que desea utilizar en su libro principal (múltiples hojas) a un libro de una sola hoja de cálculo para los nodos y un libro de trabajo de una sola hoja de cálculo para bordes. Además, los títulos de las columnas en mi libro ( "Mi #", "# de Fav", "Autor. La cita de Favaro completa", "Año", etc.) son mi taquigrafía y no pueden ser interpretados por Gephi, otra razón por la que la copia de la información que desea utilizar para nuevos archivos de libro de una sola hoja de cálculo es muy recomendable.

  1. Usted tendrá que crear dos archivos .csv: una tabla de nodos y una tabla de borde. Yo uso Excel como mi solicitud de tabla, archivos de Excel y guardar por defecto para el formato .xlsx. Con el fin de obtener el .csv, tiene que elegir esa opción para el formato de archivo al guardar.
  2. La tabla de nodos dice Gephi todos los posibles nodos en una red y debe tener al menos las columnas ID y la etiqueta. Debe haber una línea por cada nodo que aparecerá en cualquier columna de la tabla irregular:
Esto parece bastante fácil, pero ¿qué tipo de información se encuentra en mejor posición en la columna Id, y cómo debe diferir de que la etiqueta? El ejemplo anterior es tomado de una hoja de cálculo que utilizo para organizar la información sobre la biblioteca de Galileo. Todos mis nodos en este ejemplo son los nombres propios que se encuentran en los títulos de la biblioteca y de los propios títulos (alrededor de 2.650 nodos en total). El ejemplo anterior es, en una palabra, torpe. Es redundante y, finalmente, hace que mi visualización de la red ilegible si trato de añadir etiquetas en los nodos. Considere el siguiente ejemplo en el que los títulos completos se convertirían en las etiquetas de más de aproximadamente 650 nodos (nodos y bordes oscureciendo en el proceso):



Tener un número de identificación único (ID que Gephi espera) me permite almacenar una gran cantidad de información acerca de ese nodo en una hoja de cálculo o base de datos que después puedo elegir acceder cuando sea necesario. Ya que mi sistema de organización se creó mucho antes de saber acerca Gephi, mi columna de etiqueta corresponde a la columna Título en mi hoja de cálculo (que en última instancia estorba mi visualización hasta el punto de ilegibilidad si agrego etiquetas). Para que esto sea más fácil de leer, tengo que cambiar los datos en la columna Etiqueta de los datos de una columna “Short Title".

3) Como se puede observar, hay otras columnas en la primera captura de pantalla de la tabla de nodos. La tabla de nodos también puede incluir atributos (en paréntesis en el ejemplo, ya que no son necesarios para una visualización básica de una red). Los atributos son una forma de clasificar los datos, tal vez por género, raza, edad, etc. Aunque no es necesario para explorar los datos con Gephi, que permiten una exploración más matizada de una red. Por ejemplo, voy a querer añadir columnas de atributos de la afiliación religiosa (Jesuita, Benedictino, protestante, católica, etc.) y el género para iniciar la visualización de los datos de una manera que me ayuda a responder a mis preguntas de investigación. Columnas de atributos también se pueden añadir en la sección "Laboratorio de Datos" de la interfaz Gephi incluso después de haber cargado los archivos .csv para los nodos y los bordes.

4) El intervalo de tiempo es otra columna opcional de información para incluir alrededor de sus datos, los cuales pueden o no ser aplicables o útil. Copio aquí una captura de pantalla parcial de la página Gephi.org como referencia:



El wiki Gephi también muestra el código detrás de este proceso.

Pensando en mi propio conjunto de datos, necesito una columna de intervalo de tiempo para cada título que muestra el año más temprano que un libro podría haber entrado en la biblioteca. Voy a dejar mis intervalos de tiempo con la muerte de Galileo en 1642. A partir de los ejemplos en la parte 3, el tiempo de intervalo de información se vería así en la versión .csv de la hoja de cálculo, con las columnas ID, hora de inicio, hora de finalización:

4,1640,1642

5,1628,1642

6,1637,1642

Una vez que haya subido el csv, en el Laboratorio de Datos, puede combinar las columnas de la hora de inicio y fin utilizando la estrategia de combinación "Crear Intervalo de tiempo." Esto va a concatenar y formato de lo que necesita con el fin de ser capaz de ver el cambio a lo largo tiempo de la red.

5) La tabla de enlaces (el segundo archivo .csv que necesita para crear) le dice a Gephi las conexiones que existen entre los nodos. Debe tener la columnas Source y Target:


Aquí es donde tener un identificador único para todos los nodos puede ser muy conveniente. Mi fuente de arriba es el título 299 en el que la Academia de Colonia se menciona como un contribuyente al libro que yo he dado a los títulos de libros identificador 299. puede incluir a personas o lugares (objetivos), pero las personas o lugares no puede incluir títulos (Fuentes), por lo mis bordes se dirigen, y la distinción entre los nodos de origen y los nodos de destino es crítica.

6) De manera similar a la tabla de nodos, hay muchas categorías opcionales que pueden añadir matices a un análisis de una red. La tabla irregular también puede incluir una columna Etiqueta para ayudar con la clasificación de los tipos de relaciones, un identificador único para la relación (generada por Gephi), atributos (por ejemplo: la familia, amigo, compañero de trabajo, compañero de clase, etc., para las redes sociales), e intervalo de tiempo.

7) La tabla irregular también puede incluir información que no se encuentra en la tabla de nodos. Tipo indica si la relación es dirigido o no dirigido. Esta columna puede ser auto-llenado de carga y es visible en el Laboratorio de Datos.

8) Otra opción para la tabla de borde es proporcionar weightedness para la relación. De peso es su oportunidad de dar más importancia a ciertas relaciones, dándoles un peso numérico.

No olvide guardar los archivos como .csv, luego cargarlos en Gephi, los nodos en primer lugar, mediante la opción "Importar CSV" en la barra de herramientas del Laboratorio de Datos. Asegúrese de indicar el tipo de archivo que está subiendo (tabla de nodos o tabla irregular), de lo contrario corre el riesgo de mensajes de error.

Los datos pueden ser simplemente la entrada directamente en el Laboratorio de Datos de Gephi, pero estoy más familiarizado con la funcionalidad de Excel, se han organizado mis datos de investigación utilizando hojas de cálculo, y prefieren hacer ajustes, filtrar los datos, y guardar mi información en un solo formato. Los lenguajes de programación tales como R parecen particularmente adeptos a crear la información tabular necesita aquí, sobre todo cuando se tira de forma automática datos de un gran corpus.

Mi enfoque puede no funcionar para todos o cada proyecto, pero es de esperar ver los datos reales en un formato crudo proporciona un contexto para su presentación en el laboratorio de datos:




A su vez, esto debería hacer el análisis de algo tan complejo como la visualización de las conexiones entre los nombres en la biblioteca de Galileo menos opaco: