Behavioural queueing : cellular automata and a laboratory experiment

Dans cette thèse, nous étudions les aspects comportementaux d'agents qui interagissent dans des systèmes de files d'attente à l'aide de modèles de simulation et de méthodologies expérimentales. Chaque période les clients doivent choisir un prestataire de servivce. L'objectif est d'analyser l'impact des décisions des clients et des prestataires sur la formation des files d'attente. Dans un premier cas nous considérons des clients ayant un certain degré d'aversion au risque. Sur la base de leur perception de l'attente moyenne et de la variabilité de cette attente, ils forment une estimation de la limite supérieure de l'attente chez chacun des prestataires. Chaque période, ils choisissent le prestataire pour lequel cette estimation est la plus basse. Nos résultats indiquent qu'il n'y a pas de relation monotone entre le degré d'aversion au risque et la performance globale. En effet, une population de clients ayant un degré d'aversion au risque intermédiaire encoure généralement une attente moyenne plus élevée qu'une population d'agents indifférents au risque ou très averses au risque. Ensuite, nous incorporons les décisions des prestataires en leur permettant d'ajuster leur capacité de service sur la base de leur perception de la fréquence moyenne d'arrivées. Les résultats montrent que le comportement des clients et les décisions des prestataires présentent une forte "dépendance au sentier". En outre, nous montrons que les décisions des prestataires font converger l'attente moyenne pondérée vers l'attente de référence du marché. Finalement, une expérience de laboratoire dans laquelle des sujets jouent le rôle de prestataire de service nous a permis de conclure que les délais d'installation et de démantèlement de capacité affectent de manière significative la performance et les décisions des sujets. En particulier, les décisions du prestataire, sont influencées par ses commandes en carnet, sa capacité de service actuellement disponible et les décisions d'ajustement de capacité qu'il a prises, mais pas encore implémentées. - Queuing is a fact of life that we witness daily. We all have had the experience of waiting in line for some reason and we also know that it is an annoying situation. As the adage says "time is money"; this is perhaps the best way of stating what queuing problems mean for customers. Human beings are not very tolerant, but they are even less so when having to wait in line for service. Banks, roads, post offices and restaurants are just some examples where people must wait for service. Studies of queuing phenomena have typically addressed the optimisation of performance measures (e.g. average waiting time, queue length and server utilisation rates) and the analysis of equilibrium solutions. The individual behaviour of the agents involved in queueing systems and their decision making process have received little attention. Although this work has been useful to improve the efficiency of many queueing systems, or to design new processes in social and physical systems, it has only provided us with a limited ability to explain the behaviour observed in many real queues. In this dissertation we differ from this traditional research by analysing how the agents involved in the system make decisions instead of focusing on optimising performance measures or analysing an equilibrium solution. This dissertation builds on and extends the framework proposed by van Ackere and Larsen (2004) and van Ackere et al. (2010). We focus on studying behavioural aspects in queueing systems and incorporate this still underdeveloped framework into the operations management field. In the first chapter of this thesis we provide a general introduction to the area, as well as an overview of the results. In Chapters 2 and 3, we use Cellular Automata (CA) to model service systems where captive interacting customers must decide each period which facility to join for service. They base this decision on their expectations of sojourn times. Each period, customers use new information (their most recent experience and that of their best performing neighbour) to form expectations of sojourn time at the different facilities. Customers update their expectations using an adaptive expectations process to combine their memory and their new information. We label "conservative" those customers who give more weight to their memory than to the xiv Summary new information. In contrast, when they give more weight to new information, we call them "reactive". In Chapter 2, we consider customers with different degree of risk-aversion who take into account uncertainty. They choose which facility to join based on an estimated upper-bound of the sojourn time which they compute using their perceptions of the average sojourn time and the level of uncertainty. We assume the same exogenous service capacity for all facilities, which remains constant throughout. We first analyse the collective behaviour generated by the customers' decisions. We show that the system achieves low weighted average sojourn times when the collective behaviour results in neighbourhoods of customers loyal to a facility and the customers are approximately equally split among all facilities. The lowest weighted average sojourn time is achieved when exactly the same number of customers patronises each facility, implying that they do not wish to switch facility. In this case, the system has achieved the Nash equilibrium. We show that there is a non-monotonic relationship between the degree of risk-aversion and system performance. Customers with an intermediate degree of riskaversion typically achieve higher sojourn times; in particular they rarely achieve the Nash equilibrium. Risk-neutral customers have the highest probability of achieving the Nash Equilibrium. Chapter 3 considers a service system similar to the previous one but with risk-neutral customers, and relaxes the assumption of exogenous service rates. In this sense, we model a queueing system with endogenous service rates by enabling managers to adjust the service capacity of the facilities. We assume that managers do so based on their perceptions of the arrival rates and use the same principle of adaptive expectations to model these perceptions. We consider service systems in which the managers' decisions take time to be implemented. Managers are characterised by a profile which is determined by the speed at which they update their perceptions, the speed at which they take decisions, and how coherent they are when accounting for their previous decisions still to be implemented when taking their next decision. We find that the managers' decisions exhibit a strong path-dependence: owing to the initial conditions of the model, the facilities of managers with identical profiles can evolve completely differently. In some cases the system becomes "locked-in" into a monopoly or duopoly situation. The competition between managers causes the weighted average sojourn time of the system to converge to the exogenous benchmark value which they use to estimate their desired capacity. Concerning the managers' profile, we found that the more conservative Summary xv a manager is regarding new information, the larger the market share his facility achieves. Additionally, the faster he takes decisions, the higher the probability that he achieves a monopoly position. In Chapter 4 we consider a one-server queueing system with non-captive customers. We carry out an experiment aimed at analysing the way human subjects, taking on the role of the manager, take decisions in a laboratory regarding the capacity of a service facility. We adapt the model proposed by van Ackere et al (2010). This model relaxes the assumption of a captive market and allows current customers to decide whether or not to use the facility. Additionally the facility also has potential customers who currently do not patronise it, but might consider doing so in the future. We identify three groups of subjects whose decisions cause similar behavioural patterns. These groups are labelled: gradual investors, lumpy investors, and random investor. Using an autocorrelation analysis of the subjects' decisions, we illustrate that these decisions are positively correlated to the decisions taken one period early. Subsequently we formulate a heuristic to model the decision rule considered by subjects in the laboratory. We found that this decision rule fits very well for those subjects who gradually adjust capacity, but it does not capture the behaviour of the subjects of the other two groups. In Chapter 5 we summarise the results and provide suggestions for further work. Our main contribution is the use of simulation and experimental methodologies to explain the collective behaviour generated by customers' and managers' decisions in queueing systems as well as the analysis of the individual behaviour of these agents. In this way, we differ from the typical literature related to queueing systems which focuses on optimising performance measures and the analysis of equilibrium solutions. Our work can be seen as a first step towards understanding the interaction between customer behaviour and the capacity adjustment process in queueing systems. This framework is still in its early stages and accordingly there is a large potential for further work that spans several research topics. Interesting extensions to this work include incorporating other characteristics of queueing systems which affect the customers' experience (e.g. balking, reneging and jockeying); providing customers and managers with additional information to take their decisions (e.g. service price, quality, customers' profile); analysing different decision rules and studying other characteristics which determine the profile of customers and managers.

Gene Ontology Function prediction in Mollicutes using Protein-Protein Association Networks

Abstract Background: Many complex systems can be represented and analysed as networks. The recent availability of large-scale datasets, has made it possible to elucidate some of the organisational principles and rules that govern their function, robustness and evolution. However, one of the main limitations in using protein-protein interactions for function prediction is the availability of interaction data, especially for Mollicutes. If we could harness predicted interactions, such as those from a Protein-Protein Association Networks (PPAN), combining several protein-protein network function-inference methods with semantic similarity calculations, the use of protein-protein interactions for functional inference in this species would become more potentially useful. Results: In this work we show that using PPAN data combined with other approximations, such as functional module detection, orthology exploitation methods and Gene Ontology (GO)-based information measures helps to predict protein function in Mycoplasma genitalium. Conclusions: To our knowledge, the proposed method is the first that combines functional module detection among species, exploiting an orthology procedure and using information theory-based GO semantic similarity in PPAN of the Mycoplasma species. The results of an evaluation show a higher recall than previously reported methods that focused on only one organism network.

Evolution of Coordination in Social Networks: A Numerical Study

Coordination games are important to explain efficient and desirable social behavior. Here we study these games by extensive numerical simulation on networked social structures using an evolutionary approach. We show that local network effects may promote selection of efficient equilibria in both pure and general coordination games and may explain social polarization. These results are put into perspective with respect to known theoretical results. The main insight we obtain is that clustering, and especially community structure in social networks has a positive role in promoting socially efficient outcomes.

Learning about Bayesian networks for forensic interpretation : An example based on the "the problem of multiple propositions"

Both, Bayesian networks and probabilistic evaluation are gaining more and more widespread use within many professional branches, including forensic science. Notwithstanding, they constitute subtle topics with definitional details that require careful study. While many sophisticated developments of probabilistic approaches to evaluation of forensic findings may readily be found in published literature, there remains a gap with respect to writings that focus on foundational aspects and on how these may be acquired by interested scientists new to these topics. This paper takes this as a starting point to report on the learning about Bayesian networks for likelihood ratio based, probabilistic inference procedures in a class of master students in forensic science. The presentation uses an example that relies on a casework scenario drawn from published literature, involving a questioned signature. A complicating aspect of that case study - proposed to students in a teaching scenario - is due to the need of considering multiple competing propositions, which is an outset that may not readily be approached within a likelihood ratio based framework without drawing attention to some additional technical details. Using generic Bayesian networks fragments from existing literature on the topic, course participants were able to track the probabilistic underpinnings of the proposed scenario correctly both in terms of likelihood ratios and of posterior probabilities. In addition, further study of the example by students allowed them to derive an alternative Bayesian network structure with a computational output that is equivalent to existing probabilistic solutions. This practical experience underlines the potential of Bayesian networks to support and clarify foundational principles of probabilistic procedures for forensic evaluation.

EEG-based functional networks in schizophrenia.

Schizophrenia is often considered as a dysconnection syndrome in which, abnormal interactions between large-scale functional brain networks result in cognitive and perceptual deficits. In this article we apply the graph theoretic measures to brain functional networks based on the resting EEGs of fourteen schizophrenic patients in comparison with those of fourteen matched control subjects. The networks were extracted from common-average-referenced EEG time-series through partial and unpartial cross-correlation methods. Unpartial correlation detects functional connectivity based on direct and/or indirect links, while partial correlation allows one to ignore indirect links. We quantified the network properties with the graph metrics, including mall-worldness, vulnerability, modularity, assortativity, and synchronizability. The schizophrenic patients showed method-specific and frequency-specific changes especially pronounced for modularity, assortativity, and synchronizability measures. However, the differences between schizophrenia patients and normal controls in terms of graph theory metrics were stronger for the unpartial correlation method.

Cognate microRNA-Gene Regulatory Networks Mediating Glioblastoma Oncogenic Properties

Malignant gliomas, including the most common and fatal form glioblastoma (GBM, WHO grade IV astrocytoma), remain a challenge to treat. In the United States and Europe, more than 30,000 patients per year are newly diagnosed with GBM. Despite ongoing trials, the best currently available multimodal treatment approaches include surgical resection followed by concomitant and adjuvant radiation (RT) and temozolomide (TMZ) therapy, resulting in a low median overall survival (OS) rate ranging from 12.2 - 15.9 months. The important role of genetic and epigenetic changes in DNA, RNA, and protein alteration as well as epigenetic changes secondary to the tumor microenvironment and outside selection pressure (therapeutic interventions), are increasingly being recognized. In GBM treatment, the focus is shifting toward a more patient-centered (personalized) therapy. In this regard, in particular, microRNAs are being increasingly studied. MicroRNAs are non¬protein coding small RNAs that serve as negative gene regulators by binding to a specific sequence in the promoter region of a target gene, thus regulating gene expression. A single microRNA potentially targets hundreds of genes; thus, microRNAs and their cognate target genes have important roles as tumor suppressors and oncogenes as well as regulators of various cancer- specific cellular features, such as proliferation, apoptosis, invasion, and metastasis. The identification of distinct microRNA-gene regulatory networks in GBM patients can be expected to provide novel therapeutic insights by identifying candidate patients for targeted therapies. To this end, in this work we identified and validated clinically relevant and meaningful novel gene- microRNA regulatory networks that correlated with MR tumor phenotypes, histopathology, and patient survival and response rates to therapy. - Le traitement des gliomes malins, y compris sous leur forme la plus commune et meurtrière, le glioblastome (GBM, ou astrocytome de grade IV selon l'OMS), demeure à ce jour un défi. Aux États-Unis et en Europe, un nouveau diagnostic de GBM est prononcé dans plus de 30Ό00 cas par an. En dépit de tests en cours, les meilleures approches thérapeutiques combinées actuellement disponibles comprennent la résection chirurgicale de la tumeur, suivie d'une radiothérapie adjuvante ainsi que d'un traitement au temozolomide (RT/TMZ), thérapies dont résulte une médiane de survie globale basse (overall survival, OS), comprise entre 12.2 et 15.9 mois. On reconnaît de plus en plus le rôle majeur de l'ADN, de l'ARN et de l'altération des protéines ainsi que des modifications épigénétiques, secondaires par rapport au microenvironnement de la tumeur et à la pression de sélection extérieure (les interventions thérapeutiques). Dans le traitement du GBM, le centre d'intérêt se déplace vers une thérapie centrée sur le cas individuel du patient. Dans ce but, en particulier les microARN sont de plus en plus analysés. Les microARN sont de petits ARN non-codants (les protéines) qui servent de régulateurs négatifs de gènes en s'attachant à une séquence spécifique dans la région promotrice d'un gène-cible, régulant ainsi l'expression du gène. Un seul microARN cible potentiellement des centaines de gènes; on a ainsi découvert que les microARN et leurs gènes-cibles apparentés ont une fonction importante en tant que suppresseurs de tumeurs et d'oncogènes, ainsi que comme régulateurs de diverses caractéristiques cellulaires spécifiques du cancer, comme la prolifération, l'apoptose, l'invasion et la métastase. On peut s'attendre à ce que l'identification de réseaux microARN régulateurs de gènes, distincts selon les patients de GBM, fournisse une approche thérapeutique inédite par la détermination des patients susceptibles de réagir favorablement à des thérapies ciblées.

Statistical mechanics of multi-edge networks

Statistical properties of binary complex networks are well understood and recently many attempts have been made to extend this knowledge to weighted ones. There are, however, subtle yet important considerations to be made regarding the nature of the weights used in this generalization. Weights can be either continuous or discrete magnitudes, and in the latter case, they can additionally have undistinguishable or distinguishable nature. This fact has not been addressed in the literature insofar and has deep implications on the network statistics. In this work we face this problem introducing multiedge networks as graphs where multiple (distinguishable) connections between nodes are considered. We develop a statistical mechanics framework where it is possible to get information about the most relevant observables given a large spectrum of linear and nonlinear constraints including those depending both on the number of multiedges per link and their binary projection. The latter case is particularly interesting as we show that binary projections can be understood from multiedge processes. The implications of these results are important as many real-agent-based problems mapped onto graphs require this treatment for a proper characterization of their collective behavior.

Wireless Sensor Networks for Infrastructure Monitoring, TR-611, 2010

A good system of preventive bridge maintenance enhances the ability of engineers to manage and monitor bridge conditions, and take proper action at the right time. Traditionally infrastructure inspection is performed via infrequent periodical visual inspection in the field. Wireless sensor technology provides an alternative cost-effective approach for constant monitoring of infrastructures. Scientific data-acquisition systems make reliable structural measurements, even in inaccessible and harsh environments by using wireless sensors. With advances in sensor technology and availability of low cost integrated circuits, a wireless monitoring sensor network has been considered to be the new generation technology for structural health monitoring. The main goal of this project was to implement a wireless sensor network for monitoring the behavior and integrity of highway bridges. At the core of the system is a low-cost, low power wireless strain sensor node whose hardware design is optimized for structural monitoring applications. The key components of the systems are the control unit, sensors, software and communication capability. The extensive information developed for each of these areas has been used to design the system. The performance and reliability of the proposed wireless monitoring system is validated on a 34 feet span composite beam in slab bridge in Black Hawk County, Iowa. The micro strain data is successfully extracted from output-only response collected by the wireless monitoring system. The energy efficiency of the system was investigated to estimate the battery lifetime of the wireless sensor nodes. This report also documents system design, the method used for data acquisition, and system validation and field testing. Recommendations on further implementation of wireless sensor networks for long term monitoring are provided.

Diffusion dynamics on multiplex networks

We study the time scales associated with diffusion processes that take place on multiplex networks, i.e., on a set of networks linked through interconnected layers. To this end, we propose the construction of a supra-Laplacian matrix, which consists of a dimensional lifting of the Laplacian matrix of each layer of the multiplex network. We use perturbative analysis to reveal analytically the structure of eigenvectors and eigenvalues of the complete network in terms of the spectral properties of the individual layers. The spectrum of the supra-Laplacian allows us to understand the physics of diffusionlike processes on top of multiplex networks.

Deciphering the global organization of clustering in real complex networks

We uncover the global organization of clustering in real complex networks. To this end, we ask whether triangles in real networks organize as in maximally random graphs with given degree and clustering distributions, or as in maximally ordered graph models where triangles are forced into modules. The answer comes by way of exploring m-core landscapes, where the m-core is defined, akin to the k-core, as the maximal subgraph with edges participating in at least m triangles. This property defines a set of nested subgraphs that, contrarily to k-cores, is able to distinguish between hierarchical and modular architectures. We find that the clustering organization in real networks is neither completely random nor ordered although, surprisingly, it is more random than modular. This supports the idea that the structure of real networks may in fact be the outcome of self-organized processes based on local optimization rules, in contrast to global optimization principles.

Bayesian networks and the evaluation of scientific evidence in forensic science

Résumé Ce travail de thèse étudie des moyens de formalisation permettant d'assister l'expert forensique dans la gestion des facteurs influençant l'évaluation des indices scientifiques, tout en respectant des procédures d'inférence établies et acceptables. Selon une vue préconisée par une partie majoritaire de la littérature forensique et juridique - adoptée ici sans réserve comme point de départ - la conceptualisation d'une procédure évaluative est dite 'cohérente' lors qu'elle repose sur une implémentation systématique de la théorie des probabilités. Souvent, par contre, la mise en oeuvre du raisonnement probabiliste ne découle pas de manière automatique et peut se heurter à des problèmes de complexité, dus, par exemple, à des connaissances limitées du domaine en question ou encore au nombre important de facteurs pouvant entrer en ligne de compte. En vue de gérer ce genre de complications, le présent travail propose d'investiguer une formalisation de la théorie des probabilités au moyen d'un environment graphique, connu sous le nom de Réseaux bayesiens (Bayesian networks). L'hypothèse principale que cette recherche envisage d'examiner considère que les Réseaux bayesiens, en concert avec certains concepts accessoires (tels que des analyses qualitatives et de sensitivité), constituent une ressource clé dont dispose l'expert forensique pour approcher des problèmes d'inférence de manière cohérente, tant sur un plan conceptuel que pratique. De cette hypothèse de travail, des problèmes individuels ont été extraits, articulés et abordés dans une série de recherches distinctes, mais interconnectées, et dont les résultats - publiés dans des revues à comité de lecture - sont présentés sous forme d'annexes. D'un point de vue général, ce travail apporte trois catégories de résultats. Un premier groupe de résultats met en évidence, sur la base de nombreux exemples touchant à des domaines forensiques divers, l'adéquation en termes de compatibilité et complémentarité entre des modèles de Réseaux bayesiens et des procédures d'évaluation probabilistes existantes. Sur la base de ces indications, les deux autres catégories de résultats montrent, respectivement, que les Réseaux bayesiens permettent également d'aborder des domaines auparavant largement inexplorés d'un point de vue probabiliste et que la disponibilité de données numériques dites 'dures' n'est pas une condition indispensable pour permettre l'implémentation des approches proposées dans ce travail. Le présent ouvrage discute ces résultats par rapport à la littérature actuelle et conclut en proposant les Réseaux bayesiens comme moyen d'explorer des nouvelles voies de recherche, telles que l'étude de diverses formes de combinaison d'indices ainsi que l'analyse de la prise de décision. Pour ce dernier aspect, l'évaluation des probabilités constitue, dans la façon dont elle est préconisée dans ce travail, une étape préliminaire fondamentale de même qu'un moyen opérationnel.

Probabilistic evidential assessment of gunshot residue particle evidence (Part I): likelihood ratio calculation and case pre-assessment using Bayesian networks

Well developed experimental procedures currently exist for retrieving and analyzing particle evidence from hands of individuals suspected of being associated with the discharge of a firearm. Although analytical approaches (e.g. automated Scanning Electron Microscopy with Energy Dispersive X-ray (SEM-EDS) microanalysis) allow the determination of the presence of elements typically found in gunshot residue (GSR) particles, such analyses provide no information about a given particle's actual source. Possible origins for which scientists may need to account for are a primary exposure to the discharge of a firearm or a secondary transfer due to a contaminated environment. In order to approach such sources of uncertainty in the context of evidential assessment, this paper studies the construction and practical implementation of graphical probability models (i.e. Bayesian networks). These can assist forensic scientists in making the issue tractable within a probabilistic perspective. The proposed models focus on likelihood ratio calculations at various levels of detail as well as case pre-assessment.