Network monitoring has become a necessity to aid in the management and operation of large networks. Passive network monitoring consists of extracting metrics (or any information of interest) by analyzing the traffic that traverses one or more network links. Extracting information from a high-speed network link is challenging, given the great data volumes and short packet inter-arrival times. These difficulties can be alleviated by using extremely efficient algorithms or by sampling the incoming traffic. This work improves the state of the art in both these approaches. For one-way packet delay measurement, we propose a series of improvements over a recently appeared technique called Lossy Difference Aggregator. A main limitation of this technique is that it does not provide per-flow measurements. We propose a data structure called Lossy Difference Sketch that is capable of providing such per-flow delay measurements, and, unlike recent related works, does not rely on any model of packet delays. In the problem of collecting measurements under the sliding window model, we focus on the estimation of the number of active flows and in traffic filtering. Using a common approach, we propose one algorithm for each problem that obtains great accuracy with significant resource savings. In the traffic sampling area, the selection of the sampling rate is a crucial aspect. The most sensible approach involves dynamically adjusting sampling rates according to network traffic conditions, which is known as adaptive sampling. We propose an algorithm called Cuckoo Sampling that can operate with a fixed memory budget and perform adaptive flow-wise packet sampling. It is based on a very simple data structure and is computationally extremely lightweight. The techniques presented in this work are thoroughly evaluated through a combination of theoretical and experimental analysis.

Avui dia, estam assistint a un increment important en el coneixement i en la introducció de les Tecnologies de la Informació i les Comunicacions (TIC) en la societat. De cada dia més i més gent acull les noves formes de consumir béns i serveis electrònics a través de l’ús de les noves infrastuctures TIC, típicament relacionades en escenaris mòbils. El nombre de dispositius mòbils sempre connectats ha experimentat un gran increment degut a la promoció de subscripcions de banda ampla mòbil que permeten als usuaris accedir a la informació quan volen i allà on volen, fins i tot amb models de consum d’informació a temps real. És justament en aquest escenari de mobilitat on moltes àrees de negoci poden rebre excel·lents beneficis de l’increment de l’ús de les TIC. Un d’aquests camps és el comerç electrònic. De fet, d’acord amb un estudi recent de prospecció de mercat, les ventes relacionades amb el comerç electrònic (especialment en el mercat Business to Customer (B2C)) augmentaran globalment a un ritme d’entre el 10% i el 15% des del 2012 fins al 2017. A més, l’estudi també apunta que la gent estirà de cada vegada més acostumada a fer ús dels seus dispositius mòbils per accedir a serveis electrònics relacionats amb el comerç electrònic. No obstant, la gent també exigeix certs nivells de privacitat per a confiar més i estar més actius en l’ús del comerç electrònic. Encara que actualment el comerç electrònic és un tema molt important i molta gent està ja familiaritzada amb ell, encara li resta un llarg camí per recórrer. Com s’ha dit anteriorment, una de les majors preocupacions dels consumidors i dels venedors és la falta de privacitat i confiança quan fan ús d’Internet, i especialment quan han de realitzar compres a la xarxa o han d’accedir a serveis electrònics. De fet, aquesta és la premisa que ha motivat la recerca recollida en aquesta Tesi. Llavors, l’objectiu d’aquesta Tesi és el de proposar noves i millors solucions que protegeixin la privacitat dels actors implicats per a tractar de resoldre algunes mancances del comerç electrònic i d’aquesta forma incrementar la privacitat, la seguretat i la confiança per accelerar encara més la utilització del comerç electrònic. Entre tots els temes que composen el comerç electrònic, en aquesta Tesi es tracten tres serveis que sofreixen aquesta falta de privacitat i confiança per part dels consumidors i dels venedors: el pagament a canvi de compres de petit valor, l’ús de cupons electrònics que normalment associen algun tipus de descompte o regal i el tíquets electrònics per accedir a serveis a canvi d’una tarifa basada en l’ús que se li ha donat al servei. Per tant, en la Tesi es proposen tres noves solucions per a protegir la privacitat dels tres serveis abans esmentats. Les solucions aportades s’han definit per mitjà de models funcionals i de seguretat formals i s’han provat que són segurs després de verificar-ne la seva seguretat d’acord amb les propietats requerides en cada cas. Encara que l’objectiu principal de la Tesi giri al voltant de la proposta teòrica de noves solucions que protegeixin la seguretat, també és important remarcar que les solucions també han de ser pràctiques i eficients per a poder implementar-les i després usarles en dispositius mòbils actuals. Llavors, el treball que ha conduit a la realització d’aquesta Tesi també inclou el desenvolupament d’implementacions funcionals de les solucions proposades i l’anàlisi del rendiment obtingut sobre dispositius mòbils actuals. / Nowadays, we are witnessing an important increase in the knowledge and the introduction rate of Information Communications Technologies (ICT) in society. Day after day, there are more and more people embracing new means to consume electronic goods or services through the utilization of these new ICT infrastructures, usually related to mobile scenarios. The number of always connected mobile devices has experienced an important growth due to the release of mobile broadband subscriptions that allow users to access information where and when they want, even with real-time data consumption patterns. In this mobility scenario, there are many business areas that can receive excellent benefits from the increasing use of ICTs. One of these fields is electronic commerce (e-commerce). In fact, according to a recent forecast research, sales due to e-commerce (specially the Business to Customer (B2C) market), will rise globally at an annual rate of between 10% and 15% from 2012 to 2017. Besides, the study also points out that people are more likely to use their mobile devices to access e-commerce services. However, people also want to achieve certain levels of privacy to be more confident and active with e-commerce. Despite the fact that e-commerce currently is an important topic and that many people are already familiarized with it, e-commerce still has a long way to go. As introduced before, one of the main concerns of customers and merchants is the lack of privacy and trust when they browse Internet, and especially when they have to do on-line purchases or have to access electronic services. Indeed, this is the underlying premise that motivates the research gathered in this dissertation. Therefore, the objective of this dissertation is to propose new and improved privacy-protecting solutions to address some unresolved deficiencies in the e-commerce field to increase privacy, security and trust that would accelerate even more the use of e-commerce by society. Among all topics within the e-commerce field, this dissertation deals with three services that may suffer this lack of privacy and trust from customers and merchants: payment of low value purchases, use of electronic coupons (typically associated to some discounts or gifts) and electronic ticketing to access services in exchange for a fare based on the given use. Thus, the dissertation proposes three new privacy-protecting solutions that cover the aforementioned e-commerce tools. Solutions are defined by formal functional and security models and proved secure by means of a security verification according to the required security properties. Although the main objective of this dissertation revolves around the theoretical proposal of new privacy-protecting solutions, it is also important to note that they should be proved practical and efficient to be implemented and afterward used by current mobile devices. So, the work that conducts to this dissertation addresses also the development of functional implementations of proposed privacy-protecting solutions and their performance evaluation on current mobile devices.

L’objectiu d’aquesta recerca és observar com s’estableixen i quins són els usos orals en una aula de P3, és a dir, amb alumnes de 3 a 4 anys. La tria d’aquesta edat no ha estat una decisió arbitrària. Des d’un punt de vista sociolingüístic és una etapa rellevant perquè la investigació en un grup-classe des del moment que es constitueix permet analitzar com es construeixen i es resolen les negociacions de codi. Una part molt considerable de les investigacions lingüístiques amb infants giren a l’entorn de l’adquisició dels aspectes fonètics, lèxics i morfosintàctics, i només d’una manera més tangencial dels aspectes referits a les tries lingüístiques entre iguals i a la reproducció de les normes de les llengües. En aquest estudi, però, es deixa de banda el primer àmbit i es descriuen tres aspectes relacionats amb els usos orals dins de l’aula. En primer lloc s’analitzen les normes lingüístiques tutoritzades, això és, les pràctiques lingüístiques que posa en circulació el personal docent amb els alumnes. En segon terme s’observa en quina llengua els alumnes resolen les interaccions intra- i intergrupals en situacions quasiespontànies. I finalment s’exposa com en aquestes mateixes situacions els infants negocien el codi d’interacció en les seves converses entre iguals. Bona part de l’anàlisi es posa en relació amb les xarxes socials, una variable que al llarg de nombrosos estudis ha demostrat tenir un gran potencial a l’hora d’explicar el comportament sociolingüístic de les persones. Aquest és el fonament del cinquè capítol, dedicat a presentar els resultats obtinguts. La resta de la tesi s’organitza en els apartats que es descriuen a continuació. El primer aporta la perspectiva teòrica de les tries de llengües. L’estudi de les tries lingüístiques ha conegut dues grans tradicions: la macrosocial i la microsocial-interaccional. La primera entén que les tries no són producte d’una decisió (totalment) lliure del parlant, sinó que a nivell supraindividual hi ha una sèrie d’institucions que n’influeixen el comportament lingüístic. En canvi, la perspectiva interaccional concentra la seva atenció en el parlant i deixa de banda la pressió que es pugui exercir des de les institucions. Diversos autors han apuntat mancances a l’hora d’arribar a una comprensió holística de les tries de llengües només a partir de la dicotomia entra una i altra tradició. Per aquest motiu, en aquesta recerca s’ha optat per les xarxes socials com a constructe teòric capaç d’establir ponts explicatius entre els factors politicosocials que afecten el manteniment o substitució lingüístics i les motivacions de tria lingüística en interaccions locals. El segon capítol ressegueix la presència del català a l’escola, des de la Transició fins a l’actualitat. L’apartat històric deixa pas, en la darrera part del capítol, a l’anàlisi del coneixement i usos del català i castellà en els escolars catalans a partir de l’escrutini de diversos informes i estudis de caire macrosocial. El tercer capítol està dedicat a presentar les capacitats lingüístiques que desenvolupen els infants entre els 3 i 4 anys, a partir de l’adquisició de les habilitats lèxiques, fonètiques i morfosintàctiques. El quart capítol té com a objectiu presentar la metodologia de la recollida de dades i el seu posterior tractament. Al llarg d’aquestes pàgines s’exposen els motius pels quals s’ha optat per l’observació participant com la tècnica més adequada per obtenir dades de qualitat. També es fa referència als condicionants sociolingüístics de l’entorn de l’escola, del mateix centre i de l’aula, i s’expliciten les vies que es van seguir per accedir als informants. Finalment, es descriu el procés de transcripció de les dades. El capítol que clou la tesi presenta les principals conclusions del treball. / This thesis examines the language of interaction and the way it is deployed among a group of children aged 3-4 in an early childhood center located in Barcelona. More specifically, the first part of the analysis is focused on tutored linguistic behavior, based on interactions organized as a class activity and directly supervised by teachers. Secondly, children’s language interactions are observed in intra-group and extra-group conversations in semi-spontaneous situations. Finally, it is revealed how, under these same circumstances, children negotiate the code of interaction in peer to peer dialogues. An important part of the analysis is related to social networks, a variable which is highly useful to explain sociolinguistic behavior as has been demonstrated in a large number of studies. In addition to the chapter devoted to data analysis, the thesis is organized in five other sections. The first one has to do with the theoretical perspectives of language choices. Two main traditions are described at this point: the macro-social and the micro-interactional. Why these traditions cannot convey holistic understanding about language choices is discussed. Thus, this research is based on social networks as the theoretical construct capable of building bridges between sociopolitical factors related to language maintenance or shift and the reasons for a specific language choice in local interactions. The second chapter deals with the sociopolitical struggle to reintroduce Catalan in schools from the late 1960’s since the beginning of the XXIst century. Furthermore, several studies are examined to shed light on Catalan students’ levels of knowledge and use of Catalan and Spanish. The third and fourth chapters are dedicated to exploring language acquisition in children aged 3-4, and to describing methodology respectively. Regarding the latter, participant observation is justified as the most suitable technique to achieve quality data. An explanation is made as to how the researcher gained access to informants, as well as the process of data transcription. In the last chapter the main conclusions of the research are shown.

La teoria evolutiva té com a objectiu explicar la diversitat i disparitat dels organismes vius. Aquesta estableix que les poblacions tenen variabilitat fenotípica heredable que en el medi afecta la contribució relativa dels diferents individus d'una població en la següent generació. A més, la teoria estableix que aquest procés s afectat per dependències històriques i fenòmens atzarosos com ara la deriva gènica. La causa última de la variació fenotípica rau en mutacions que són essencialment atzaroses (malgrat més probables en certes regions del DNA). Això, però, no explica quin tipus de variacions morfològiques són possibles en un llinatge concret. De fet, la teoria Darwinista ens ajuda a entendre com diferents variants en les poblacions es substitueixen unes a altres però no com o perquè apareixen unes variacions o unes altres (excepte a nivell molecular). L'objectiu d'aquesta tesi és introduir certs aspectes de com el desenvolupament funciona per tal de que la teoria evolutiva, o una variant d'aquesta, tingui un cert poder predictiu sobre l'estructura del fenotip. A part, això, pot ajudar a entendre quins factors, i com, afecten la evolució dels metazous. El desenvolupament és també un producte de l'evolució. Fent el que acabem d'esmentar també aconseguim desenvolupar un marc teòric que ens permeti estudiar evolució i desenvolupament unificadament.

La Teoria de Sistemes Dinàmics proporciona eines per a l'anàlisi de Sèries Temporals (ST). Una de les eines proposada es porta a terme mitjançant la predicció no lineal de ST. Amb aquesta tècnica podem extreure algunes de les característiques que aquesta teoria proposa,com la Dimensió d'Immersió (DI) o la Sensibilitat a les Condicions Inicials (SCI). Sugihara y May(1990) han difós un mètode no paramètric que permet fer prediccions mitjançant l'observació de gràfics, procediment que creiem que afegeix una component de subjectivitat. Per superar aquesta dificultat proposem realitzar la presa de decisions mitjançant inferència estadística.El mètode que s'exposa en aquesta tesi es basa en la predicció no lineal amb Xarxes Neuronals Artificials (XNA). Hem realitzat un seguit d'experiments de simulació per estimar la DI i avaluar la SCI entrenant XNA. En el primer cas es pretén trobar un invariant en la predicció en funció del nombre de components de l'atractor reconstruït, a partir d'una ST observada. Aquest coincideix amb el valor de la DI en el que la predicció ja no millora encara que augmenti el nombre de components. En el segon cas, un cop entrenada la XNA, s'analitza si existeix una disminució significativa de la precisió en la predicció en funció del nombre d'iteracions d'aquesta. Si es dóna aquesta disminució es conclou que la ST és sensible a les condicions inicials. Per tal de provar aquesta nova tècnica que he proposat, he emprat ST simulades (component x del mapa de Hénon i de l'atractor de Rössler) sense soroll i amb dos nivells de soroll afegit. Per al primer conjunt de dades els resultats són consistents amb les nostres hipòtesis. D'altra banda, els resultats per a les dades de l'atractor de Rössler no són tan satisfactoris com era d'esperar en les nostres prediccions. / Researchers from Dynamical Systems Theory have developed tools for the analysis of Time Series (TS) data. Some of these, based on nonlinear forecasting, allow us to estimate some of the characteristics proposed under this approach like embedding dimension or sensitive dependence on initial conditions. Sugihara and May (1990) have shown a nonparametric forecasting method to assess these magnitudes based on the observation of graphics. This process is too subjective in the case where the results are not sufficiently clear. For this reason the goal of this investigation was to find a method of estimation based on statistical inference.Some simulation experiments have been developed to achieve more objective estimations of the embedding dimension and the assessment of sensitivity to initial conditions. The forecasting of TS in this dissertation has been performed using artificial neural networks. The set of experiments to estimate dimensionality are designed to find an invariant of the correct performance, as a function of the number of components of the reconstructed attractor. To asses the sensitivity to the initial conditions, the experiments will allow us to study the forecasting performance of the best trained network, as a function of the number of iterations.To test the experiments proposed we have used the Hénon and the Rössler data sets with different noise levels. The results show a good performance of the method used for the Hénon data set. On the other hand, the results for the Rössler data sets are not consistent with our hypotheses.

The research we have conducted has been aimed at developing a new mechanism of extraction and use of parallelism at a high level, based on speculation techniques, in cluster environments. This allows our mechanism to be architecture independent and to be adapted to heterogeneous environments. As a drawback there are some limitations due to the fact of working at a high level, such as memory address access dependencies and those occurring in vector operations. The Master/Slave Speculative Parallelization Architecture for Computer Clusters (MSSPACC) is considered that works at the TLP taking advantage of the execution tools of the ILP level. It works at TLP level because the program is divided into threads which we call blocks. The blocks they are considered like single instructions and follow the same pattern of a superscalar processor ILP (input variables are considered like operands and the output like the result of the execution). / L’objectiu d’aquesta recerca és desenvolupar un nou mecanisme d'extracció i explotació del paral•lelisme basat en tècniques d'especulació a nivell d’aplicació sobre clústers. Així hem aconseguit que el sistema no tingui una dependència arquitectònica i poder adaptar-se a entorns heterogenis. Com a contrapartida ens hem trobat amb les limitacions degudes al fet de treballar a nivell d’aplicació, com són les dependències d’adreces d’accés a memòria i les provocades en operacions amb vectors. La proposta desenvolupada s’anomena Master/Slave Speculative Parallelization Architecture for Computer Clusters (MSSPACC) i es pot considerar que treballa a nivell TLP aprofitant les eines d’execució del nivell ILP. Divideix el programa en fils d’execució que anomenem blocs bàsics que s’executen seguint el mateix patró ILP d’un processador Superescalar, considerant que un bloc bàsic és equivalent a una instrucció, les variables d’entrada com a operants i les de sortida com al resultat de l’execució del bloc bàsic.

de la memòriaEn aquest estudi es consideren aspectes teòrics i pràctics del modelatge de sistemes no lineals mitjançant xarxes neuronals modulars.A la vessant teòrica s'ha proposat un model que aprofita les avantatges de les xarxes neuronals i minimitza els seus inconvenients, permetent interpretar físicament els resultats i afegir coneixement previ per accelerar el procés de modelatge. Es tracta de les xarxes de mòduls neuronals.Un mòdul neuronal és una xarxa neuronal que aprofita l'ús de restriccions estructurals per forçar un tipus de comportament al model. Aquest concepte s'ha creat a propòsit en aquest estudi, recolzat per l'argument de que les restriccions topològiques constitueixen un mètode més versàtil i efectiu que el propi mecanisme d'aprenentatge per facilitar comportaments desitjats en una xarxa neuronal.D'aquesta forma, una vegada aplicat el procés de identificació, el model resultant és una xarxa neuronal composada per mòduls, cadascun dels quals representa un bloc funcional del sistema amb un significat fàcilment interpretable.Donat que els mòduls neuronals són paradigmes nous dins de l'àmbit de les xarxes neuronals, s'ha proposat una sèrie de pautes pel seu disseny i es descriu un conjunt de mòduls neuronals format per nou no linealitats dures i els sistemes lineals sense restricció d'ordre.També s'ha realitzat un estudi formal en el que s'han caracteritzat els sistemes que es poden aproximar mitjançant xarxes de mòduls neuronals, el conjunt ?NM, i s'ha establert una cota de l'error d'aquesta aproximació. Aquest resultat és fonamental perquè assenta una base sòlida per plantejar el modelatge de sistemes no lineals amb xarxes de mòduls neuronals. En ell es demostra que, com més precisa sigui l'aproximació de les diferents parts del sistema, més precisa serà l'aproximació del sistema global.Des del punt de vista pràctic, es consideren els aspectes de creació i optimització del model proposat.Primerament, i donat que es tracta d'una xarxa neuronal, es repassen els mecanismes existents a la literatura per adaptar els paràmetres del model al problema. En aquest sentit, s'ha dissenyat un algoritme d'aprenentatge específic per les xarxes neuronals modulars, el modular backpropagation, el cost computacional del qual comparat amb altres algoritmes clàssics, és menor en estructures modulars.Es descriu també una eina de modelització dissenyada a propòsit com mètode per crear i optimitzar, de forma automàtica, xarxes de mòduls neuronals. Aquesta eina combina la programació evolutiva, algoritmes clàssics d'aprenentatge neuronal i el gestor d'aprenentatge, modular backpropagation, amb la finalitat de resoldre problemes de modelització de sistemes no lineals mitjançant xarxes de mòduls neuronals.Finalment, es proposa un esquema del procés de modelització de sistemes no lineals utilitzant les eines desenvolupades en aquest estudi. S'ha creat una aplicació que permet sistematitzar aquest procés i s'ha obtingut els models de tres sistemes no lineals per comprovar la seva utilitat. Els problemes que s'han sotmès al procés de modelització amb xarxes neuronals són: un motor de corrent continu, un sistema no lineal amb histèresi i un element piezoelèctric. En els tres casos s'ha arribat a una solució satisfactòria que permet confirmar la utilitat de les eines desenvolupades en aquest estudi. / This work is concerned with theoretical and applied aspects of nonlinear system modelling with modular neural networks.From the theoretical viewpoint, a new model is proposed. This model attempts to combine the capabilities of neural networks for nonlinear function approximation with the structural organisation of classical block oriented techniques for system modelling and identification. This model is the Neural Module (NM).A neural module is a neural network that behaves inherently like a function or family of functions. The specified behaviour is forced with the use of topological restrictions in the network. The neural module is a new concept developed upon the argument that topological restrictions is a much more versatile and effective way of facilitating a specific behaviour in a neural network than the learning mechanism itself.Once the learning process finishes, the resulting model is a neural network composed by modules. Each module is supposed to model a functional element of the system, with an easy to understand meaning.As long as the neural module is a new paradigm in the neural network domain, rules and guidelines are given for their design. A set of neural modules with nine hard nonlinearities and the linear systems is also described.The set of dynamic systems that can be approximated using neural modules, called SNM, is formally described. The approximation error between en element of SNM and its neural model is calculated and found bounded. This is a basic result that sets up a firm base from which neural module modelling could be considered as a useful type of model.From the practical viewpoint, creation and optimisation aspects of the proposed model are considered.First of all, some of the classical rules of parameter adaptation in neural networks are reviewed. In order to allow modular networks to learn more efficiently, a specific learning algorithm is introduced. This is the modular backpropagation (MBP) algorithm. The computational cost of MPB is less than the cost of classical algorithms when they are applied to modular structures.A modelling tool, specially designed for the automatic creation and optimisation of modular neural networks, is also described. This tool combines Evolutionary Programming, classical neural learning algorithms and the learning manager, MBP. This tool is aimed at solving nonlinear modelling problems with the use of modular neural networks.Finally, an outline of the modelling process with the tools developed in this work is given. This process is applied to the modelling and identification of three nonlinear systems, which are: a dc motor, a nonlinear system with hysteresis, and a piezoelectric element. The three cases are modelled satisfactorily and the usefulness of the framework presented is confirmed.

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.

Tal i com indica el seu títol, la present memòria de tesi té com objecte d'estudi el desenvolupament d'algorismes i implementacions eficients per resoldre el problema conegut dins del món de l'Optimització i Investigació Operativa com a problema de fluxos multiarticle en xarxa. Com es desprèn del seu nom, és un problema d'optimització en xarxa on, a diferència del problema clàssic uniarticle, diversos productes (els articles) comparteixen el mateix canal físic (la xarxa) sense poder ser combinats entre ells. Això provoca que sigui necessària una replicació de les variables -fluxos en cada arc- de la xarxa original, tantes vegades com articles hi ha, el qual incrementa considerablement el nombre de variables i constriccions a ser tractades.L'optimització de fluxos en xarxes multiarticle és un problema ben conegut, i durant anys diverses aplicacions reals han estat modelitzades mitjançant aquesta tècnica. Alhora, és un problema molt costós des d'un punt de vista computacional, donat el gran nombre de variables i equacions que intervenen com abans s'ha esmentat. Aquest doble fet (el seu interès per solucionar problemes reals i el seu elevat cost) ha motivat l'estudi i desenvolupament de tècniques per tractar-lo de forma específica. Sovint, però, aquest esforç ha conduït a la formulació de diversos algorismes però rarament ha donat lloc a implementacions de caràcter pràctic. Amb això que acabem de dir queda clar que suposarem que hi ha una clara distinció entre el que és algorisme i el que és implementació, tot i que sovint és difícil decidir on hi ha la frontera entre un i altre concepte. En general, per algorisme entendrem la seqüència de processos que s'han de seguir per tal d'aconseguir un cert objectiu, mentre que la implementació fa referència a com, en última instància, s'han dut a la pràctica. Des d'aquest punt de vista es podria dir que un algorisme té moltes implementacions, però que una implementació només respon a un únic algorisme. S'ha cregut convenient fer una breu discussió sobre els conceptes d'algorisme i implementació, donat que al treball aquí presentat ambdós tenen un pes específic. Al treball desenvolupat no s'ha pretès només detallar com modificar, ampliar o obtenir algorismes per solucionar el problema de fluxos multiarticle, sinó que a més s'ha plantejat com objectiu prioritari l'obtenció d'implementacions el més eficients i robustes possibles. Vista així, la tasca desenvolupada es troba a cavall entre dos camps com ara la Investigació Operativa i la Informàtica. També cal tenir present que en aquesta memòria es presentarà detalladament tot el que faci referència a la part algorísmica però no tant a nivell d'implementació. Això implicaria haver de descriure una gran quantitat d'estructures de dades i una gran quantitat de rutines desenvolupades i altres usades de llibreries numèriques estàndard. Tanmateix, això no ha de fer oblidar que la major part de l'esforç necessari ha estat dedicat a l'obtenció i disseny d'aquestes rutines i estructures de dades. I el fet de que tot aquest treball quedi plasmat en només l'obtenció d'una sèrie de taules amb valors numèrics no ha de fer oblidar la gran quantitat de feina no descrita que hi ha darrera d'aquests resultats.Un cop s'ha definit el marc on es troba el treball realitzat, procedirem a definir amb més detall els objectius que s'han perseguit i les aportacions que representa respecte el que fins ara s'havia fet. Finalitzarem la introducció amb una breu descripció sobre com ha estat estructurada aquesta memòria.

During the last decades, it has become clear that systems formed by many interacting parts show emergent dynamical properties which are inherently related to the topology of the underlying pattern of connections among the constituent parts. Such systems, usually known as complex systems, are in general suitably described through their networks of contacts, that is, in terms of nodes (representing the system's components) and edges (standing for their interactions), which allows to catch their essential features in a simple and general representation. In recent years, increasing interest on this approach, thanks also to a favorable technological progress, led to the accumulation of an increasing amount of data. This situation has allowed the arising of new questions and, therefore, the diversification of the scientific work. Among them, we can point out three general issues that have been receiving a lot of interest: (i) is the available information always reliable and complete? (ii) how does a complex interaction pattern affect the emergence of collective behavior in complex systems? And (iii) which is the role of mobility within the framework of complex networks? This thesis has been developed along these three lines, which are strictly interrelated. We expand on three case-studies, each one of which deals with two the above mentioned macro-issues. We consider the issue of the incompleteness of the available information both in the case of natural (Chapter 2) and artificial (Chapter 3) networks. As a paradigmatic emergent behavior, we focus on the synchronization of coupled phase oscillators (Chapter 2 and Chapter 4), deeply investigating how different patterns of connections can affect the achievement of a globally coherent state. Finally, we include moving agents in two different frameworks, using them as explorers of unknown networks (Chapter 3) and considering them as interacting units able to establish connections with their neighbors (Chapter 4). In Chapter 2, we study the problem of the reconstruction of an unknown interaction network, whose nodes are Kuramoto oscillators. Our aim is to extract topological features of the connectivity pattern from purely dynamical measures, based on the fact that in a heterogeneous network the global dynamics is not only affected by the distribution of the natural frequencies but also by the location of the different values. The gathered topological information ranges from local features, such as the single node connectivity, to the hierarchical structure of functional clusters, and even to the entire adjacency matrix. In Chapter 4, instead, we present a model of integrate and fire oscillators that are moving agents, freely displacing on a plane. The phase of the oscillators evolves linearly in time and when it reaches a threshold value they fire at their neighbors. In this way, the interaction network is a dynamical object by itself since it is re-created at each time step by the motion of the units. Depending on the velocity of the motion, the average number of neighbors, the coupling strength and the size of the agents population, we identify different regimes. Moving agents are employed also in Chapter 3 where they play the role of explorers of unknown artificial networks, having the mission to recover information about their structures. We propose a model in which random walkers with previously assigned home nodes navigate through the network during a fixed amount of time. We consider that the exploration is successful if the walker gets the information gathered back home, otherwise, no data is retrieved. We show that there is an optimal solution to this problem in terms of the average information retrieved and the degree of the home nodes and design an adaptive strategy based on the behavior of the random walker. / Durante las últimas décadas, se ha empezado a poner de manifiesto que sistemas formados por muchos elementos en interacción pueden mostrar propiedades dinámicas emergentes relacionadas con la topología del patrón de conexiones entre las partes constituyentes. Estos sistemas, generalmente conocidos como sistemas complejos, en muchos casos pueden ser descritos a través de sus redes de contactos, es decir, en términos de nodos (que representan los componentes del sistema) y de enlaces (sus interacciones). De esta manera es posible capturar sus características esenciales en una representación simple y general. En esta última década, el creciente interés en este enfoque, gracias también a un progreso tecnológico favorable, ha llevado a la acumulación de una cantidad ingente de datos. Eso, a su vez, ha permitido el surgimiento de nuevas preguntas y, por lo tanto, la diversificación de la actividad científica. Entre ellas, podemos destacar tres cuestiones generales que son objeto de mucho interés: (i) ¿la información disponible es siempre fiable y completa? (ii) ¿cómo un patrón de interacción complejo puede afectar el surgimiento de comportamientos colectivos? Y (iii) ¿cual es el papel de la movilidad en el marco de las redes complejas? Esta tesis se ha desarrollado siguiendo estas tres líneas, que están íntimamente relacionadas entre sí. Hemos profundizado en tres casos de estudio, cada uno de los cuales se ocupa de dos de los macro-temas mencionados. Consideramos la cuestión del carácter incompleto de la información disponible tanto en el caso de redes naturales (Capítulo 2) como de redes artificiales (Capítulo 3). Nos centramos en la sincronización de los osciladores de fase acoplados (Capítulos 2 y 4) en cuanto comportamiento emergente paradigmático, investigando en profundidad cómo los diferentes patrones de conexión puedan afectar la consecución de un estado coherente a nivel global. Por último, analizamos el rol de la movilidad incluyendo agentes móviles en dos marcos diferentes. En un caso, los utilizamos como exploradores de redes desconocidas (Capítulo 3), mientras que en otro los consideramos como unidades que interaccionan y son capaces de establecer conexiones con sus vecinos (Capítulo 4).