En los clusters de altas prestaciones, los requerimientos actuales de las comunicaciones de las aplicaciones, como el patrón de tráfico, el volúmen de comunicaciones entre otras, pueden cambiar a lo largo del tiempo y son difíciles de predecir. Estas necesidades generalmente exceden o no se corresponden con los recursos disponibles realmente, lo cual conlleva a una situación de desbalanceo de los recursos, congestión en la red, reducción del throughput y un incremento considerable en los valores de latencia de los mensajes. Todo esto conlleva una degradación general del rendimiento de todo el sistema computacional. Los estudios de las aplicaciones paralelas demuestran que estas tienen un comportamiento repetitivo. Además, esta repetitividad puede detectarse y caracterizarse a través de unas fases representativas. Este trabajo propone un Algoritmo de Encaminamiento Predictivo y Distribuido (PR-DRB). Este nuevo método propone controlar la congestión de la red de manera gradual basándose en la expansión controlada de caminos, la distribución del tráfico, la repetitividad en las aplicaciones paralelas y el encaminamiento adaptativo especulativo; de manera a mantener los valores de latencia controlados. PR-DRB monitorea la latencia de los mensajes en los encaminadores y guarda las mejores soluciones adaptativas encontradas a una situación de congestión. Esto se realiza de manera a re aplicar estas mejores soluciones de manera rápida ante situaciones similares futuras. Fueron desarrollados varios experimentos que generen congestión de tráfico a fin de evaluar el rendimiento de la propuesta, y se han logrado mejoras importantes en el rendimiento global del sistema. / In high performance clusters, current parallel application communication needs, such as traffic pattern, communication volume, etc., change along time and are difficult to know in advance. Such needs often exceed or do not match available resources causing resource use imbalance, network congestion, throughput reduction and message latency increase, thus degrading the overall system performance. Studies on parallel applications show repetitive behavior that can be characterized by a set of representative phases. This work presents a Predictive and Distributed Routing Balancing (PR-DRB) technique, a new method developed to gradually control network congestion, based on paths expansion, traffic distribution, applications pattern repetitiveness and speculative adaptive routing, in order to maintain low latency values. PR-DRB monitors messages latencies on routers and saves the found solutions to congestion, to quickly respond in future similar situations. Traffic congestion experiments were conducted in order to evaluate the performance of the method, and improvements were observed.

Esta tesis doctoral aborda la aplicación de seis enfoques estadísticos que se utilizan para estimar tamaños de muestra en poblaciones multinomiales los que corresponden a: Angers (1974), Tortora (1978), Thompson (1987), Cochran (1977), Bromaghin (1993) y Fitzpatrick & Scott (1987), dichos enfoques están ampliamente discutidos en la literatura del muestreo estadístico pero generan controversia al momento de aplicarlos en estudios de salud dado a que no siempre permiten conjugar costos, representatividad y tamaños de muestra adecuados para un esquema de muestreo aleatorio simple y muestreo complejo de poblaciones en donde la variable de diseño o estudio corresponde a una distribución de tipo multinomial. Se discute inicialmente como la utilización de la máxima varianza cuando la variable de diseño con k=2 categorías entrega estimaciones de prevalencias considerando un valor P=0,50 para estimar dicho tamaño muestral, sin conocer valores previos de dicho estimador lo que entrega estimaciones sesgadas. Posteriormente se simularon poblaciones teóricas para variables de k=3, 4, 5, 6 y 7 categorías, generando 25 poblaciones distintas de tamaño N=1.000.000 que variaban según distintos valores de proporciones para las distintas categorías. Para dichas poblaciones se extrajeron mediante muestro aleatorio simple, muestras de distintos tamaños que fueron estimadas mediante los seis enfoques mencionados anteriormente que consideraron distintos valores de errores muestrales, posteriormente se evaluó el desempeño de estos mediante: 1) Tamaño de muestra, 2) Nivel de confianza real, 3) Estimador promedio, 4) Sesgo y 5) Mediana del Error cuadrático medio. Luego la discusión se enfoca en la determinación de que método analizado entrega mejores tamaños de muestra y estimaciones considerando distintos escenarios en donde las categorías consideradas van desde k=3 a k=7, finalmente se propone y discute la utilización de las medidas de incertidumbre o entropía de Shannon para estudiar la incertidumbre asociada a los vectores estimados mediante los distintos métodos. / This dissertation addresses the application of six statistical approaches used to estimate sample sizes in multinomial populations which correspond to: Angers (1974), Tortora (1978), Thompson (1987), Cochran (1977), Bromaghin (1993) and Fitzpatrick & Scott (1987), such approaches are widely discussed in the literature of statistical sampling but generated controversy when applying in health studies because they do not always allow combining costs, representation and adequate sample sizes for sampling scheme simple random sampling and complex populations where the design variable or study corresponds to a multinomial distribution type. Initially discusses how the use of a maximun variance when the design variable with k = 2 gives estimates of prevalence categories considering a P = 0.50 for this sample size estimate without knowing previous values of this estimator which delivers biased estimates. Later theoretical populations were simulated for variables k = 3, 4, 5, 6 and 7 categories, generating 25 different populations of size N = 1,000,000 varying proportions according to different values for different categories. For these populations were extracted by simple random sampling, samples of different sizes were estimated using the six approaches mentioned above that considered different values of sampling errors, then the performance of these was assessed by: 1) sample size, 2) Level of real confidence, 3) average Estimator, 4) bias and 5) mean Square Error. The discussion then focuses on determining which delivery method best used sample sizes and estimates considering scenarios where the categories considered ranging from k = 3 to k = 7, finally proposes and discusses the use of measures of uncertainty or entropy Shannon to study the uncertainty associated with the estimated vectors using different methods.

Nuestra línea de investigación se ha desarrollado en el ámbito de la estadística aplicada a las finanzas. Nuestro objetivo es encontrar y analizar nuevos modelos estadísticos para ajustar los datos financieros y nuevas técnicas para estudiar el comportamiento de las colas. Una aplicación destacada de este trabajo es el estudio del riesgo operacional. En los últimos años, la industria bancaria ha cambiado profundamente por los procesos de liberalización, innovación financiera y tecnológica. Esto, ha generado en las entidades financieras una evolución en el ámbito de la modelización de procesos para la medición y gestión del riesgo. El riesgo financiero se define como el impacto adverso en el rendimiento debido a diferentes fuentes de incertidubre. En la actualidad, y desde una perspectiva avanzada de riesgos, se identificarían y se cuantificarían tres tipos de riesgo: riesgo de mercado, riesgo de crédito y riesgo operacional. A diferencia de los anteriores, el riesgo operacional es un riesgo que no es producto de la toma de una posición de riesgo, tiene su origen en sucesos que no pueden ser adscritos a riesgo de mercado o a riesgo de crédito, se define como la pérdida potencial por deficiencias en los controles, por los errores en el procesamiento y almacenamiento de las operaciones o en la transmisión de información, así como por resoluciones administrativas y judiciales adversas, fraudes, robos o por factores externos. El método más reciente para la cobertura de riesgo operacional es el método de medición avanzado (AMA) que consiste en la modelización de la distribución agregada de pérdidas (Loss Distribution Approach o LDA) que se ha utilizado con éxito en el ámbito de seguros. Bajo el supuesto de que las severidades son independientes entre si e independientes de la frecuencia de los sucesos, la metodología LDA requiere la modelización por separado de la frecuencia y de la severidad. El capital regulatorio se calcula como el percentil de la distribución agregada de pérdidas para un nivel de probabilidad del 99;9%. Las fluctuaciones pronunciadas de precios conducen a serias inestabilidades en los mercados financieros. Estas perturbaciones llevan a problemas en la gestión del riesgo. En este contexto, es necesaria la modelización del comportamiento de estos precios que alcanzan valores extremos. La distribución normal no determina con suficiente precisión dicho comportamiento, lo cual obliga a recurrir a otro tipo de distribuciones de colas pesadas o semi pesadas. En el Capítulo uno, haremos una descripción de las distribuciones de colas pesadas que son distribuciones que tienen colas más pesadas que la distribución exponencial. Históricamente se han utilizado en el mundo de seguros, especificamente las distribuciones subexponenciales. En la última década, esta metodología se ha trasladado al mundo de las finanzas. De forma más amplia los mercados financieros están bajo una permanente tensión por la interacción entre la oferta y la demanda, lo cual implica fluctuaciones pronunciadas en los precios. El modelo clásico para estudiar la evolución de los precios es el modelo de Black Scholes que supone normalidad en la distribución de los precios. Los estudios empíricos, que presentan una curtosis elevada y valores extremos que no se pueden ajustar por la distribución normal, muestran que este modelo está lejos de ser adecuado. Suponiendo normalidad de la distribución de la oferta y de la demanda, y si hay tantas ofertas como demandas (mercado ideal), las transacciones siguen una mixtura de normales. En caso contrario, cuando no se aceptan de la misma manera las ofertas y las demandas las transacciones pueden seguir una mixtura de normales truncadas. En el Capítulo dos, proponemos la mixtura de normales truncadas para ajustar los datos de tipo de cambio. Es un modelo muy apropiado dado que en la práctica nos permite estudiar la no-normalidad de los datos teniendo en cuenta la asimetría de los mismos. Para ello, primero desarrollamos las propiedades de la distribución propuesta y a continuación demostramos que la función de verosimilitud tiene un máximo único y que este máximo depende del coeficiente de variación. El enfoque basado en la modelización de la distribución de severidad mediante distribuciones de colas semi pesadas tales que la distribución lognormal, la inversa gaussiana y la mixtura de normales proporcionan estimaciones robustas estables del capital regulatorio, es decir, las cifras de capital entre dos periodos sólo pueden variar por su exposición al riesgo. El enfoque basado en la teoría de valor extremo que se caracteriza por el ajuste de los valores que superan un determinado umbral con la distribución de Pareto generalizada es de mucha importancia dado que las entidades se basan únicamente sobre las pérdidas elevadas, aunque la elección de manera eficiente del umbral a partir del cual se realiza el ajuste a una distribución de Pareto es crucial para obtener valores estables de las medidas de riesgo. Varios autores estudiaron la estimación de la distribución de Pareto generalizada mediante el método de máxima verosimilitud. No obstante, los métodos numéricos no siempre tienen soluciones sobretodo cuando las muestras son pequeñas, por ello se han propuesto otros métodos tales como el método de los momentos ponderados que sólo se puede utilizar cuando el momento de orden dos es finito, y el método que consiste en estimar los parámetros a través de los estadísticos de orden. En el Capítulo tres, explicaremos los problemas destacados de la no convergencia en algunos casos de la función profile verosimilitud de la distribución de Pareto generalizada. Luego, demostraremos que la función profile verosimilitud se caracteriza por el coeficiente de variación empírico. Por último, probaremos que en el caso de la distribución de Pareto, la función de verosimilitud tiene un máximo global cuando el coeficiente de variación empírico es mayor que uno. Por otro lado, ilustramos con un ejemplo que la función de verosimilitud de la distribución de Pareto generalizada puede no tener soluciones. En el Capítulo cuatro, utilizamos la caracterización de la distribución de Pareto generalizada a través del coeficiente de variación condicionado para desarrollar una metodología previa y complementaria a los estudios paramétricos y contrastar el modelo desde un punto de vista empírico. Es un método alternativo a los métodos clásicos ME-Plot y el Hill-Plot para estudiar las colas. Además nos permite encontrar de manera eficiente el umbral a partir del cual podemos ajustar los datos por una distribución de Pareto y estimar el parámetro del peso de la cola. Por otro lado, proponemos un test de exponencialidad contra las alternativas de cola Pareto. Una de las dificultades de la distribución de Pareto generalizada es que al incluir distribuciones de soporte acotado, existen problemas de convergencia de los estimadores. Además las ecuaciones de verosimilitud para muestras pequeñas pueden no tener soluciones. Por ello, proponemos la distribucón TNP que es la unión de la normal truncada, la distribución exponencial y la distribución de Pareto como alternativa a la distribución GPD. / Our line of investigation has developed in the field of the statistical applied to the finances. Our aim is to find and analyse new statistical models to adjust the financial data and new techniques to study the behavior of the tails. An application of this work is the study of operational risk. The banking business has changed deeply by the processes of liberalization, financial and technological innovation. This, has generated an evolution in the field of modeling the processes for the measurement and the quantification of the risk. The risk of loss has his origin in events that can not be attribute to market risk or to credit risk, it is resulting from inadequate or failed internal processes, people and systems or from external events. This definition includes legal risk but excludes strategic and reputacional risk. The most recent method for hedging the operational risk is the method of advanced measurement (AMA) that consists in modeling the aggregate distribution of losses (Loss Distribution Approach or LDA) that has been used successfully in the field of insurances. assuming that the severities are independent, and, that are independent of the frequency of the events, the methodology LDA requires modeling separately the frequency and the severity. The VaR is then calculated as the percentile of the aggregate distribution of losses for a level of probability 99;9%. In the Chapter one, we give an overview on heavy-tailed distributions. Historically, it have been used in the world of insurances, specifically the distributions subexponentials. In the last decade, this methodology has moved to the world of the finances. In the Chapter two, it is shown that the prices formation mechanism may explain some amount of non-normality. Assuming normality for bid and ask prices, the observed transaction prices may be a mixture of normal distributions or a mixture of left- right truncated normal distributions, the latter case being more likely. The statistical properties of the mixture of left-right truncated normal distri- butions are developed. It is proved that there is only one maximum for the likelihood function and the maximum is closely related to the coeficient of variation. Our results show that continuity at zero of this distribution can be avoided in statistical analysis. Empirical work suggests that in financial data non-normality is also produced for a large number of values close to the mean, here referred to as ïnliers". This could explain that the Laplace approximation is often a better approach than normal distribution for daily returns. The approach based in the modeling the distribution of severity by semi weighed distributions such as the lognormal distribution, the inverse gaussian and the mixture of normal provide robust estimates estables of the VaR. The approach based in the theory of extreme value that adjust the values over an determined threshold by the generalized Pareto distribution is of importance To obtain values estables of the measures of the risk. In the Chapter three, we provide precise arguments to explain the anomalous behavior of the likelihood surface when sampling from the generalized Pareto distribution for small or moderate samples. The behavior of the profile-likelihood function is characterized in terms of the empirical coefficient of variation. A suficient condition is given for global maximum of the likelihood function of the Pareto distribution to be at a finite point. In the Chapter four, we develop a previous and complementary methodology to the parametric studies to contrast the model from a point of empirical view. New methods to decide between polynomial or exponential tails are introduced. Is an alternative method to the classical methods ME-Plot and the Hill-Plot. The key idea is based on a characterization of the exponential distribution and uses the residual coefficient of variation as a random process. A graphical method, called a CV plot, is introduced to distinguish between exponential and polynomial tails. Moreover, new statistics introduced from a multivariate point of view allow for testing exponentiality using simultaneously several thresholds. The usefulness of our approach is clearly shown with the daily returns of exchange rates between the US dollar and the Japan yen. One of the difficulties of the distribution of generalized Pareto is that include bounded distributions, there lead a problems of convergence of the estimators. Besides the likelihood functions for small samples can not having solutions. Thus, we propose the TNP distribution that is the union of the normal truncated, the exponential distribution and the distribution of Pareto and is an alternative to the distribution GPD to modeling financial data.

A graph where every vertex has three neighboring vertices is a cubic graph. An edge-coloring is an assignment of colors to the edges of a graph in such a way that the edges incident to a vertex have no repeated colors. An edge-coloring is optimal if it uses the minimum possible number of colors. Vizing's Theorem implies that an optimal edge-coloring of a cubic graph requires three or four colors. If three colors are enough, we call the edge-coloring a Tait-coloring. If four colors are needed, we call the graph a snark. Holyer proved that deciding wether a cubic graph is Tait-colorable is an NP-complete problem, therefore it is widely believed that it is a very difficult or intractable problem in the general case. Nevertheless, theory does not forbid efficient solutions in specific cases: this is called "breaking intractability". We describe an heuristic algorithm called CVD, for "Conflicting Vertex Displacement", which has a good empirical performance in random regular graphs. Also it allows us to check a conjecture by Biggs on "odd graphs" in instances with milions of vertices and edges, using moderately powerful computers. Snarks are relevant in graph theory: they appear often as minimal counterexamples of important conjectures, such as the Cycle Double Cover Conjecture (every bridgeless graph has a family of cycles such that every edge belongs to exactly two cycles of the family). In the analysis and synthesis of snarks, multipoles, "pieces" of cubic graphs with free ends that can be joined to each other, are often used. In a Tait-colored multipole, the number of equally colored free ends for each color and the total number of free ends have the same parity (the number of vertices of the multipole has this same parity, too). This result, known as the Parity Lemma, allows the interpretation of multipoles as logic gates and cubic graphs as logic circuits. This gives a very general way to construct snarks, based on logic circuits with no valid Boolean assignment, and allows us to relate the Tait-coloring of cubic graphs to integer factorization. In particular, we can construct snarks from prime numbers. A state of a multipole is the restriction of a Tait-coloring of the multipole to its free ends. If the set of states of a multipole is a non-empty subset of the set of states of another multipole with a larger number of vertices, we call the smaller multipole a reduction of the larger one. An irreducible multipole is a multipole with no reduction (an obvious example is a minimal multipole, that is, with no vertices or with a single vertex). The maximum number of vertices of an irreducible multipole as a function of its number (m) of free ends is denoted by v(m). Its behavior is well-known only for m<6, while there is a specific lower bound for v(6). We prove the irreducibility of multipoles having a tree, a forest or a cycle as their underlying graphs. This allows us to prove a linear lower bound for v(m), the first general result for this function. / Un graf on cada vèrtex té tres vèrtexs adjacents és un graf cúbic. Un aresta-acoloriment és una assignació de colors a les arestes d'un graf de tal manera que no es repeteixin colors en les arestes incidents a un mateix vèrtex. Un aresta-acoloriment és òptim si utilitza el mínim nombre possible de colors. El Teorema de Vizing implica que un aresta-acolorament òptim d'un graf cúbic requereix tres o quatre colors. Si tres colors són suficients, de l'aresta-acoloriment en diem Tait-acoloriment. Si fan falta quatre colors, diem que el graf és un snark. Holyer va demostrar que determinar si un graf cúbic és Tait-acolorible és un problema NP-complet, i per tant se suposa àmpliament que és un problema molt difícil o intractable en el cas general. Tanmateix, la teoria no prohibeix que es puguin resoldre eficientment casos concrets: és el que s'anomena "ruptura de la intractabilitat". Descrivim un algorisme heurístic anomenat DVC, per "Desplaçament de Vèrtexs Conflictius", que té un bon rendiment empíric en grafs regulars aleatoris. També ens permet comprovar una conjectura de Biggs sobre els "odd graphs" en instàncies de milions de vèrtexs i arestes, utilitzant ordinadors de potència moderada. Els snarks són rellevants en la teoria de grafs: sovint apareixen com a contraexemples minimals de conjectures importants, com per exemple la Conjectura del Recobriment Doble per Cicles (tot graf sense ponts té una família de cicles tal que cada aresta pertany exactament a dos dels cicles). En l'anàlisi i síntesi d'snarks se solen utilitzar multipols, que són "peces" de grafs cúbics amb extrems lliures que es poden unir entre ells. En un multipol Tait-acolorit, el nombre d'extrems lliures de cada color té la mateixa paritat que el nombre total d'extrems lliures (i que el nombre de vèrtexs del multipol). Aquest resultat, conegut com el Lema de Paritat, permet interpretar els multipols com a portes lògiques i els grafs cúbics com a circuits lògics. Això proporciona una manera molt general de construir snarks, en base a circuits lògics sense cap assignació booleana vàlida, i també permet relacionar l'aresta-acoloriment de grafs amb la factorització de nombres enters. En particular, permet construir snarks a partir de nombres primers. Un estat d'un multipol és la restricció d'un Tait-acoloriment del multipol als seus extrems lliures. Si el conjunt d'estats d'un multipol és un subconjunt no buit del conjunt d'estats d'un altre multipol amb un nombre de vèrtexs més gran, diem que n'és una reducció. Un multipol irreductible és un multipol sense cap reducció (un exemple obvi és un multipol minimal, és a dir sense vèrtexs o amb un sol vèrtex). El màxim nombre de vèrtexs d'un multipol irreductible en termes del seu nombre d'extrems lliures és una funció, representada per v(m), el comportament de la qual només es coneix exactament per m<6, mentre que hi ha una fita inferior específica per v(6). Demostrem la irreductibilitat dels multipols que tenen un arbre, un bosc o un cicle com a graf subjacent. Això ens permet establir una fita lineal inferior que és el primer resultat de naturalesa general sobre la funció v(m).

En la presente tesis se analiza el problema del coloreado de grafos tanto desde el punto de vista teórico como en relación a la resolución del problema mediante técnicas algorítmicas, algunas de las cuales se describen por vez primera. Se estudian asimismo distintas variaciones del problema simple del coloreado incluyendo el coloreado de vértices etiquetados, en que se asigna un número variable de colores a cada vértice, y el coloreado con aristas etiquetadas, en el que los colores asignados a vértices adyacentes deben guardar una distancia mayor o igual a la etiqueta de la arista que los une, así como combinaciones de ambos.Las técnicas descritas para el coloreado de grafos han sido posteriormente adaptadas a un problema de asignación de frecuencias en telefonía móvil habiéndose aplicado los algoritmos sobre distintos tipos de redes celulares. Las distintas redes analizadas pueden incorporar o no conmutación en frecuencia, variando la naturaleza del problema en cada caso. Para el caso de coloreado múltiple asociado al problema de asignación de frecuencias se ha descrito un conjunto de matrices asociadas a un grafo G(V,E) y un coloreado simple C que permiten reasignar colores a distintos vértices de G(V,E) aprovechando colores de C. Este reciclaje, en combinación con las métodos algorítmicos aplicados en coloreados simples, ha permitido resolver con eficiencia el problema del multicoloreado de grafos y en consecuencia el problema de asignación de frecuencias en redes celulares.En la segunda parte de la tesis se estudian las redes pequeño-mundo y se describen pautas deterministas para su obtención. De este modo se describe en primer lugar el modelo probabilista definido por Watts y Strogatz y se analiza la aparición de autoorganización crítica en las redes pequeño-mundo (caracterizadas por un apiñamiento elevado y un diámetro o distancia máxima entre vértices reducido) para a continuación ampliar el concepto sobre modelos deterministas. Se ha demostrado de este modo la posibilidad de obtener redes pequeño-mundo sobre grafos circulantes, mallas toroidales e hipercubos.Finalmente se ha probado la universalidad del efecto pequeño-mundo, es decir, la posibilidad de recortar arbitrariamente el diámetro de un grafo genérico G(V,E) sin que se produzcan variaciones significativas en su topología local (medida a partir del factor de clustering o apiñamiento del grafo), explicando así la ubicuidad de las redes pequeño-mundo y su descripción en entornos de todo tipo: social, biológico, industrial, matemático, etcétera.

For a given cost matrix and a given communication requirement matrix, the OCSTP is defined as finding a spanning tree that minimizes the operational cost of the network. OCST can be used to design of more efficient communication and transportation networks, but appear also, as a subproblem, in hub location and sequence alignment problems. This thesis studies several mixed integer linear optimization formulations of the OCSTP and proposes a new one. Then, an efficient Branch & Cut algorithm derived from the Benders decomposition of one of such formulations is used to successfully solve medium-sized instances of the OCSTP. Additionally, two new combinatorial lower bounds, two new heuristic algorithms and a new family of spanning tree neighborhoods based on the Dandelion Code are presented and tested.

El fet que cada vegada disposem de més dades socials de sistemes socio-tecnològics---sistemes que registren la nostra activitat diària, tals com a registres de targeta de crèdit, registres de trucades telefòniques, correu electrònic, etc.---i les xarxes socials on-line---com facebook, twitter, instagram, etc.---, ha fet possible estudiar el comportament humà des de diferents perspectives. Descobrir els patrons darrere d'aquestes dades no només aportarà un millor coneixement de la societat, sinó que també beneficiaria a la societat en diferents aspectes, com l'adaptació de tecnologia a les necessitats socials o el disseny de millors polítiques per evitar la propagació d'epidèmies. L'objectiu d'aquesta tesi és precisament descobrir patrons estructurals i temporals en els sistemes socials i desenvolupar models predictius sobre la seva base. En particular, analitzem l'evolució a llarg termini en una xarxa de correu electrònic amb més d'1.000 persones al llarg de quatre anys consecutius. Veiem que, encara que l'evolució de la comunicació entre usuaris és altament impredictible, l'evolució macro de les xarxes de comunicació social segueix lleis estadístiques ben definides, caracteritzades pel decaïment exponencial de les variacions logarítmicas del pes de les comunicacions entre usuaris i del pes dels individus a la xarxa. Al mateix temps, trobem que els individus tenen una forma característica de comunicar-se, i aquesta no canvia en anys. Quant a la predictabilidad, desenvolupem dos models basats en xarxes: un model de recomanació (que prediu votacions d'usuaris sobre objectes) i un model d'inferència temporal (que prediu successos en el temps). El nostre model de recomanació és escalable i considerablement més precís en les seves prediccions que els algorismes actuals per bases de dades de milions de votacions. L'enfocament es basa en la suposició que hi ha grups de persones i d'articles (per exemple, pel·lícules, llibres, etc.) i que les preferències d'un individu sobre un element donat depenen del grups als que pertanyin. Però a més, permet que cada individu i cada article pertanyin simultàniament a diferents grups. Les comunitats superposades resultants i les prediccions sobre les votacions poden inferir-se amb un algorisme escalable de maximització d'expectatives basat en una aproximació variacional. En el mo / El hecho que cada vez dispongamos de más datos sociales de sistemas socio-tecnológicos---sistemas que registran nuestra actividad diaria, tales como registros de tarjeta de crédito, registros de llamadas telefónicas, correo electrónico, etc.---y las redes sociales on-line---como facebook, twitter, instagram, etc.---, ha hecho posible estudiar el comportamiento humano desde diferentes perspectivas. Descubrir los patrones detrás de estos datos no sólo aportará un mejor conocimiento de la sociedad, sino que también beneficiaría a la sociedad en diferentes aspectos, como la adaptación de la tecnología a las necesidades sociales o el diseño de mejores políticas para evitar la propagación de epidemias. El objetivo de esta tesis es precisamente descubrir patrones estructurales y temporales en los sistemas sociales y desarrollar modelos predictivos en base a ellos. En particular, analizamos la evolución a largo plazo en una red de correo electrónico con más de 1.000 personas a lo largo de cuatro años consecutivos. Vemos que, aunque la evolución de la comunicación entre usuarios es altamente impredecible, la evolución macro de las redes de comunicación social sigue leyes estadísticas bien definidas, caracterizadas por el decaimiento exponencial de las variaciones logarítmicas del peso de las comunicaciones entre usuarios y del peso de los individuos en la red. Así mismo, encontramos que los individuos presentan una forma caracteristica de comunicarse, y esta no cambia en años. En cuanto a la predictibilidad, desarrollamos dos modelos basados en redes: un modelo de recomendación (que predice votaciones de usuarios sobre objetos) y un modelo de inferencia temporal (que predice sucesos en el tiempo). Nuestro modelo de recomendación es escalable y considerablemente más preciso en sus predicciones que los algoritmos actuales para bases de datos de millones de votaciones. El enfoque se basa en la suposición de que hay grupos de personas y de artículos (por ejemplo, películas, libros, etc.) y que las preferencias de un individuo sobre un artículo dado dependen de los grupos a los que pertenezcan. Pero además, permitimos que cada individuo y cada artículo pertenecan simultáneamente a diferentes grupos. Las comunidades superpuestas resultantes y las predicciones sobre las votaciones pueden inferirse con un algoritmo de maximiz / The increasing availability of social data sources from socio-technological systems ---systems that record our daily activity such as credit card records, call-phone records, email, etc.--- and on-line social networks ---such as facebook, twitter, instagram, etc.---, has made it possible to study human behavior from different perspectives. Uncovering the patterns behind this data would not only give us a better knowledge about our society but could also benefit our society in a number of ways such as adapting technology to social needs or design better policies to avoid spread of epidemics. The aim of this thesis is precisely to uncover both structural and temporal patterns in social systems and to develop predictive models based on them. In particular, we analyze the long-term evolution in an email network with over 1,000 individuals throughout four consecutive years. We find that, although the evolution of individual ties is highly unpredictable, the macro-evolution of social communication networks follows well-defined statistical laws, characterized by exponentially decaying log-variations of the weight of social ties and of individuals' social strength. At the same time, we find that individuals have social signatures that are remarkably stable over the scale of several years. Regarding predictability, we develop two network-based models: a recommender model, and a temporal inference model. Our recommender model makes scalable predictions and is considerably more accurate than current algorithms for large datasets. The approach is based on the assumption that there are groups of individuals and of items (e.g. movies, books, etc.), and that the preferences of an individual for an given item depend on their group memberships. Importantly, we allow each individual and each item to belong simultaneously to different groups. The resulting overlapping communities and the predicted preferences can be inferred with a scalable expectation-maximization algorithm based on a variational approximation. In the temporal inference model users can belong simultaneously to different groups, but also the time intervals belong to overlapping communities. The results suggest that the algorithm is able to distinguish real events of non-events almost perfectly.

No description available.

La majoria de metaheuristiques tenen una component aleatori, que normalment està basada en aleatorització uniforme -i.e., l'ús de la distribució de probabilitat uniforme per fer seleccions aleatòries. Per altra banda, el marc Multi-start biased Randomization of classical Heuristics with Adaptive local search proposa l'ús de aleatorització esbiaixada (no uniforme) per al disseny de algoritmes metaheuristics alternatius -i.e., l'ús de distribucions de probabilitat esbiaixades com la geomètrica o la triangular. En algunes situacions, aquesta aleatorització no uniforme ha obtingut una convergència més ràpida a la solució quasi òptima. El marc MIRHA també inclou un pas de cerca local per a millorar les solucions generades durant el procés iteratiu. A més, permet afegir passos de cerca adaptats al problema, com cache (memòria) o splitting (dividir i conquerir), que permeten la generació de solucions competitives (quasi òptimes). Els algoritmes dissenyats amb el marc MIRHA permeten obtenir solucions d'alta qualitat a problemes realistes en temps de computació raonables. A més, tendeixen a utilitzar un nombre reduït de paràmetres, el que els fa simples d'implementar i configurar en la majoria d'aplicacions pràctiques. El marc s'ha aplicat exitosament a diversos problemes d'enrutament i planificació. Un dels principals objectius d'aquesta tesi és desenvolupar nous algoritmes , basats en el marc mencionat, per solucionar problemes d'optimització combinatòria que poden ser d'interès a la industria de les telecomunicacions. / La mayoría de metaheurísticas tienen un componente aleatorio, que normalmente está basada en aleatorización uniforme -ie, el uso de la distribución de probabilidad uniforme para hacer selecciones aleatorias. Por otra parte, el marco Multi-start Biased Randomization of classical heurística with Adaptive local search propone el uso de aleatorización sesgada (no uniforme) para el diseño de algoritmos metaheurísticos alternativos -ie, el uso de distribuciones de probabilidad sesgadas como la geométrica o triangular. En algunas situaciones, esta aleatorización no uniforme ha obtenido una convergencia más rápida en la solución casi óptima. El marco MIRHA también incluye un paso de búsqueda local para mejorar las soluciones generadas durante el proceso iterativo. Además, permite añadir pasos de búsqueda adaptados al problema, como caché (memoria) o splitting (dividir y conquistar), que permiten la generación de soluciones competitivas (casi óptimas). Los algoritmos diseñados con el marco MIRHA permiten obtener soluciones de alta calidad a problemas realistas en tiempo de computación razonables. Además, tienden a utilizar un número reducido de parámetros, lo que los hace simples de implementar y configurar en la mayoría de aplicaciones prácticas. El marco se ha aplicado exitosamente a varios problemas de enrutamiento y planificación. Uno de los principales objetivos de esta tesis es desarrollar nuevos algoritmos, basados ¿¿en el marco mencionado, para solucionar problemas de optimización combinatoria que pueden ser de interés en la industria de las telecomunicaciones. / Most metaheuristics contain a randomness component, which is usually based on uniform randomization -i.e., the use of the Uniform probability distribution to make random choices. However, the Multi-start biased Randomization of classical Heuristics with Adaptive local search framework proposes the use of biased (non-uniform) randomization for the design of alternative metaheuristics -i.e., the use of skewed probability distributions such as the Geometric or Triangular ones. In some scenarios, this non-biased randomization has shown to provide faster convergence to near-optimal solutions. The MIRHA framework also includes a local search step for improving the incumbent solutions generated during the multi-start process. It also allows the addition of tailored local search components, like cache (memory) or splitting (divide-and-conquer) techniques, that allow the generation of competitive (near-optimal) solutions. The algorithms designed using the MIRHA framework allows to obtain "high-quality" solutions to realistic problems in reasonable computing times. Moreover, they tend to use a reduced number of parameters, which makes them simple to implement and configure in most practical applications. This framework has successfully been applied in many routing and scheduling problems. One of the main goals of this thesis is to develop new algorithms, based in the aforementioned framework, for solving some combinatorial optimization problems that can be of interest in the telecommunication industry.

En aquesta tesi s'estudia la dimensió mètrica forta de grafs producte. Els resultats més importants de la tesi se centren en la recerca de relacions entre la dimensió mètrica forta de grafs producte i la dels seus factors, juntament amb altres invariants d'aquests factors. Així, s'han estudiat els següents productes de grafs: producte cartesià, producte directe, producte fort, producte lexicogràfic, producte corona, grafs unió, suma cartesiana, i producte arrel, d'ara endavant "grafs producte". Hem obtingut fórmules tancades per la dimensió mètrica forta de diverses famílies no trivials de grafs producte que inclouen, per exemple, grafs bipartits, grafs vèrtexs transitius, grafs hamiltonians, arbres, cicles, grafs complets, etc, i hem donat fites inferiors i superiors generals, expressades en termes d'invariants dels grafs factors, com ara, l'ordre, el nombre d'independència, el nombre de cobriment de vèrtexs, el nombre d'aparellament, la connectivitat algebraica, el nombre de cliqué, i el nombre de cliqué lliure de bessons. També hem descrit algunes classes de grafs producte, on s'assoleixen aquestes fites. És conegut que el problema de trobar la dimensió mètrica forta d'un graf connex es pot transformar en el problema de trobar el nombre de cobriment de vèrtexs de la seva corresponent graf de resolubilitat forta. En aquesta tesi hem aprofitat aquesta eina i hem trobat diverses relacions entre el graf de resolubilitat forta de grafs producte i els grafs de resolubilitat forta dels seus factors. Per exemple, és notable destacar que el graf de resolubilitat forta del producte cartesià de dos grafs és isomorf al producte directe dels grafs de resolubilitat forta dels seus factors. / En esta tesis se estudia la dimensión métrica fuerte de grafos producto. Los resultados más importantes de la tesis se centran en la búsqueda de relaciones entre la dimensión métrica fuerte de grafos producto y la de sus factores, junto con otros invariantes de estos factores. Así, se han estudiado los siguientes productos de grafos: producto cartesiano, producto directo, producto fuerte, producto lexicográfico, producto corona, grafos unión, suma cartesiana, y producto raíz, de ahora en adelante "grafos producto". Hemos obtenido fórmulas cerradas para la dimensión métrica fuerte de varias familias no triviales de grafos producto que incluyen, por ejemplo, grafos bipartitos, grafos vértices transitivos, grafos hamiltonianos, árboles, ciclos, grafos completos, etc, y hemos dado cotas inferiores y superiores generales, expresándolas en términos de invariantes de los grafos factores, como por ejemplo, el orden, el número de independencia, el número de cubrimiento de vértices, el número de emparejamiento, la conectividad algebraica, el número de cliqué, y el número de cliqué libre de gemelos. También hemos descrito algunas clases de grafos producto, donde se alcanzan estas cotas. Es conocido que el problema de encontrar la dimensión métrica fuerte de un grafo conexo se puede transformar en el problema de encontrar el número de cubrimiento de vértices de su correspondiente grafo de resolubilidad fuerte. En esta tesis hemos aprovechado esta herramienta y hemos encontrado varias relaciones entre el grafo de resolubilidad fuerte de grafos producto y los grafos de resolubilidad fuerte de sus factores. Por ejemplo, es notable destacar que el grafo de resolubilidad fuerte del producto cartesiano de dos grafos es isomorfo al producto directo de los grafos de resolubilidad fuerte de sus factores. / In this thesis we study the strong metric dimension of product graphs. The central results of the thesis are focused on finding relationships between the strong metric dimension of product graphs and that of its factors together with other invariants of these factors. We have studied the following products: Cartesian product graphs, direct product graphs, strong product graphs, lexicographic product graphs, corona product graphs, join graphs, Cartesian sum graphs, and rooted product graphs, from now on ``product graphs''. We have obtained closed formulaes for the strong metric dimension of several nontrivial families of product graphs involving, for instance, bipartite graphs, vertex-transitive graphs, Hamiltonian graphs, trees, cycles, complete graphs, etc., or we have given general lower and upper bounds, and have expressed these in terms of invariants of the factor graphs like, for example, order, independence number, vertex cover number, matching number, algebraic connectivity, clique number, and twin-free clique number. We have also described some classes of product graphs where these bounds are achieved. It is known that the problem of finding the strong metric dimension of a connected graph can be transformed to the problem of finding the vertex cover number of its strong resolving graph. In the thesis we have strongly exploited this tool. We have found several relationships between the strong resolving graph of product graphs and that of its factor graphs. For instance, it is remarkable that the strong resolving graph of the Cartesian product of two graphs is isomorphic to the direct product of the strong resolving graphs of its factors.