Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia

bbc Equation Chapter 1 Section 1 Trabajo Fin de Máster Máster en Organización Industrial y Gestión Empresarial Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Autora: Laura Calzada Infante Tutor: Sebastián Lozano Segura Dep. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 201 6 iii Trabajo Fin de Máster Máster en Organización Industrial y Gestión de Empresas Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Autora: Laura Calzada Infante Tutor: Sebastián Lozano Segura Dep. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2016 v Trabajo Fin de Máster: Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Autora: Laura Calzada Infante Tutor: Sebastián Lozano Segura El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2016 El Secretario del Tribunal A mi familia Agradecimientos En primer lugar me gustaría agradecer a mi tutor de Trabajo Fin de Máster, Sebastián Lozano, por toda su ayuda, comprensión y paciencia. Desde el momento en que le conocí, no ha dejado de sorprenderme y de romperme todos los esquemas, con un despliegue de asertividad, eficiencia y entusiasmo envidiable, ayudándome a ampliar mi visión de la vida y de la profesión. Quisiera dar también las gracias a Adenso, por su paciencia y por darme la oportunidad de adentrarme en el mundo de la organización y la eficiencia. La vida está llena de sorpresas y nunca sabes dónde te puede llevar. Quisiera dar las gracias a Santiago, por sus enseñanzas, sus consejos, su atención y su amistad, no hay día que no me acuerde de nuestras charlas y espero se produzcan muchas más. Quisiera dar las gracias a mi familia, por estar siempre tan cerca. Gracias a vuestro apoyo y consejos. No hay día que no os dedique una sonrisa. Gracias a Fernando, por su apoyo y comprensión infinita. Sin ti, no hubiera llegado tan lejos. Gracias por cambiarme el prisma. Y por último y no menos importante gracias a mis amigos por apoyarme, por los buenos y malos momentos que hemos pasado y por los que están por llegar. Gracias por enseñarme tanto. Laura Calzada Infante Sevilla, 2016 1 Í NDICE DE F IGURAS Figura 2.1. Esquema de una DMU 1 Figura 2.2. Tecnología FDH en un modelo con una entrada y una salida 4 Figura 2.3. Tecnología VRS y CRS en un modelo con una entrada y una salida 5 Figura 2.4 Modelo CCR-Input con una entrada y una salida 8 Figura 2.5: Modelo CCR-Input con dos entradas y una salida 8 Figura 2.6 Modelo CCR-Output con una entrada y una salida 11 Figura 2.7 Modelo CCR-Output con una entrada y dos salidas 11 Figura 2.8 Modelo BCC-Input para el caso de una entrada y una salida 12 Figura 2.9 Comparación del modelo CCR-Input y el modelo BCC-Input 13 Figura 2.10: Modelo FDH con orientación de entrada en el caso de un modelo con dos entradas y una salida15 Figura 2.11 Modelo Aditivo con tecnología VRS, caso de 2 entradas y 1 salida 19 Figura 2.12: Visualización de los pasos intermedios generados por los modelos TEIP y SEIP en un caso con 6 DMUs con una entrada y una salida 21 Figura 2.13 Identificación de los diferentes niveles de frontera eficiente en un conjunto de datos con dos entradas y una salida constante. 23 Figura 2.14: Objetivos reales propuestos para la DMU L que le permiten llegar a la frontera eficiente. 25 Figura 2.15: Caminos posibles que puede tomar L hasta la frontera eficiente, en el juego de datos de los supermercados 25 Figura 3.1: Tipos principales de redes complejas y sus transformaciones 28 Figura 3.2 Generación de redes de mundos pequeños 35 Figura 3.3: Representación de la variación de la media de la longitud geodésica y el clustering en función de la probabilidad p 35 Figura 4.1 Distribución del PageRank de forma simplificada 43 Figura 5.1 Visualización de la red de dominancia del juego de datos de CST 50 Figura 5.2 Subgrafo de esqueleto en la red CST 50 Figura 5.3 Distribución de las distancias máximas a la frontera eficiente del caso CST 51 Figura 5.4 Distribución de los enlaces del caso CST 51 Figura 5.5 Visualización del grado de entrada y de salida en función de las capas en el caso CST 52 Figura 5.6 Visualización de la red de dominancia en el caso Lim 54 Figura 5.7 Distribución de las distancias máximas a la frontera eficiente en el caso Lim 55 Figura 5.8 Subgrafo de esqueleto en el caso Lim 55 Figura 5.9 Distribución de los enlaces en el caso Lim 56 Índice de Figuras 2 Figura 5.10 Visualización del grado de entrada y de salida en función de las capas en el caso Lim 57 Figura 5.11 Visualización de la red de dominancia del juego de datos de Park 59 Figura 5.12 Subgrafo de esqueleto en el caso Park 59 Figura 5.13 Distribución de las distancias máximas a la frontera eficiente en el caso Park 60 Figura 5.14 Distribución de los enlaces en el caso Park 60 Figura 5.15 Visualización del grado de entrada y de salida en función de las capas en el caso Park 61 1 1 O BJETIVO l Análisis de Redes Complejas ha tenido una gran aplicación en diferentes ciencias. Se basa en la caracterización de un sistema, entendiendo como sistema, a una serie de entes, llamados nodos, que está relacionados entre sí por enlaces y que simbolizan la interacción existente entre dichos nodos. La caracterización, permite comprender como funciona la agrupación, analizar su estructura para determinar cuáles son los elementos más determinantes en una red, cuáles son los principios que permiten a una red crecer hasta convertirse en una red robusta y eficiente e incluso predecir cuál será el futuro de ese sistema. Por otro lado, la metodología de Análisis por Envoltura de Datos, permite comparar una serie de unidades, con el fin de determinar la eficiencia relativa entre dichas unidades, considerando como eficiencia el cociente entre producción y recursos. Los múltiples modelos de programación lineal que se han desarrollado permiten comparar todas las unidades entre sí, determinar cuáles son las unidades no eficientes y cuáles son sus objetivos a seguir teniendo en cuenta su tamaño. El Análisis por Envoltura de Datos es una herramienta muy utilizada; sin embargo, es compleja la visualización de sus resultados cuando se analizan múltiples entradas y/o salidas. Por ello, el objetivo de este trabajo es utilizar las herramientas de caracterización y visualización del Análisis de Redes Complejas, para estudiar estos resultados. Para ello se establecerán como nodos las unidades analizadas, y los enlaces partirán de aquellas unidades que no son eficientes y señalaran a las que son de su mismo tamaño y las dominan por ser más eficientes que ellas. Gracias a estas relaciones de dominancia se obtendrá una red dirigida, debido a que los enlaces o arcos tienen una dirección. En el capítulo 2 se explicarán todos los conceptos necesarios del Análisis por Envoltura de Datos y en el capítulo 3 los del Análisis de Redes Complejas para poder desarrollar la metodología planteada en el capítulo 4. Finalmente en el capítulo 5 se aplicará la metodología a varios juegos de datos, tras la cual se desarrollarán las conclusiones del presente trabajo. E “Una imagen vale más que mil palabras” Proverbio chino 1 2 A NÁLISIS P OR E NVOLTURA D E D ATOS n este apartado se pretende explicar los principales conceptos de la metodología conocida como Envoltura de Análisis de Datos, (Data Envelopement Analysis, DEA). Con el fin de desarrollar la base que será necesaria para comprender la técnica que se desarrollará en este trabajo. El Análisis de Envoltura de datos tiene como objetivo determinar la eficiencia relativa de las unidades que se están estudiando. Este estudio permitiría analizar cuáles son aquellas unidades que realizan una mejor gestión de sus recursos, y que por ello, se consideran modelos a seguir por las unidades de la muestra que poseen un tamaño similar. El origen de esta herramienta no paramétrica se remonta a 1978, donde Charnes, Cooper y Rhodes publicaron (Charnes et al. 1978), basándose en el concepto de eficiencia desarrollado por Farrell en 1957. El fin de su investigación era analizar la eficiencia del programa de educación “Follow Through” en escuelas públicas de Estados Unidos. Farrell planteaba en (Farrell 1957) como se podría aumentar la producción de una empresa, haciéndola más eficiente sin tener que aumentar sus recursos. Desarrolló un método que medía la eficiencia técnica de una empresa comparándola con otra hipotética que usaba la misma proporción de recursos y que había sido generada a partir de la media ponderada de otras dos empresas existentes. 2.1 Conceptos fundamentales La técnica DEA se puede aplicar a cualquier unidad que realice un proceso productivo que consuma unos recursos (inputs o entradas) y obtenga unos resultados (outputs o salidas). Estas unidades homogéneas se denominan Unidades de Decisión (Decision Making Units, DMUs), debido a que cada unidad decide cómo gestionar sus recursos y es responsable de su productividad, al ser capaz de modificar su proceso productivo. Figura 2.1. Esquema de una DMU E Las personas debemos el progreso a los insatisfechos. -Aldous Huxley - Análisis Por Envoltura De Datos 2 Como consecuencia de la amplia variedad de factores que afectan a un sistema productivo, se deben analizar cuáles son las salidas que se pretenden medir y cuáles son las entradas que serían determinantes en el proceso productivo y que afectan directamente a esas salidas. A continuación se muestran las principales variables que se tienen en cuenta en un modelo DEA: o n observaciones o DMUs con j=1,..,n, con m entradas y s salidas cada una. o x ij : Entrada i consumida por la unidad j con i=1,..,m Siendo X la matriz de entradas de dimensiones nxm o y kj : Salida k correspondiente a la unidad j con k=1,..,s Siendo Y la matriz de salidas de dimensiones nxs Para poder ejecutar un modelo DEA, la relación que debe existir entre el número de DMUs y el número de entradas y salidas que se analizan es:  > 3 (  +  ) (2.1) 2.1.1 Productividad y Eficiencia Según (Farrell 1957) se entiende como productividad la relación entre los resultados obtenidos y los recursos consumidos en el proceso productivo. De forma matemática se expresaría como el ratio entre las unidades producidas y las unidades consumidas.  =    =   =   (2.2) Esta expresión representa la eficiencia absoluta, dado que muestra la proporción de recursos necesarios teniendo en cuenta únicamente los datos del proceso productivo de la unidad que se está analizando. Sin embargo, una vez escogido los principales factores que representarían los resultados y los recursos de los procesos productivos, para poder agregar los resultados por una parte y los recursos por otro, se les debe asignar un peso a cada uno, que represente su importancia y permita que el ratio sea adimensional. Siendo   y   los pesos correspondientes a cada entrada y salida respectivamente. La agregación de las entradas y las salidas de la unidad j se expresaría de la siguiente forma. Entradas = &   '  ( ) * + (2.4)  = &   ,  -  * + (2.5) Sin embargo, resulta interesante disponer de un índice que permita evaluar la productividad de una unidad respecto de las demás unidades semejantes. Por ello surgió el concepto de eficiencia relativa, donde se toma como referencia una unidad homogénea. En este documento siempre que se hable de eficiencia, se referirá a la eficiencia relativa.     =      . (2.6)  =  /    /   (2.3) 3 3 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Dependiendo de qué unidad se tome como referencia se referirá a diferentes tipos de eficiencia relativa: o Si se toma como referencia la unidad con la máxima eficiencia absoluta, se utiliza el concepto de eficiencia global. o Se habla de eficiencia técnica si se considera como referencia la unidad de tamaño similar con la mayor eficiencia absoluta. Se dicen de dos unidades de tamaño similar cuando ambas tienen el mismo orden de magnitud. o Se habla de eficiencia de escala cuando se evalúa el ratio entre la eficiencia global y la eficiencia técnica de una determinada unidad. Hay que tener en cuenta que la eficiencia relativa depende de la orientación. Se considera orientación de entrada, cuando el objetivo de la unidad que se está analizando es disminuir el número de recursos empleados, sin disminuir la producción y se habla de orientación de salida si pretende aumentar los resultados del proceso productivo sin variar los recursos que emplea en él. Por lo tanto cuando se analice la eficiencia técnica, si se obtiene un ratio de 1, se considera que la unidad es eficiente y por ello formará parte de la frontera eficiente, que se compone de las unidades más eficientes de la muestra analizada. Las unidades que no tengan un radio 1, siempre serán inferiores a la unidad y se denominan unidades no eficientes. En el caso de la eficiencia de escala, si la unidad analizada tiene un ratio 1, entonces coincide la eficiencia global con la eficiencia técnica. Por lo que, dicha unidad tiene el tamaño de escala más productivo (Most Productive Scale Size, MPSS) Gracias a que la unidad de referencia va a ser siempre una unidad eficiente, el ratio de eficiencia absoluta será igual a la unidad. Por lo que la expresión de eficiencia se expresa finalmente de la siguiente forma:    = ∑   ,  -  * + ∑   '  1  * + (2.7) 2.1.2 Tecnología El concepto de tecnología hace referencia al conjunto de procesos productivos tecnológicamente factibles que se evalúan en el modelo DEA. Existen cuatro hipótesis que permiten definir la tecnología: 1. Envoltura: Las observaciones pertenecen al conjunto de posibilidades de producción (T) { ( '  , ,  ) ∈ 5 } (2.8) 2. Free disposability o libre disponibilidad: Libre para desechar o derrochar. Se considera que una unidad puede usar más recursos de los que en verdad necesita y que puede producir menos de lo que puede llegar a producir. { ( ' , , ) ∈ 5 ∀ ' ≥ ' , , ≤ , } (2.9) 3. Hipótesis de convexidad: Considera que es factible cualquier combinación convexa de las unidades existentes.  ( ' + , , + ) ∈ 5 & ( ' ; , , ; ) ∈ 5 → = ( ' + , , + ) + ( 1 − = ) ( ' ; , , ; ) ∈ 5 (2.10) 4. Escalabilidad: Se puede escalar cualquier proceso productivo perteneciente al conjunto de posibilidades de producción.  ( ' + , , + ) ∈ 5 & ( ' ; , , ; ) ∈ 5 → ( =' , =, ) ∈ 5 ∀ = ≥ 0 (2.11) Existen tres tipos de tecnología FDH (Free Disposability Hull), VRS (Variable Return to Scale) y CRS (Constante Return to Scale) y cada una cumple una serie de hipótesis. o La tecnología FDH cumple las hipótesis de envoltura y libre disponibilidad Análisis Por Envoltura De Datos 4 o La tecnología VRS cumple las hipótesis de convexidad, envoltura y libre disponibilidad o La tecnología CRS cumple las hipótesis de escalabilidad, convexidad, envoltura y libre disponibilidad. La tecnología FDH cumple las propiedades de envoltura y de libre disponibilidad, es decir, está compuesta por las unidades observadas más todos aquellos procesos productivos que consumen más recursos que los existentes o consiguen niveles de producción inferiores. Se define de con la siguiente expresión. 5 ABC = D ( ' E , , E ) : ∃ = E ≥ 0 , & =  = 1 ; I  * + = E J ≤ ' K K K E ; = E L ≥ , E ; =  ∈ { 0 , 1 } M (2.12) Las unidades únicamente se pueden proyectar sobre una DMU existente, debido a que la variable = es binaria y el sumatorio debe ser 1. En la Figura 2.2 que se muestra a continuación, se aprecia la proyección de una DMU ineficiente sobre una DMU que forma parte de la frontera eficiente. Cabe destacar que los segmentos que unen las DMUs eficientes, no forman parte de la frontera eficiente. Figura 2.2. Tecnología FDH en un modelo con una entrada y una salida Fuente: (Fernández 2015) La tecnología VRS permite la combinación convexa de las unidades existentes, como se puede visualizar en la Figura 2.3. Por lo tanto todas las unidades factibles se encuentran por debajo de la línea continua. La frontera eficiente en esta compuesta por las unidades eficientes y los segmentos que las unen, sin embargo los tramos paralelos a los ejes únicamente forman parte de la frontera de producción admisible. En esta tecnología se puede apreciar tres tipos de rendimiento de escala diferentes: o Retornos de escala crecientes (Increasing Return Scale, IRS): se aprecia cuando el incremento porcentual de outputs es mucho mayor que el incremento porcentual de los inputs. En la Figura 2.3 se correspondería con el tramo AB. o Retornos de escala constantes (Constant Return Scale, CRS): el incremento porcentual de outputs es igual al incremento porcentual de inputs. Las unidades que se encuentran en este tramo de la frontera poseen el tamaño de escala más productivo (MPSS). En la Figura 2.3 se correspondería con los tramos BC y CD. o Retornos de escala decrecientes (Decreasing Return Scale, DRS): el incremento porcentual de outputs es mucho menor que el incremento porcentual de los inputs. 5 5 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Figura 2.3. Tecnología VRS y CRS en un modelo con una entrada y una salida Fuente: (Fernández 2015) La tecnología VRS, se expresa matemáticamente con la siguiente expresión: 5 NOP = D ( ' E , , E ) : ∃ = E ≥ 0 , & =  = 1 ; I  * + = E J ≤ ' K K K E ; = E L ≥ , E M (2.13) En la frontera eficiente de la tecnología CRS, se encuentran las unidades con la máxima productividad posible al utilizarse como referencia la eficiencia global máxima de las DMUs existentes. Esta frontera eficiente aparece representada con una línea discontinua en la Figura 2.3. La expresión matemática que define la tecnología CRS es: 5 QOP = { ( ' E , , E ) : ∃ = E ≥ 0 , = E J ≤ ' K K K E ; = E L ≥ , E } (2.14) 2.2 Modelos Existen múltiples modelos DEA dependiendo de qué aspectos se pretenden enfatizar, debido a que depende de ello la eficiencia relativa. 2.2.1 Modelos de Retornos de Escala Constante A continuación se presentan los modelos básicos en los que se considera como tecnología admisible, la tecnología CRS. Por lo que se consideran factibles como unidades de referencias, la unidad con mayor productividad escalada. Los modelos que se presentan son: Modelo Ratio, Modelo CCR-Input y Modelo CCR-Output, desarrollados por (Charnes et al. 1978) 2.2.1.1 Modelo Ratio Calcula la eficiencia relativa de cada unidad al compararla con el resto de las unidades que forman parte de la tecnología. Parte de la definición de eficiencia relativa, debido a su objetivo es maximizar la eficiencia absoluta de la unidad que se está analizando (J). Este objetivo equivale a maximizar la eficiencia relativa de la unidad J, porque al tomar como referencia la unidad más eficiente el denominador será constante e igual a la unidad. ' ∑  R , R -  * + ∑  R ' R 1  * + (2.15) Análisis Por Envoltura De Datos 12 De esta forma cada unidad virtual eficiente se situará entre dos unidades eficientes observadas, donde =  indicará el % de similitud que tiene con cada una de ellas. A continuación se expresa el Modelo BCC-Input en forma envolvente, se aprecia que es similar al Modelo CCRInput, salvo por el hecho de que la frontera es convexa. XY Z R − V [ & ℎ  ] - *+ + & ℎ  ^ 1 *+ _ .. &=  '  =Z R ' R −ℎ ^ I *+ =1,2,.., &=  ,  =, R +ℎ  ] I *+ W=1,2,.., &=  =1 I *+ =  ≥0 ∀T; ℎ ^ ,ℎ  ] ≥0 ∀,W Z R  (2.27) A continuación en la Figura 2.8 se muestra la solución de un caso en el que se analizan las unidades productivas con una entrada y una salida. Figura 2.8 Modelo BCC-Input para el caso de una entrada y una salida Fuente: (Villa 2003) Como se puede apreciar la frontera eficiente está compuesta por tres tramos entre las unidades A y D. Al igual que en el caso de los modelos de retornos de escala constante las unidades eficientes se proyectan sobre sí mismas, por lo que las únicas proyecciones que se aprecian se corresponden a las de las unidades ineficientes. Las unidades F y G, no tienen holgura porque se proyectan directamente sobre la frontera eficiente, este no es el caso de la unidad E, debido a que se proyecta sobre la frontera admisible. Si comparamos las diferentes soluciones que se obtienen a la hora de aplicar dos modelos diferentes con la 13 13 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia misma orientación, uno con retorno de escala constante y el otro con retorno de escala variable. Se aprecia como en el CCR-Input tiene menos unidades eficientes que el modelo BCC-Input, como se puede apreciar en la Figura 2.9. Figura 2.9 Comparación del modelo CCR-Input y el modelo BCC-Input Fuente: (Villa 2003) Por otra parte la eficiencia calculada en el modelo BCC-Input será superior a la del modelo CCR-Input, debido a que la frontera eficiente en este último se encuentra más alejado de las unidades ineficientes, al compararse con las unidades de mayor productividad del problema. Muchas unidades que son eficientes, ya sean virtuales u observadas del modelo BCC-Input serían ineficientes para el modelo CCR-Inputs, siempre que no se encontraran dichas unidades en la parte de la frontera con el tamaño de escala más productivo (MPSS), línea BC. Las unidades que se encuentran en la zona AB, se encuentran en la zona con retorno de escala creciente (Increasing Return Scale, IRS) son unidades eficientes para las unidades de tamaño similar; sin embargo deberían incrementar sus inputs si quieren alcanzar el tamaño de mayor productividad del problema. Lo mismo ocurre con las unidades de la zona CD, son unidades eficientes cuando se compararan con unidades de tamaño similar pero si quieren alcanzar el tamaño de mayor productividad observada en el problema deberían reducir sus recursos, estas unidades operan con retornos de escala decrecientes (Decreasing Return Scale, DRS) 2.2.2.2 Modelo BCC-OUTPUT De forma análoga al modelo BCC-Input se construye el modelo de Retorno de Escala Variable con orientación de salida, partiendo del modelo CCR-Output. La expresión del modelo BCC-Output en forma envolvente es: X'Y c R + V [ & ℎ  ] - *+ + & ℎ  ^ 1 *+ _ .. &=  '  =' R −ℎ ^ I *+ =1,2,.., & =  ,  = c R , R + ℎ  ] I  * + W = 1 , 2 , . . ,  (2.28) Análisis Por Envoltura De Datos 14 & =  = 1 I *+ =  ≥0 ∀T; ℎ ^ ,ℎ  ] ≥0 ∀,W c R  Las apreciaciones realizadas en el ejemplo del modelo BCC-Input y su comparativa con el modelo CCR-Input, se pueden extrapolar al modelo BCC-Output, con la salvedad de que la orientación, de este último, es de salida. 2.2.3 Modelos FDH (Free Disposal Hull) Estos modelos utilizan la tecnología FDH, se diferencian en la tecnología VRS en que no permiten la combinación convexa de dos unidades existentes, únicamente se considera la existencia de las unidades observadas y de otras unidades virtuales que consumen más recursos o producen menos que estas. La tecnología FDH, como se había visto el apartado 2.1.2 tiene las propiedades de envoltura y libre disponibilidad. A continuación se presentan varios modelos con tecnología FDH: Modelo FDH con orientación de entrada, Modelo FDH con orientación de salida, Modelo Aditivo, Measure of Inefficiency Proportions y Range-Adjusted Measure. 2.2.3.1 Modelo FDH con orientación de entrada A partir de un modelo que considera la tecnología VRS, es sencillo imponer la condición de tecnología FDH, ya que la única condición que habría que imponer es que una unidad tome como referencia una única unidad eficiente existente. Es decir que la variable =  sea binaria. La expresión matemática del Modelo FDH con orientación de entrada es: XY Z R .. &=  '  =Z R ' R −ℎ ^ I *+ =1,2,.., &=  ,  =, R +ℎ  ] I *+ W=1,2,.., &=  =1 I *+ =  ={0,1} ∀T; ℎ ^ ,ℎ  ] ≥0 ∀,W Z R  (2.29) Las holguras no participan en la función objetivo, debido a que con la proyección es radial, una vez que la DMU se proyecta sobre la frontera admisible utiliza las holguras para proyectarse sobre la frontera eficiente. Se puede dar el caso en el que una unidad se proyecte directamente sobre la frontera eficiente, en este caso las holguras serían nulas. 15 15 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Figura 2.10: Modelo FDH con orientación de entrada en el caso de un modelo con dos entradas y una salida Fuente: (Villa 2003) En la Figura 2.10, se muestra la solución de un Modelo FDH con orientación de entrada en un caso con dos entradas y una salida. Es interesante destacar el caso de la unidad ineficiente E, en el que tras chocar con la frontera eficiente puede tomar indistintamente como unidad de referencia la unidad C o D. Todas las variables =  tendrán valor cero salvo una que tendrá valor 1. Al tener variables binarias, no se puede resolver por el método simplex; sin embargo se puede utilizar el siguiente algoritmo: Z R ∗ = min  ∈ B ( R ) f max  * + , . . , 1 f '  ' R h h (2.30) Siendo: i(j)={T.'  ≤' R ,∀;,  ≤, R ,∀W } Es decir, las unidades que dominan a J. 2.2.3.2 Modelo FDH con orientación de salida Si se aplican las mismas consideraciones que se han tenido en cuenta en el apartado 2.2.3.1, el modelo que considera la orientación de salida con tecnología FDH tiene la siguiente expresión matemática: X'Y c R .. &=  '  =' R −ℎ ^ I *+ =1,2,.., &=  ,  =c R , R +ℎ  ] I *+ W=1,2,.., &=  =1 I *+ =  ={0,1} ∀T; ℎ ^ ,ℎ  ] ≥0 ∀,W (2.31) Análisis Por Envoltura De Datos 16 c R  Siendo el algoritmo que lo resuelve: c R ∗ = max  ∈ B ( R ) f min  * + , . . , k f ,  , R h h (2.32) 2.2.3.3 Modelo Aditivo El modelo aditivo fue desarrollado inicialmente por (Charnes et al. 1985) y más tarde por (Bardhan et al. 1996) Este modelo se caracteriza porque no tiene orientación, no dispone de fase radial, únicamente tiene fase rectangular como la fase 2 del modelo CCR y BCC. Este modelo se puede utilizar en tecnología CRS y VRS con las restricciones de la región admisible que se emplearon en los apartados 2.2.1 y 2.2.2. A continuación se expresa el modelo en forma envolvente: X'Y & ℎ  ] - *+ + & ℎ  ^ 1 *+ .. &=  '  =' R −ℎ ^ I *+ =1,2,.., &=  ,  =, R +ℎ  ] I *+ W=1,2,.., &=  =1 I *+ =  = { 0 , 1 } ∀ T ; ℎ  ^ , ℎ  ] ≥ 0 ∀  , W (2.33) El hecho de que no tenga orientación, permite que la unidad productiva se compare con más unidades eficientes de la frontera eficiente y tome como referencia aquella que maximice las holguras. Una característica de este modelo, descubierta por (Ali & Seiford 1990) que también posee el modelo BCC, es que es invariante ante las translaciones, es decir, se puede añadir una constante arbitraria tanto a los recursos como a las salidas y no variarán los valores óptimos del modelo, ni la tecnología, ni la ordenación de las unidades analizadas. 2.2.3.4 Measure of Inefficiency Proportions En el artículo (Cooper, W. W., Park, K. S. Pastor 1999), se desarrolló el modelo Measure of Inefficiency Proportions (MIP), es un modelo aditivo, por lo que no tiene orientación. Esta medida agrega la proporción de las holguras respecto de la unidad analizada; e intenta encontrar aquellas unidades de referencia que maximice la suma de dichas proporciones. Se rige por la siguiente expresión: X'Y Xl = & ℎ  ^ ' R 1 *+ + & ℎ  ] , R - *+ .. & =  '  = ' R − ℎ  ^ I  * +  = 1 , 2 , . . ,  (2.34) 17 17 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia & =  ,  = , R + ℎ  ] I *+ W = 1 , 2 , . . ,  &=  =1 I *+ =  = { 0 , 1 } ∀ T ; ℎ  ^ , ℎ  ] ≥ 0 ∀  , W 2.2.3.5 Range-Adjusted Measure Range-Adjusted Measure (RAM) fue desarrollado en (Cooper, W. W., Park, K. S. Pastor 1999), y al igual que el modelo MIP es un modelo aditivo y no tiene orientación. Como consecuencia, permite determinar cuál es la proporción de la holgura respecto de la máxima holgura que se da en la muestra. Para ello define dos parámetros denominados rango que tienen como valor la holgura máxima de cada variable.   ^ = max  { '  } − min  { '  }   ] = max  { ,  } − min  { ,   } (2.35) Si se agregan las proporciones de las holguras respecto de su rango, se obtiene la siguiente expresión: 0 ≤ 1  +  m & ℎ  ^   ^ 1  * + + & ℎ  ]   ] -  * + n ≤ 1 (2.36) Al tener un valor entre 0 y 1, la medida de eficiencia se calcula restándole a la unidad la ineficiencia, dejando la siguiente expresión 0 ≤ 1 − 1  +  m & ℎ  ^   ^ 1  * + + & ℎ  ]   ] -  * + n ≤ 1 (2.37) Por lo tanto el modelo se expresa con la siguiente formulación: X'Y 1 + m & ℎ  ^  ^ 1 *+ + & ℎ  ]  ] - *+ n .. &=  '  =' R −ℎ ^ I *+ =1,2,.., &=  ,  =, R +ℎ  ] I *+ W=1,2,.., &=  =1 I *+  ^ =max  {'  }−min  o'  p =1,2,..,   ] = max  { ,  } − min  o ,  p W = 1 , 2 , . . ,  (2.38) Análisis Por Envoltura De Datos 18 =  = { 0 , 1 } ∀ T ; ℎ  ^ , ℎ  ] ≥ 0 ∀  , W 2.3 Medidas de eficiencia En (Charnes et al. 1978) se define que la unidad eficiente que se usaba como referencia se nombraba con un asterisco (' ∗ ,, ∗ ) para todos los recursos i y todas las salidas k de esa unidad eficiente, así como todas las variables que se utilizaban para referirse a ella. Siendo una unidad eficiente, aquella que no pueda mejorar sus entradas o salidas sin empeorar otras entradas o salidas. La medida que analice la eficiencia de una unidad ineficiente (Γ)a partir de los resultados de los modelos anteriores debe tener las siguientes características: A. 0≤Γ≤1 B. Γ=t1⟺iXv w   0 ⟺iXv x   C. Γ es invariante independientemente de cual sea el óptimo y de las unidades que definan las variables de entrada y de salida D. Γes monotonica, siendo una función monotónica aquella cuya primera derivada no cambia de signo. Measure Efficiency Dominance (MED) fue desarrollada por (Bardhan et al. 1996) en el que partía de las restricciones de la tecnología del modelo aditivo para representar la ineficiencia de las unidades proyectadas, apoyándose en la propiedad de la traslación invariante del modelo aditivo. Se genera la proporción ineficiente de la entrada i de la unidad J. & =  '  = '  ∗ = ' R − ℎ  ^ I *+  = 1 , 2 , . . ,  0≤ℎ ^ =' R −' ∗ ≤' R 0 ≤ ℎ ^ ' R = ' R − ' ∗ ' R ≤ 1 (2.39) Y de la misma forma se genera la proporción ineficiente de la salida k de la unidad J: Estas proporciones son adimensionales por lo que se pueden agregar en la siguiente expresión, denominada Measure of Inefficiency Dominance (MID). Automáticamente, al tener la medida de ineficiencia valores entre 0 y 1, al restarle a la unidad se obtiene la llamada Measure of Efficiency Dominance (MED): & =  ,  = ,  ∗ = , R + ℎ  ] I *+ W = 1 , 2 , . . ,  0≤ℎ  ] =, ∗ −, R ≤, ∗ 0 ≤ ℎ  ] ,  ∗ = , ∗ − , R ,  ∗ ≤ 1 (2.40) 0 ≤ ∑ ' R − '  ∗ ' R 1 *+ + ∑ ,  ∗ − , R ,  ∗ - *+  +  ≤ 1 (2.41) 19 19 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Esta medida será igual a la unidad cuando no existan holguras, es decir cuando la unidad sea eficiente y será cero cuando sea ineficiente. 2.4 Secuencia de targets intermedios Una DMU ineficiente debe establecer unos targets intermedios antes de llegar a la frontera eficiente bien porque la unidad proyectada es una unidad virtual, ejecutar a la vez múltiples estrategias que mejoren la eficiencia resulta complejo y porque es complicado alcanzar la eficiencia en un solo paso. A continuación se muestra un ejemplo de la dificultad de proyectarse sobre la frontera eficiente en una tecnología VRS en el caso de dos entradas y 1 salida con valores constantes. La unidad L tiene como objetivo la unidad virtual L`, al no existir esta unidad es complejo materializarla como objetivo así como alcanzarlo en un solo paso. Figura 2.11 Modelo Aditivo con tecnología VRS, caso de 2 entradas y 1 salida Fuente: (Lim et al. 2011) Una unidad ineficiente puede estar dominada por otras unidades son ineficientes, por lo tanto no todas las unidades ineficientes son igual de importantes. Si una vez analizada la tecnología, se elimina la frontera eficiente las DMUs que formen la nueva frontera eficiente pertenecerán a Frontera Eficiente de segundo nivel. Si se repite el proceso, se obtendrá la Frontera Eficiente de tercer nivel, así sucesivamente hasta que no queden más DMUs. Este proceso fue expuesto por (Seiford & Zhu 2003) y proporciona una media relativa del atractivo de una DMU y su progreso hacia la frontera eficiente. 2.4.1 Technical Efficiency Improvement Program y Scale Efficiency Improvement Program Las unidades intermedias se convierten en objetivos específicos que pueden monitorizar y medir el grado de mejora de la unidad analizada. Por otra parte aquellas unidades que son eficientes técnicamente, deben intentar alcanzar la eficiencia global y situarse en la zona de máxima productividad (Most Productive Scale Size). (Lozano & Villa 2010) definieron dos modelos basados en el modelo MIP para tecnología VRS. El primero 0 ≤ 1 − ∑ ' R − '  ∗ ' R 1 *+ + ∑ ,  ∗ − , R ,  ∗ - *+  +  ≤ 1 (2.42) Análisis Por Envoltura De Datos 20 determinaba las unidades intermedias que no pertenecían a la frontera eficiente como Technical Efficiency Improvement Program (TEIP) y marcaban el camino a la frontera eficiente, mientras que el segundo, llamado Scale Efficiency Improvement Program (SEIP), tenía como objetivo determinar los pasos intermedios para que una unidad técnicamente eficiente alcanzara la zona MPSS. El modelo TEIP impone unos límites de mejora que generan unas unidades virtuales que marcan el camino hacia la frontera eficiente. Para ello el decisor determina las siguientes variables: o ‰ . ^ Máximo reducción relativa del recurso i para la unidad 0 o Š . ] Máximo aumento relativo de la salidas k para la unidad 0 El modelo que desarrollaron, en el que se analiza el objetivo para la unidad DMU0 en el paso t es el siguiente: X' Y ‹ .Œ = & ℎ Œ ^ ' R 1 *+ + & ℎ Œ ] , R - *+ .. &=  '  =' R Œ^+ −ℎ Œ ^ I *+ =1,2,.., &=  ,  =, R Œ^+ +ℎ Œ ] I *+ W=1,2,.., &=  =1 I *+ ℎ Œ ^ ≤‰ . ^ ' R Œ^+ =1,2,.., ℎ Œ ] ≤Š . ] , R Œ^+ W=1,2,.., = Œ > 0 ∀ T ; ℎ  ^ , ℎ  ] ≥ 0 ∀  , W (2.43) Siendo: o  el índice de los targets intermedios o ‹ .Œ Incremento de la eficiencia técnica en el paso t La solución óptima que genera el modelo para el paso t para la unidad 0 ' . Œ =&=  '  =' R Œ^+ −(ℎ Œ ^ ) ∗ I *+ , . Œ =&=  ,  =, R Œ^+ +(ℎ Œ ] ) ∗ I *+ El modelo SEIP generado para que las unidades eficientes obtengan la eficiencia global, no debe presentar la restricción de convexidad de la tecnología VRS, para utilizar la tecnología CRS. La siguiente expresión, determina el modelo con paso t de la unidad 0 hasta la unidad con eficiencia global 0’. XY = . Œ .. = .Œ ' . += .•Œ ' .• =' . Œ^+ +ℎ Œ ] +ℎ Œ ^ = . Œ ,  . + = .• Œ ,  .• = ,  . Œ ^ + + ℎ Œ ] + ℎ Œ ^ (2.44) 21 21 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia = . Œ + = . • Œ = 1 ℎ Œ ] ≤ ‰ . ] ' . Œ^+  = 1 , 2 , . . ,  ℎ Œ ^ ≤ ‰ . ] ' . Œ^+ =1,2,.., ℎ Œ ] ≤Š . ] , . Œ^+ W=1,2,.., ℎ Œ ^ ≤Š . ] , . Œ^+ W=1,2,.., = . Œ , = .• Œ , ℎ Œ ] , ℎ Œ ^ , ℎ Œ ] , ℎ Œ ^ ≥ 0 ∀  , W La unidad que se pretende alcanzar 0’ se ha determinado a través del modelo CRS MIP y permite determinar que unidades pertenecen a la zona MPSS así como qué unidades de dicha zona se convierten en los objetivos de las unidades eficientes que no tienen eficiencia global. En la Figura 2.12 se muestra el análisis de 6 DMUs con una entrada y una salida, en una tecnología VRS y los pasos que deberían seguir las unidades eficientes E y F hasta la frontera eficiente con el modelo TEIP, así como los pasos que deberían dar las unidades eficientes A, D y la unidad E cuando llega a la frontera eficiente, para alcanzar la eficiencia global. Figura 2.12: Visualización de los pasos intermedios generados por los modelos TEIP y SEIP en un caso con 6 DMUs con una entrada y una salida Fuente: (Lozano & Villa 2010) 2.4.2 Selección de targets intermedios En el artículo (Lim et al. 2011) se buscan aquellas unidades intermedias que permitan diseñar un camino hacia la frontera eficiente para todas las unidades que no pertenecen a ella. Serán targets intermedios aquellas unidades que tengan más atractivo para la unidad analizada, que no se encuentren muy alejadas y sean factibles para dicha unidad. La selección de la unidad objetivo se basa en tres criterios que se ponderan con unos pesos (• + ,• ; ,• ‘ ) escogidos por el decisor: ’ ℎ  W  ∗ = arg max {  k = • + “ k ∗ − • ;  k ∗ − • ‘ ” k : / ∈  Œ ^ + } (2.45) Siendo: o  • la frontera eficiente del nivel l ∈[1,—] o T∈”(j • ) el conjunto de iXv  ∈j • , donde j •]+ =j • − • . j + está formado por todas las unidades observadas en el problema Análisis de Redes Complejas 28 o Matriz de adyaciencia, es una matriz nxn, siendo n el número de nodos, en las que el elemento ij es igual a la unidad si existe un arco que con origen en i y destino en j. Esta matriz será simétrica si se trata de una red no dirigida. o Matriz de incidencia para grafos no dirigidos, es una matriz nxm, siendo m el número de arcos, en la que el elemento ij es igual a 1 si el vértice i es uno de los dos extremos del arco j. o Matriz de incidencia para grafos dirigidos, es una matriz nxm en la que el elemento ij es igual a 1 si el vértice i es destino del arco j, o será igual a -1 si el vértice i es el origen del arco j. o Matriz de incidencia para grafos bipartitos, es una matriz n 1 xn 2 , siendo n 1 el número de nodos de tipo 1 y n 2 el número de nodos de tipo 2, en la que el elemento ij es igual a 1 si existe un enlace entre el nodo i es un nodo de tipo 1 y el nodo j que es un nodo de tipo 2. Estas matrices también se usan para definir las redes con pesos, la única diferencia es que sus elementos no son iguales a la unidad, sino al peso del arco que se está considerando. Como consecuencia, una red sin pesos es equivalente a una red con pesos iguales a la unidad. Una vez se dispone de una red dirigida con pesos, se puede convertir en una red no dirigida si se aplica la herramienta de simetría, según (Costa et al. 2007) la matriz que se genera parte de la suma de la matriz de adyaciencia original y su traspuesta. También se puede convertir en una red sin pesos considerando que existen todos los arcos de la red original cuyo peso supere un cierto umbral. Figura 3.1: Tipos principales de redes complejas y sus transformaciones Fuente: (Costa et al. 2007) A continuación se muestran los conceptos de paseo, camino, sendero, ciclo y componentes con el fin de mostrar los diferentes tipos de conjuntos existentes en una red según el criterio de agrupación. Una sucesión de nodos conectados entre sí constituyen un paseo, mientras que en un paseo si ninguno de los nodos se ha recorrido más de una vez se denomina camino. La longitud de un camino viene determinada por la suma de los pesos de los arcos que componen el camino, siendo el camino más corto entre un par de nodos el camino geodésico. Un paseo en el que ningún arco se recorre más de una vez se denomina un sendero, mientras que un sendero cerrado, es decir que se inicia y finaliza en el mismo nodo, se denomina ciclo. Como consecuencia, una red acíclica es una red que no tiene ciclos. Por otra parte, el arco que tiene como origen y destino el mismo nodo se denomina loop. 29 29 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Dentro de una red se define como componente, al mayor subgrafo conectado. De forma que todos vértices pertenecen a una única componente, por lo que dos vértices conectados entre sí pertenecen a la misma componente. En el caso de los vértices aislados, cada vértice forma una única componente. La componente con el mayor número de nodos se denomina, componente gigante. Matemáticamente se define con la siguiente expresión: ( ® • , “ • ) : D ® • ⊆ ® ∧ “ ′ ⊆ “  ∈ ® • ∧ T ∈ ® • ⟹ T  á       é   “ ′  ∈ ® • ∧ (  , T ) ∈ “ ⟹ T ∈ ® ′ (  , T ) ∈ “ ′ (3.1) En el caso de una red dirigida existen dos tipos de componentes: las componentes débilmente conectadas que no tienen en cuenta el sentido de los arcos y se calculan como si la red fuese no dirigida y las componentes fuertemente conectadas que tienen en cuenta el sentido de los arcos, por lo que dentro de una componente existe un camino entre cada par de nodos del subgrafo. Dentro de una red dirigida se considera la componente de salida de un nodo, como el conjunto de nodos que pueden ser alcanzados por él, mientras que la componente de entrada de un nodo es el conjunto de nodos que pueden alcanzarlo. 3.2 Caracterización de las redes Antes de definir los modelos básicos de redes es necesario conocer algunas métricas que permitan caracterizarlas. La nomenclatura que se utilizará en las formulaciones son: ⋅  : Número de nodos en una red ⋅  Número de arcos en una red ⋅ “: Matriz de adyaciencia que define la red con elementos binarios ⋅ ´: Matriz de adyaciencia que define los pesos de los arcos de la red ⋅   : Camino geodésico entre el nodo i y el nodo j A continuación se definen las métricas básicas que caracterizan una red: o Densidad: Muestra el ratio entre el número de enlaces existentes en una red y el número posible de enlaces. En una red no dirigida el número de posibles enlaces existentes en una red es la mitad que en una red dirigida para el mismo número de nodos. Tabla 3.1. Densidad Red no dirigida Red dirigida µ =   (  − 1 ) / 2 µ =   (  − 1 ) o Grado del nodo i: Existen varios tipos de grado, en caso de las redes no dirigidas se habla de grado (W  ) al número de nodos que están conectados con el nodo i. En el caso de las redes dirigidas se habla de grado de entrada (W I ) al número de arcos que tienen como destino el nodo i, mientras que el grado de salida (W x·Œ ) es el número de arcos que Análisis de Redes Complejas 30 tienen como origen el nodo i. El grado total representa el número de conexiones que tiene el grado i y se calcula como la suma del grado de entrada y el grado de salida. Tabla 3.2. Grado Red no dirigida Red dirigida W  =&“   W  I = & “   W x·Œ =&“   W  = W  x·Œ + W  I o Fuerza del nodo i (  ). En el caso de las redes no dirigidas representa la longitud total de los arcos que conectan al nodo i con la red. Si se considera el caso de las redes dirigidas, se hace la misma distinción que se ha realizado en la métrica del grado. El sumatorio de las longitudes de los arcos que tienen como origen el nodo i es el grado de entrada ( I ), mientras que el grado de salida ( x·Œ ) es el sumatorio de las longitudes de los arcos que llegan al nodo i. Siendo el sumatorio de ambos la fuerza total del nodo i (  ). Tabla 3.3. Fuerza Red no dirigida Red dirigida   =&´     I = & ´    x·Œ =&´     =   x·Œ +   I o Camino medio: Determina la longitud media de los caminos más cortos entre cualquier par de nodos. En caso de que se considere que la matriz entre dos nodos que no están conectados es ∞, se debe considerar únicamente en la siguiente formulación los caminos entre los nodos que sí están conectados. Tabla 3.4. Camino medio Red no dirigida Red dirigida 〈  〉 = ∑    »   (  − 1 ) 〈  〉 = ∑    »   (  − 1 ) / 2 o Diámetro El diámetro representa la máxima distancia geodésica que se observa en toda la red para cada par de nodos. Al igual que en el cálculo del camino medio, si se considera que la distancia entre dos nodos conectados es ∞, sólo se considerarán los caminos entre nodos que sí están conectados. 31 31 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Tabla 3.5. Diámetro Red no dirigida Red dirigida i = max  ¼    i = max  »    o Eficiencia: Esta medida determina que la eficiencia con la que manda información el nodo i al nodo j es inversamente proporcional a la distancia que hay entre ellos Tabla 3.6. Eficiencia Red no dirigida Red dirigida ½ = ∑    »   (  − 1 ) ½ = ∑     »   (  − 1 ) / 2 Esta métrica se corresponde con la inversa de la media armónica. o Coeficiente de clustering del nodo i: Es una métrica que permite analizar si los nodos vecinos del nodo i están conectados entre sí, dependiendo del tipo de red que se esté analizando en la literatura existen múltiples variaciones como se puede ver en (Saramäki et al. 2007), en este apartado se van a desarrollar los coeficientes de clustering recogidos por (Fagiolo 2007). Tabla 3.7. Coeficiente de Clustering red sin pesos Red no dirigida Red dirigida ¾  = 1 2 ∑ ∑     ¿   ¿ ¿ » (  ,  )  »  1 2W  (W  −1) = ( “ ‘ )  W  ( W  − 1 ) ¾  = 1 2 ∑ ∑ a   +   b (   ¿ +  ¿  ) (   ¿ +  ¿  ) ¿  W ŒxŒ aW ŒxŒ −1b−2 ↔ = = ( “ + “ Á )  ‘ 2 [ W  ŒxŒ a W  ŒxŒ − 1 b − 2   ↔ ] Siendo: ⋅ (“ ‘ )  el elemento de la diagonal i en la matriz “ ‘ ⋅ “ Á la traspuesta de la matriz “ ⋅ + ; W  (W  −1) el número de posibles triángulos que pueden existir como máximo ⋅  ↔ el número de enlaces que son bidireccionales (hay que tenerlos en cuenta para eliminar los falsos triángulos que se obtendrían en caso de no considerarlos. El nodo i tiene la posibilidad de formar dos triángulos con cada pareja de vecinos, teniendo como mucho  ÂÃÄà a ÂÃÄà ^+b ; parejas con las que generar un triángulo. Los falsos triángulos se generan por la pareja de enlaces que generan el enlace bidireccional, por esa razón se eliminan 2 posibles triángulos por enlace bidireccional. En el caso de que se consideren que los enlaces de la red tengan pesos, con el fin de determinar cuál es el peso de cada vecindad, basándose en el concepto de intensidad de subgrafo, definido como la media geométrica de los pesos de los enlaces del subgrafo. Análisis de Redes Complejas 32 Tabla 3.8. Coeficiente de Clustering red con pesos Red no dirigida Red dirigida ¾  = 1 2 ∑ ∑ • Å  + ‘ Æ • Å  + ‘ Æ • Å  ¿ + ‘ Æ ¿ » (  ,  )  »  1 2 W  ( W  − 1 ) = ´ Ç + ‘ Æ ¡  ‘ W  ( W  − 1 ) ¾  = ´ Ç + ‘ Æ + ( ´ Ç Á ) + ‘ Æ ¡  ‘ 2 [ W  ŒxŒ a W  ŒxŒ − 1 b − 2   ↔ ] Siendo ⋅ •Å la matriz • normalizada, •  ∈[0,1] ⋅ •Å +‘ Æ la matriz •Å a cuyos elementos se les ha aplicado la cúbica. o Transitividad: Una forma de analizar los ciclos de grado 3 de forma global es a través del ratio entre número de número de triángulos existentes (ciclos compuestos por tres arcos) y el número de tripletas, siendo una tripleta un conjunto formado por dos arcos que conectan al mismo nodo. Tabla 3.9. Transitividad Red no dirigida Red dirigida 5 = 3 ⋅ ∑ “  “  “   ¼  ¼  ∑ ( “  “  + “  “  + “  “  )  ¼  ¼  5 = ∑ “  “  “   »  »  ∑ “  “   »  »  o Centralidad: La posición de un nodo respecto de los demás nodos de la red, resulta determinante para el control de la información y dependiendo del punto de vista con que se mire, un nodo será más central que otro. A continuación se muestran algunos de los más relevantes:  Centralidad según el grado: Se considera que un nodo es central cuantas más conexiones tenga, porque es capaz de recibir y transmitir información fácilmente. Sin embargo no se tiene en cuenta como son los nodos a los que está conectado. Tabla 3.10. Centralidad según el grado Red no dirigida Red dirigida i ¾  = W   − 1 i ¾  = W  I + W  x·Œ  − 1 = W   − 1  Centralidad eigenvector: A diferencia de la centralidad según el grado tiene en cuenta con quién está conectado el nodo, cuanto más importante sean sus conexiones, más importante será. De forma matemática la centralidad del nodo i se expresaría de la siguiente forma: '  = + É ∑“  '  , siendo = el autovalor máximo de “.  Centralidad de intermediación: Determina con qué frecuencia se encuentra un nodo en el camino más corto entre cada par de nodos. Siendo Ê(T,/) el número de caminos más cortos entre j y p y Ê(T,/|) el número de caminos más cortos entre j y p que pasan por r. 33 33 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Tabla 3.11. Centralidad de intermediación Red no dirigida Red dirigida Š © = 1 (  − 1 ) (  − 2 ) & Ê ( T , / |  ) Ê ( T , / )  ¼ k  » © » k Š © = 2 (  − 1 ) (  − 2 ) & Ê ( T , / |  ) Ê ( T , / )  » k  » © » k o Vulnerabilidad Ante la desaparición de un nodo, no todas las redes se comportan de la misma forma, en unas la desaparición de unos pocos nodos puede suponer la desconexión de la red, mientras que otras son más robustas. Por otra parte, algunas redes presentan propiedades jerárquicas, es decir los nodos más cruciales se encuentran en las posiciones de la jerarquía más elevadas. Con el fin de determinar que nodos son más críticos se define en (Gol’dshtein et al. 2004) como la vulnerabilidad de un nodo i al ratio que determina la pérdida de eficiencia de la red cuando desaparece el nodo i y los enlaces que lo conectan. ®  =  −  ^   (3.2) Siendo la distribución máxima de todos los vértices, la vulnerabilidad de la red. Por otra parte, la distribución de la vulnerabilidad determina si una estructura es jerárquica, si todos los vértices tienen la misma vulnerabilidad estamos ante una estructura no jerárquica. Además Gol’dshtein afirma que existe una relación entre las estructuras simétricas y las estructuras jerárquicas; sin embargo no es directa. o Asortatividad: Una red es asortativa si se produce un mayor número de conexiones entre nodos del mismo tipo, en las redes sociales al hecho de que dos personas con características afines (religión, educación….) se le denomina homofilia. Para ello se genera una matriz  en la que cada elemento ( -Œ ) representa el número de arcos que conectan los vértices de tipo  con vértices del tipo . Ê =  ‖  ‖ (3.3) Siendo ‖‖ la suma de los elementos de la matriz , por lo que Ê es la matriz  normalizada. Por lo que la probabilidad de que un vértice  tenga como vecino un vértice , se rige por la siguiente expresión.  (  |  ) = ê -Œ ∑ ê -·· &  (  |  ) Œ = 1 (3.4) De forma que la asortatividad se define con el siguiente ratio, si se quiere dar el mismo peso a cada grupo, siendo Î Œ el número de grupos existentes en la red. 0 ≤ ℚ Ç = ∑  (  |  ) − 1 - Î Œ − 1 ≤ 1 (3.5) Siendo ℚ Ç=1 en caso de redes completamente asortativas y ℚ Ç=0 en el caso de redes aleatorias. Sin embargo, si el tamaño de los grupos es significativo, se utiliza la siguiente expresión, que asigna el mismo peso a todos los nodos. Análisis de Redes Complejas 34 0 ≤ ℚ = 5Y (  ) − ‖  ; ‖ 1 − ‖  ; ‖ ≤ 1 (3.6) Siendo ℚ=1 en el caso de ser una red asortativa y ℚ=0 en caso de ser una red aleatoria. 3.3 Modelos de redes Con el fin de estudiar las propiedades topológicas de las redes reales se han generados múltiples modelos; sin embargo en este apartado se van a presentar los más básicos reflejados en (Newman 2003). 3.3.1 Redes aleatorias Las redes aleatorias son el modelo más básico de las redes complejas, fue formulada en (Erdös & Rényi 1959), donde definen una red a través n vértices desconectados que se van conectando con m enlaces que se añaden evitando los loops. Otros modelos consideran que se parten de n vértices no conectados entre los que se genera un enlace entre cada par de nodos con una probabilidad p. Este último se conoce como el modelo de ErdösRényi (ER) y sus enlaces se generan según distribución binomial ’( I(I^+) ; ,/), de forma que la distribución del grado de los nodos sigue una binomial ’(−1,/). Sin embargo, cuando el número de nodos tiende a ∞ los enlaces se distribuyen según una Poisson de media 〈W〉=/(−1). En función de la probabilidad que se emplee la red estará más o menos conectada. Si /=1/ el grado medio es 1 generándose una gran componente, si la probabilidad es mucho más inferior se obtiene una red con muchos nodos aislados. Si /=ln()/, entonces el grado medio de la red es 〈W〉≈ln () desarrollando una red completamente conectada. Como características principales de la red, cabe decir que la asortatividad es nula y al igual que el grado medio, el camino medio y el clustering medio dependen de la probabilidad con la que se generan los arcos, rigiéndose por la siguiente expresión. 〈  〉 ≈ log (  ) log ( W ) /  → ∞ ¾¾ ≅ / = 〈 W 〉  − 1 ,   /  → ∞ (3.7) 3.3.2 Redes de mundo pequeño Muchas de las redes reales estudiadas presentan una media de caminos geodésicos baja, el hecho de que un nodo pueda alcanzar otro a través de un número pequeño de arcos fue descubierto por Milgram en 1967 que afirmo que los ciudadanos de EEUU estaban conectados de media por 6 conocidos. También se ha observado que estas redes tienen un número elevado de ciclos compuestos por tres arcos, es decir tienen un alto clustering. En el artículo (Watts & Strogatz 1998), se definieron las redes de mundo pequeño con el fin de generar una red que pudiera representar las propiedades descritas anteriormente, sin embargo hasta 1998 se analizaban redes o completamente aleatorias o completamente regulares, siendo estas últimas aquellas cuyos nodos tienen el mismo grado cuyo valor es mucho más pequeño que el número de nodos de la red. Las redes aleatorias tienen la media de los caminos geodésicos pequeña pero no tienen un elevado clustering, mientras que las redes regulares presentan un alto clustering y una media de caminos geodésicos elevada. Para generar estas redes, partían de un entramado regular con  vértices, donde cada vértice estaba conectado con sus W vecinos más cercanos en cada dirección, contabilizando un grado total de valor 2W, siendo Î≫W≫ log(Î)≫1. Cada enlace de la red era reordenado con una probabilidad /, de forma que si /=0 no se producía ninguna reordenación y si /=1 se generaba una red aleatoria. 35 35 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Figura 3.2 Generación de redes de mundos pequeños Fuente: (Watts & Strogatz 1998) En la siguiente figura se muestra como se produce la variación de las métricas de la media de la distancia geodésica y el clustering al representar el ratio entre una red que ha sufrido una reordenación de sus enlaces con una probabilidad / y una red que no ha sufrido ninguna reordenación. Figura 3.3: Representación de la variación de la media de la longitud geodésica y el clustering en función de la probabilidad p Fuente: (Watts & Strogatz 1998) 3.3.3 Modelos de configuración Una forma de estudiar las redes reales es comparando sus características con las de redes aleatorias similares, buscando que tengan el mismo grado de distribución. El método más común es generar el número de nodos con el grado deseado para obtener la distribución del grado deseada. Para generar ese grado se utilizan unos tipos de enlaces, llamados stubs que no unen al nodo que están asociados con ningún otro. Aleatoriamente, se seleccionan un par de stubs y se unen para formar un enlace. Otra forma para generar una red aleatoria dirigida, es partiendo de la red real y seleccionando un par de enlaces que intercambian los nodos que conectan. Sin embargo, cuando se genera una red aleatoria no dirigida se coge un arco y se cambia uno de los extremos con otro. 3.3.4 Modelo libre de escala Como característica común en muchas de las redes reales con un gran número de nodos, se observa que la distribución del grado de los nodos sigue una distribución de leyes de potencia (W)~W ^Ô . Esta distribución muestra que un gran número de nodos tiene pocos enlaces, mientras que un pequeño número de nodos tienen un gran número de enlaces que actúan como hubs. A estas redes se las denomina redes libre de escala. Análisis de Redes Complejas 36 En el artículo (Barabási & Albert 1999), se afirma que este comportamiento se debe a dos características: el crecimiento continuo de la red con nuevos vértices y que los nuevos vértices tienden a conectarse con nodos que ya están bien conectados. Con estas dos características se generó el modelo de red de Barabasi-Albert. Para obtener esta red se parte de un conjunto de  . vértices y a cada paso se genera un nuevo vértice con m enlaces que le conectan con los vértices existentes según una probabilidad proporcional al grado que tengan. Como por ejemplo (→T)=  Õ ∑ ÖÖ . Siguiendo esta regla conocida como “preferential attachment” se observa el paradigma que aquellos nodos que están más conectados consiguen más conexiones y por ello tienen más probabilidad de conseguir más. A este paradigma se le denomina “rich get richer”. 37 4 M ETODOLOGÍA DE ANÁLISIS DE REDES DE DOMINANCIA l análisis de redes complejas ofrece una herramienta muy versátil para analizar un sistema. En este trabajo se pretende implementar esta herramienta para analizar los resultados obtenidos con el análisis de envoltura de datos. Se podrán implementar diferentes índices y filtros propios de la técnica de análisis de redes y desarrollar otros nuevos. Para ello se generará una red formada por las DMUs que estarán relacionadas entre sí según la eficiencia relativa existente entre ellas. Esta red permitirá comprender las relaciones entre las unidades 4.1 Técnicas que emplean el Análisis de Redes Complejas y Análisis de Envoltura de Datos En la literatura se pueden encontrar estudios que utilizan tanto el Análisis de Redes Complejas, como el Análisis de Envoltura de Datos, desarrollando novedosos puntos de vista que permiten ampliar la forma de ver los conceptos dentro de sus propias disciplinas. A continuación se exponen diferentes técnicas que emplean ambas técnicas. 4.1.1 Análisis de redes de colaboración En el artículo (Lee et al. 2012), se realiza un estudio acerca de las Instituciones de Investigación Públicas (Public Research Institutions, PRI) en Corea en el ámbito de la ciencia y la ingeniería. Su objetivo es determinar cuál es el impacto de las estructuras de colaboración entre las diferentes instituciones, en la producción de dichas instituciones. Para ello realizan una correlación entre las redes de colaboración y la productividad entre los años 2000 y 2010 Para identificar las cooperaciones entre instituciones se basan en la autoría de los artículos científicos que publicaban y estaban registrados en Scopus. Con estos datos generan la red con el fin de analizar la posición de cada institución respecto a las demás. Con las herramientas de CNA, como la densidad, la eficiencia y el coeficiente de intermediación, determinan como se comporta la red desde el punto de vista estructural. A mayor densidad, la información se transmite mejor; a mayor eficiencia la información se transmite a muchas instituciones con un número limitado de enlaces y a mayor coeficiente de intermediación, mayor control tiene una institución sobre la información que posee. Por otra parte, analizan como son las relaciones a través del eigenvector y la centralidad por cercanía. A mayor eigenvector, mayor capacidad de coordinación entre las instituciones y a mayor la E “Saber dónde encontrar la información y cómo usarla, éste es el secreto del éxito.” Albert Einstein Metodología de análisis de redes de dominancia 44 conectados entre sí, mientras que con una probabilidad de 0.15 se elige un destino aleatoriamente. La multiplicación del paréntesis se debe a que la media del PageRank en caso de no multiplicarlo es 1/. De forma que según la fórmula propuesta todos los nodos que tengan un >1 estarán por encima de la media. 4.2.2.2 Medidas a nivel de capa o Porcentaje de nodos de la componente c que se encuentra en la capa q: Se define como el ratio entre los nodos que pertenecen a la capa q dentro de la componente c ù— ãê ùy los nodos que pertenecen a la componente c |i ã | ü ãê = ù — ãê ù | i ã | (4.23) o Grado medio de entrada de los nodos que pertenecen a la capa q de la componente c:  ãê ÝÞß © Âý = 1 ù — ãê ù &  © I © ∈ þ è (4.24) o Grado medio de salida de los nodos que pertenecen a la capa q de la componente c:  ãê ÝÞß © ÄÖà = 1 ù — ãê ù &  © x·Œ © ∈ þ è (4.25) o Distancia mínima y máxima de la capa a la frontera eficiente: Con el fin de establecer un rango en el cual se encuentra la distancia entre la capa q y la frontera eficiente, se determinan los rangos de distancia máxima y mínima. Formulándose respectivamente Z ãê 1Ýë ∈ £ min ©∈þ è  © 1Ýë , max ©∈þ è  © 1 Ýë ¤ ì ãê 1I ∈ § min © ∈ þ è ì © 1Ýë , max © ∈ þ è ì © 1I « (4.26) 4.2.2.3 Medidas a nivel de componte o Porcentaje de nodos que se encuentran en la componente c Muestra ratio de los nodos de la red que pertenece a la componente c ‰ ã = | i ã | | i | (4.27) o Porcentaje de enlaces que se encuentra en la componente c Determina el número de enlaces que pertenecen a la componente c, siendo Î ã el número de enlaces que se encuentran en la componente c y Î el número de enlaces existentes en la red. ‰  ã = | Î ã | | Î | (4.28) Resulta significativo cuando la red está compuesto por una componente gigante y varias componentes compuestas únicamente por un nodo aislado, porque en ese caso el ratio será igual a la unidad en el caso de la componente gigante. o Porcentaje de nodos eficientes de la componente c 45 45 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia El objetivo de este índice es calcular el ratio que muestre, de los nodos eficientes cuántos pertenecen a la componente c.  ã = | i ã ∗ | | i ∗ | (4.29) o Porcentaje de nodos eficientes en la componente c Este índice busca calcular dentro de una componente, cuántos nodos son eficientes.  ã  = | i ã ∗ | | i ã | (4.30) o La media del grado de los nodos pertenecientes a la componente c Al analizarse todos los nodos de la componente, a la hora de calcular la media resulta indiferente usa el grado de entrada o el grado de salida.  ã ÝÞß© = 1 | i ã | &  © I = © ∈ B è 1 | i ã | &  © x·Œ © ∈ B è (4.31) o Densidad de la componente c Como se explicó en el apartado 3.2 la densidad se define como el número de enlaces entre el número de posibles enlaces µ ã = D 1  | i ã | = 1  ( | i ã | − 1 ) | i ã | =  ãÝÞß© | i ã | − 1  | i ã | > 1 (4.32) o Diámetro de la componente c Calcula cuál es la longitud máxima de un nodo ineficiente a la frontera eficiente. Gracias a las propiedades de transitividad y aditividad el arco ij tiene como longitud la distancia del camino geodésicos entre i y j. Δ  = max © ,  ∈ B è  © (4.33) o Distancia media de la componente c a la frontera eficiente Z ã ÝÞß© = 1 | i ã | &  © 1Ýë © ∈ B è (4.34) o Mínima eficiencia de mejora total de la componente c Determina cuál es la distancia mínima que debería recorrer los nodos ineficientes de la componente c en total para poder alcanzar la frontera eficiente. ì ã = & ì © 1I © ∈ B è \ B è ∗ (4.35) 4.2.2.4 Medidas a nivel de red En el caso de que la red esté compuesta por una componente gigante y nodos aislados algunos índices que se detallan a continuación tendrán el mismo valor que sus homólogos en los índices de las componentes. o Porcentaje de nodos eficientes Metodología de análisis de redes de dominancia 46   = | i ∗ | | i | (4.36) o Diámetro de la red Δ = max © ,  ∈ B  © = max © ∈ B  © 1Ýë = max  ∈ B ∗ î  (4.37) o Distancia media a la frontera eficiente Z ÝÞß© = ∑ | i ã | Z ã ÝÞß© ã | i | = 1  &  © 1Ýë © ∈ B (4.38) 4.2.3 Filtros Las redes de dominancia proporcionan un marco en el que se puede visualizar gráficamente quién domina a quién y cuál es la eficiencia relativa existente entre ellos. Una herramienta muy útil sobre todo cuando los datos de las unidades a analizar tienen múltiples dimensiones, que impiden su representación gráfica en 2 o 3 dimensiones. Por otra parte, dentro del Análisis de Redes Complejas, existen múltiples técnicas que permiten generar subgrafos dentro de la red, que poseen características concretas con el fin de segmentar la información proporcionada por la red. A continuación se detallan algunos de los posibles filtros que se pueden aplicar o Filtro de umbral superior Genera un subgrafo en el que se eliminan todos aquellos arcos que tienen un valor mayor a un umbral () determinado. Siendo el subgrafo resultante (i,`), donde  • ={(,T)∈:0< © ≤ }. o Filtro de umbral inferior Este filtro al igual que el filtro de umbral superior mantiene en el subgrafo generado todos los nodos de la red, pero elimina aquellos arcos que tengan un valor inferior al marcado por un determinado umbral ( • ). Siendo el subgrafo resultante (i,`), donde  • ={(,T)∈:  • ≤  © }. o Filtro de grafo bipartito Si se toman 2 tipos de nodos dentro de la red: los nodos eficientes y los nodos ineficientes. Y únicamente se muestran los enlaces existentes entre los dos tipos de nodos, sin visualizar los arcos que se encuentren entre los nodos ineficientes, se obtiene un grafo bipartito definido como (i, • ). Siendo  • ={(,T)∈:∈i\i ∗ ∧ T∈i ∗ ()} o Filtro de los objetivos eficientes más cercanos Este filtro es una combinación del filtro de grafo bipartito y el filtro de umbral superior aplicando un umbral dinámico. El objetivo de este filtro es visualizar únicamente aquellos enlaces que marcan la mínima distancia a la frontera eficiente. El subgrafo se define con la siguiente expresión (i, • )siendo  • =o(,T)∈:T∈i ∗ ∧  © =ì ©1I p={(,T)∈:∈i\i ∗ ∧T∈i ∗ ()} o Filtro de objetivos eficientes Este filtro se aplica sobre cada unidad ineficiente, mostrando únicamente los nodos eficientes sobre los que se proyecta y los arcos existentes entre ellos. Si aplicamos el filtro de objetivos eficientes al nodo r, obtendríamos el siguiente subgrafo (i ∗ (), ∗ ()) o Filtro de nodos dominados Este se aplica a cualquier nodo eficiente de la red y visualiza aquellos nodos que domina y su relación con ellos. De forma que el subgrafo resultante al aplicar el filtro de nodos dominados sobre el nodo j es (i ^+ (T), ^+ (T)) o Filtro de egonetwork Al aplicar este filtro sobre un nodo p, se visualizan todos los nodos que dominan y son dominados por el nodo p, así como los arcos existentes entre todos los nodos visualizados. Definiéndose con la siguiente expresión 47 47 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia (i ßx (/), ßx (/)) siendo i ßx (/)={/}∪i(/)∪i ^+ (/) y  ßx (/)= ^+ (/)∪(/) o Filtro de esqueleto Este filtro se aplica sobre toda la red eliminando los arcos transitivos, definidos como {(,T): ∃ /∈i()∩ i ^+ (T)}. Gracias a la propiedad de transitividad, se puede reducir el número de enlaces sin perder información en la visualización. El subgrafo resultante tras la aplicación de este filtro es (i, P ) siendo  P = {(,T):i() ∩i ^+ (T)=∅} 49 5 I LUSTRACIÓN DE LA METODOLOGÍA E n este apartado se va a aplicar la metodología desarrollada a una serie de juegos de datos de la literatura, con el fin de mostrar las ventajas que se adquieren a la hora de visualizar y analizar los resultados obtenidos tras el análisis de la eficiencia en forma de red. A la hora de realizar el análisis de eficiencia en los juegos de datos, se va a utilizar la tecnología FDH, por lo que la frontera eficiente estará compuesta por unidades existentes que se proyectan sobre sí mismas y serán targets para las unidades ineficientes. La eficiencia relativa entre estas unidades se mide con la siguiente métrica aditiva, por lo que el modelo DEA no tiene orientación de entrada, ni de salida.  © = D 0  T ∉ i (  ) & ' © − '  '  ÝÞß©  + & ,  − W © , © ÝÞß©   T ∈ i (  ) (4.4) La red se construye con la metodología descrita en el apartado 4.2.1, por ello y gracias a la métrica empleada los enlaces tienen las propiedades de aditividad y de transitividad. 5.1 Juego de datos de CST El primer juego de datos que se analiza en este capítulo se encuentra en el libro (Cooper, W. W., Seiford, L. M., Zhu 2004), consta de 8 unidades productivas, un factor de entrada y un factor de salida. No tiene dimensiones al ser no representar las DMUs unos procesos reales. Juego de datos de LIM Tabla 5–2. Ejemplo de Cooper, Seiford y Tone (CST) A B C D E F G H x1 2 3 3 4 5 5 6 8 y1 1 3 2 3 4 2 3 5 Gracias a los índices a nivel de red y de componente se puede establecer que en este caso, sin necesidad de representar gráficamente las relaciones, que la red está compuesta por 3 componentes. Dos componentes formadas por nodos aislados y la tercera es una componente gigante, cuyas métricas se representan en la Tabla 5.11. “El genio se compone del dos por ciento de talento y del noventa y ocho por ciento de perseverante aplicación.” - Ludwig van Beethoven - Ilustración de la metodología 50 50 Todos los enlaces de esta red se encuentran dentro de la componente gigante, que posee la mitad de las DMUs eficientes que componen la frontera eficiente y el 75% de los nodos de la red. Estos nodos eficientes representan el 33.33% de los nodos que forman la componente gigante. La componente tiene una densidad muy baja (30%) y está compuesta por 9 arcos, dos de los cuales son transitivos. Tabla 5.1. Índices a nivel de red y de componente en la red CST Δ Z ÝÞß©   ‰ +  ξ ¾ ¾ + ÝÞß© ì + 0.79 0.25 0.50 1 3 0.47 1.84 Δ + Z + ÝÞß©  +  ‰ + µ +  +  + ÝÞß© 0.79 0.34 0.33 0.75 0.30 0.50 1.50 La distancia del nodo más ineficiente a la frontera eficiente es de 0.79 y la distancia mínima que deberían recorrer en total todos los nodos ineficientes de la componente gigante para pertenecer a la frontera eficiente es de 1.84. No obstante, la distancia media de los nodos a la frontera eficiente es más baja que la media, por lo que hay nodos muy próximos a la frontera eficiente. El grado medio dentro de la componente gigantes es de 1.50. El coeficiente clustering es muy bajo, debido a la poca transitividad de la red y al número reducido de capas, ya que no pueden existir arcos entre nodos que pertenezcan a la misma capa. A continuación se representa la red completa y el subgrafo esqueleto, donde no se encuentran los arcos transitivos. Hay que tener en cuenta que en la Figura 5.1existe un arco existe un arco entre G y B que no se visualiza porque están superpuestos los arcos GD y BD. Este arco no existe en la Figura 5.2 Figura 5.1 Visualización de la red de dominancia del juego de datos de CST Figura 5.2 Subgrafo de esqueleto en la red CST Fuente: Propia Como se puede apreciar que la frontera eficiente está compuesta por 4 DMUs, esta apreciación se encontraba implícita dentro de los índices anteriormente mencionados, porque todos los nodos aislados pertenecen a la frontera eficiente. Dentro de la Figura 5.3 se aprecia el diámetro de la red de 0.79 y cómo la mitad de los arcos son menores o iguales a 0.35. El hecho de que haya pocos arcos transitivos hace que la distribución de los enlaces del esqueleto 51 51 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia y de la red completa, que se observan en la Figura 5.4, estén muy próximas. El peso máximo de un arco no transitivo es de 0.70 y casi el 60% de estos enlaces son menores o iguales a 0.45. Figura 5.3 Distribución de las distancias máximas a la frontera eficiente del caso CST Figura 5.4 Distribución de los enlaces del caso CST Fuente: Propia La componente gigante está compuesta por 3 capas, que están formadas cada una por 2 nodos. En este caso el grado medio de entrada es constante en la capa 1 y en la capa 0, pero el grado va a ser siempre mayor cuanto más cerca esté el nodo de la frontera eficiente. Tabla 5.2. Distribución de los nodos según su capa en el caso CST Capa Nº nodos en la capa % de nodos de la componente c en la capa Z ãê 1Ýë ì ãê 1I  ãê ÝÞß © Âý  ãê ÝÞß © ÄÖà 0 2 33.33 [0,0] [0,0] 1.50 0.00 1 2 33.33 [0.22,0.35] [0.22,0.35] 1.50 1.00 2 2 33.33 [0.67,0.79] [0.57,0.70] 0.00 3.50 El grado medio de salida de la última capa es el más elevado de todas, al ser donde se encuentran los nodos ineficientes con más targets intermedios. En esta tabla se puede apreciar como la capa 1 se encuentra muy próxima a la frontera eficiente. En la Figura 5.5 se aprecia como el grado de entrada es mayor cerca de la frontera eficiente y como a medida que los nodos pertenecen a capas más alejadas de la frontera eficiente va disminuyendo, mientras aumenta el grado de salida debido a que tienen más targets intermedios. Dentro de la especificidad de un nodo coincide con el grado total del nodo y representa el número de arcos que llegan o salen de la red, mientras que el índice hub no solo muestra la proporción de enlaces, sino también cuáles son los nodos extremos. En este caso los únicos nodos que no son extremos son los nodos C y D porque tienen un índice hub distinto de cero. Por lo que son los únicos nodos que aparecen en el camino intermedio entre los nodos extremos, por ello son los únicos con un coeficiente de intermediación distinto de cero Tabla 5.3 se observan las características de los nodos, a que componente y capa pertenece cada una así como todos los índices descritos en la metodología. Los nodos pertenecientes a la capa 1, están dominados por un Ilustración de la metodología 52 52 único nodo, luego la necesidad del benchmark de los nodos eficientes a los que se refiere aumentará. Esto también se aprecia dentro de los nodos eficientes y los nodos aislados, porque todos los nodos que pertenecen a la frontera eficiente se proyectan sobre sí mismos. .La distancia máxima y mínima de los nodos ineficientes coincidirán si sólo son dominados por un único nodo, al solo haber una medida a la frontera eficiente. Figura 5.5 Visualización del grado de entrada y de salida en función de las capas en el caso CST Fuente: Propia La especificidad de un nodo coincide con el grado total del nodo y representa el número de arcos que llegan o salen de la red, mientras que el índice hub no solo muestra la proporción de enlaces, sino también cuáles son los nodos extremos. En este caso los únicos nodos que no son extremos son los nodos C y D porque tienen un índice hub distinto de cero. Por lo que son los únicos nodos que aparecen en el camino intermedio entre los nodos extremos, por ello son los únicos con un coeficiente de intermediación distinto de cero Tabla 5.3. Índices a nivel de nodo en el caso CST iX v © Componente Capa | i ∗ (  ) |  © 1Ýë ì © 1I  © I  © x·Œ ½ © c © Š © ¾ ¾ ©   © B 1 0 1 0.00 0.00 4 0 4 0 0.00 0.50 2.55 E 1 0.00 0.00 2 0 2 0 0.00 0.00 1.03 C 1 1 0.35 0.35 1 1 2 1 0.33 1.00 0.77 D 1 0.22 0.22 2 1 3 2 0.33 0.67 0.95 F 2 2 0.79 0.70 0 4 4 0 0.00 0.33 0.67 G 2 0.67 0.57 0 3 3 0 0.00 0.33 0.673 A 2 0 1 0.00 0.00 0 0 0 0 0.00 0.00 0.67 H 3 0 1 0.00 0.00 0 0 0 0 0.00 0.00 0.673 53 53 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia Resulta sorprendente encontrar que la DMU C tiene un coeficiente de clustering 1, esto se debe a que domina a un nodo y sólo está dominada por nodo, por lo que el único arco existente entre sus vecinos es un arco transitivo. El nodo D por su parte, se encuentra en la misma capa que el nodo C y su coeficiente clustering es menor debido a que domina a dos nodos de la capa 2 que nunca podrán estar dominados por su pertenencia a la misma capa. El coeficiente PageRank permite ordenar los nodos de la red según su importancia, el nodo que más enlaces tiene y cuyos vecinos son más importantes es el nodo B, seguido por el nodo E con un PR muy cercano al nodo D esto se debe a que ambos dominan a los mismos nodos. Sin embargo, el nodo E pertenece a la frontera eficiente. Tabla 5.4. Índices a nivel de nodos eficientes en el caso CST iX v © | i ^ + ( T ) | | i ^ ^ + ( T ) | í  î  ï  A 0 0 0.00 0.00 0 B 4 2 2.03 0.79 2 E 2 0 1.27 0.70 0 H 0 0 0.00 0.00 0 Si se analizan los nodos eficientes, se observa como B es la DMU más importante al ser un target para la mayor parte de los nodos de la red. Además, es el único nodo eficiente para dos nodos de la red, mientras el resto de la frontera no los tiene. El radio de ineficiencia es similar para los nodos eficientes de la red. El potencial del benchmarking es superior en el nodo B debido a que domina a más nodos y es el único que domina a nodos que se encuentran en la primera capa. 5.2 Juego de datos de Lim A continuación se usa el juego de datos del supermercado utilizado en (Lim et al. 2011) compuesto por 12 DMUs con 2 entradas y 1 salida. Las dimensiones de las unidades de las entradas son: 10 empleados y 1000 m 2 de superficie, mientras que las dimensiones de las salidas son 100.000 dólares. A continuación se muestran los datos del problema. Tabla 5.5. Datos del caso Lim Tiendas A B C D E F G H I J K L Empleados x1 2 6 9 3 4 8 5 7 8 7 7 8 Superficie x2 7 2 1 7 5 2 5 3 3 9 4 7 Ventas Y 1 1 1 1 1 1 1 1 1 1 1 1 Todas las unidades, al tener salidas constantes, permite que se pueda representar el conjunto de datos en un gráfico de dos dimensiones y visualizar donde se encentra la frontera eficiente, así como las relaciones entre las diferentes DMUs. Una vez generada la red de dominancia, se muestra gráficamente en la siguiente figura. Ilustración de la metodología 60 60 Δ + Z + ÝÞß©  +  ‰ + µ +  +  + ÝÞß© 2.06 0.76 0.18 0.92 0.34 0.67 3.36 Si se observa la Figura 5.14 poco más del 80% de las distancias máximas a la frontera eficiente es menor o igual que 1.5 Siendo la mínima distancia que deberían recorrer las DMUs ineficientes en la componente 1 para pertenecer a la frontera eficiente 7.98. La distancia media de las DMUs a la frontera eficiente tiene un valor de 0.70 Figura 5.13 Distribución de las distancias máximas a la frontera eficiente en el caso Park Figura 5.14 Distribución de los enlaces en el caso Park Fuente: Propia El grado medio dentro de la componente es 3.36, pero si atendemos al grado medio de entrada y de salida de cada capa vemos como el grado de entrada es más elevado en la capa 0 y disminuye a medida que la capa se aleja de la frontera eficiente. Todas las capas están compuestas por 2 nodos, salvo la capa 1 que está compuesta por 3. Por lo que los intervalos entre los que se encuentran las distancias máximas y mínimas a la frontera eficiente desde dichas capas, no son en verdad un intervalo en este caso, salvo en la capa1. Tabla 5.12. Distribución de los nodos según su capa en el caso Park Capa Nº nodos en la capa % de nodos de la componente c en la capa Z ãê 1Ýë ì ãê 1I  ãê ÝÞß © Âý  ãê ÝÞß © ÄÖà 0 2 18.18 [0,0] [0,0] 4.33 0 1 3 27.27 [0.19,0.67] [0.19,0.67] 5 1 2 2 18.18 [0.62,1.15] [0.62,1.05] 3 4 3 2 18.18 [0.81,0.86] [0.76,0.81] 1.5 4.5 4 2 18.18 [1.77,2.06] [1.67,1.96] 0 8.5 En la Figura 5.15 se puede observar una correlación negativa entre el grado de entrada y las capas y una correlación positiva entre el grado de salida y las capas. En caso de querer calcularse esta correlación se debería no 61 61 Aplicaciones de técnicas de análisis de redes complejas a redes de dominación en eficiencia tener en cuenta las componentes formadas por nodos aislados. Figura 5.15 Visualización del grado de entrada y de salida en función de las capas en el caso Park Fuente: Propia Si observamos la Tabla 5.8 se aprecia que la distancia máxima y la distancia mínima de cada nodo a la frontera eficiente coindicen, salvo en las DMUs G,J,K,L. Esto se debe a que el resto de los nodos sólo tienen un nodo de referencia como muestra |i ∗ ()|. Dentro de la componente gigante se aprecian 4 nodos en los extremos, el 66.67% de los nodos tiene una especifidad en el rango entre 7 y 8 y se aprecia mucha más variación dentro del hub, donde el máximo valor lo alcanza el valor H, que alcanza también el mayor coeficiente de intermediación. El coeficiente clustering es muy elevado, debido a la transitividad mencionada previamente, siendo mayor en las capas intermedias 2 y 3. El nodo B es el más importante de todos los nodos eficientes, debido a su elevado grado de entrada y a la importancia de sus vecinos. Mientras que el nodo B tiene a los dos nodos más importantes de la capa 1 (Los nodos E y F), el nodo A sólo domina al nodo D en esta capa. De hecho el resto de los nodos que domina el nodo A, son 4 de los 6 nodos menos importantes de toda la red. Tabla 5.13. Índices a nivel de nodo en el caso Park iX v © Componente Capa | i ∗ (  ) |  © 1Ýë ì © 1I  © I  © x·Œ ½ © c © Š © ¾ ¾ ©   © A 1 0 1 0.00 0.00 5 0 5 0 0.00 0.70 1.48 B 1 0.00 0.00 8 0 8 0 0.00 0.75 3.40 D 1 1 0.67 0.67 3 1 4 3 2.25 0.83 0.66 E 1 0.24 0.24 6 1 7 6 1.48 0.71 1.16 F 1 0.19 0.19 6 1 7 6 2.48 0.71 1.20 Ilustración de la metodología 62 62 iX v © Componente Capa | i ∗ (  ) |  © 1Ýë ì © 1I  © I  © x·Œ ½ © c © Š © ¾ ¾ ©   © G 1 2 2 1.15 1.05 2 5 7 10 3.24 0.62 0.59 H 1 0.62 0.62 4 3 7 12 4.34 0.81 0.71 I 3 1 0.81 0.81 1 4 5 4 1.29 0.90 0.57 K 2 0.86 0.76 2 5 7 10 2.09 0.71 0.61 J 4 2 2.06 1.96 0 8 8 0 0.00 0.57 0.53 L 2 1.77 1.67 0 9 9 0 0.00 0.56 0.53 C 2 0 1 0.00 0.00 0 0 0 0 0.00 0.00 0.53 Si se atiende a los índices referentes a los nodos eficientes, se observa como ya se ha comentado previamente, que el nodo B tiene más nodos dentro de la capa 1 que el nodo A. La distancia máxima a los nodos que dominan es similar tanto en ambos nodos así como el potencial benchmarking aunque el nodo b domine a 3 nodos más que el nodo A. Por otra parte el nodo B cuenta con una necesidad de Benchmarking mucho mayor que el nodo A al ser el único nodo eficiente para 4 nodos de la red frente a 1 en el caso del nodo A. Tabla 5.14. Índices a nivel de nodos eficientes en el caso Park iX v © | i ^ + ( T ) | | i ^ ^ + ( T ) | í  î  ï  A 5 1 6.12 1.96 1 B 8 4 7.71 2.06 2 C 0 0 0.00 0.00 0 63 6 C ONCLUSIONES as redes de dominancia permiten tener una mayor comprensión de los resultados obtenidos con el Análisis de Envoltura de Datos. Permite visualizar gráficamente los caminos de las DMUs dominadas hacia la frontera eficiente a través de la red, siendo de gran utilidad en caso de que sea imposible graficar las DMUs debido a la multidimensionalidad de los datos. En este trabajo, tras realizar un pequeño estado del arte, se ha desarrollado una metodología que permite la creación de una red de dominancia en el caso de que el análisis de DEA emplee una métrica aditiva en una tecnología FDH. Por otra parte se han definido diferentes índices que permiten analizar la posición de cada DMU dentro de la red, su posición respecto de la frontera eficiente, a través sus caminos más cercanos y la estratificación de las unidades dominadas. Estos índices permiten caracterizar la red a diferentes niveles: a nivel de red, de componente, de capa y de nodo. Una vez creada y caracterizada la red se puede visualizar y aplicar una serie de filtros en caso de que resulte complicada la visualización y se quiera únicamente observar los nodos y las relaciones que atiendan a un criterio determinado. Para explicar mejor el alcance de esta caracterización se ha aplicado la metodología a tres conjuntos de datos. No obstante la aplicación de los filtros definidos no se ha aplicado a los conjuntos de datos expuestos en este trabajo, debido al pequeño tamaño de la red. Sin embargo, resultan muy útiles en el caso de redes grandes. Dentro de los índices que se han aplicado cabe destacar el PageRank que permite ordenar las DMUs según su importancia que es atribuida en función del número y la importancia de sus vecinos. El coeficiente de intermediación que determina la importancia de un nodo según el número de veces que se encuentre en los caminos más cortos entre cada par de nodos, debido a que su información resultará más eficiente para los nodos que domina cuanto mayor sea el coeficiente. En el futuro se podría realizar un análisis que permitiera realizar la red de dominancia para modelos de DEA que consideraran una tecnología VRS y/o CRS. Así como el desarrollo de nuevas métricas que permitan caracterizar otros aspectos de la red. L “Los momentos finales de una experiencia determinan el recuerdo que conservaremos de la misma.” - Daniel Kahneman - 65 R EFERENCIAS Ali, A.I. & Seiford, L.M., 1990. Translation invariance in data envelopment analysis. Operation Research Letters, 9(6), pp.403–405. Banker, R.D., Charnes, A. Cooper, W.W., 1984. Some Models for Estimating Technical and Scale Inefficiencies in Data Envelopment Analysis. Management Science, 30(9), pp.1078–1092. Barabási, A.-L. & Albert, R., 1999. Emergence of Scaling in Random Networks. Science, 286, pp.509–512. Bardhan, I. et al., 1996. Models for Evaluating and Measuring Efficiency and Dominance in DEA. Journal of the Operation Researh Society of Japan, 39(3), pp.322–332. Charnes, A. et al., 1985. Foundations of data envelopment analysis for Pareto-Koopmans efficient empirical production functions. Journal of Econometrics, 30(1–2), pp.91–107 Charnes, A., Cooper, W.W. & Rhodes, E., 1978. Measuring the efficiency of decision making units. European Journal of Operational Research, 2(6), pp.429–444. Cooper, W. W., Park, K. S. Pastor, J.T., 1999. RAM : A Range Adjusted Measure of Inefficiency for Use with Additive Models , and Relations to Other Models and Measures in DEA. Journal of Productivity Analysis, 11, pp.5–42. Cooper, W. W., Seiford, L. M., Zhu, J., 2004. Data envelopment analysis. In Handbook on data envelopment analysis, Costa, L.D.F. et al., 2007. Characterization of complex networks: A survey of measurements. Advances in Physics, 56(1), pp.167–242. Erdös, P. & Rényi, A., 1959. On random graphs I. Publicationes Mathematicae (Debrecen), 6, pp.290–297. Fagiolo, G., 2007. Clustering in complex directed networks. Physical Review E, 76(2), pp.1–8. Farrell, M.J., 1957. The Measurement of Productive Efficiency. Journal of the Royal Statistical Society. Series A (General), 120(3), pp.253–290. Fernández, S., 2015. Representación del conocimiento sobre el Análisis por Envoltura de Datos (DEA) usando mapas de conceptos. Universidad de Sevilla. Gol’dshtein, V., Koganov, G.A. & Surdutovich, G.I., 2004. Vulnerability and Hierarchy of Complex Networks. Physics, 16(1), pp.1–4. Ho, M.H.C. et al., 2014. A new perspective to explore the technology transfer efficiencies in US universities. Journal of Technology Transfer, 39(2), pp.247–275. Lee, D.H. et al., 2012. Collaboration network patterns and research performance: The case of Korean public research institutions. Scientometrics, 91(3), pp.925–942. Lim, S., Bae, H. & Lee, L.H., 2011. A study on the selection of benchmarking paths in DEA. Expert Systems with Applications, 38(6), pp.7665–7673. Liu, J.S. et al., 2009. A network-based approach for increasing discrimination in data envelopment analysis. Journal of the Operational Research Society, 60(11), pp.1502–1510. Liu, J.S. & Lu, W.M., 2010. DEA and ranking with the network-based approach: A case of R&D performance. Omega, 38(6), pp.453–464. Lozano, S. & Villa, G., 2010. Gradual technical and scale efficiency improvement in DEA. Annals of Operations Research, 173(1), pp.123–136. Newman, M.E.J., 2003. The structure and function of complex networks. SIAM Review, 45(2), pp.167–256. Referencias 66 66 Page, L., Brin, S., Motwani, R., Winograd, T., 1999. The PageRank Citation Ranking. Bringing Order to the Web, Park, J., Bae, H. & Lim, S., 2012. Stepwise Benchmarking Path Selection in DEA. Smart Innovation, Systems and Technologies, 16, pp.477–484. Saramäki, J. et al., 2007. Generalizations of the clustering coefficient to weighted complex networks. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 75(2), pp.1–4. Seiford, L.M. & Zhu, J., 2003. Context-dependent data envelopment analysis - Measuring attractiveness and progress. Omega, 31(5), pp.397–408. Villa, G., 2003. Análisis por Envoltura de Datos (DEA): Nuevos Modelos y Aplicaciones. Univesidad de Sevilla. Watts, D.J. & Strogatz, S.H., 1998. Collective dynamics of’small-world’ networks. Nature, 393(6684), pp.440– 442.