Bipartite experiments have recently emerged as a focal point in causal inference. In these experiments, treatment is administered to one set of units, while outcomes of interest are gauged on a distinct set of units. Such experiments are especially valuable in scenarios where pronounced interference effects transpire between units on a bipartite network. For instance, in market experiments, designating treatment at the seller level and assessing outcomes at the buyer level (or vice-versa) can lead to causal models that more accurately reflect the inherent interference between buyers and sellers. Although bipartite experiments can enhance the precision of causal effect estimations in specific contexts, it's imperative to conduct the analysis judiciously to avoid introducing undue bias through the network. Drawing from the generalized propensity score literature, we demonstrate that it's feasible to achieve unbiased estimates of causal effects for bipartite experiments, given a conventional set of assumptions. Furthermore, we delve into the formulation of confidence sets with accurate coverage probabilities. By employing a bipartite graph from a publicly accessible dataset previously explored in bipartite experiment studies, we illustrate, via simulations, a notable reduction in bias and augmented coverage. / Statistics

No description available.

Les technologies modernes permettent d'avoir des renseignements toujours plus précis sur les interactions entre individus. Dans ce contexte, la collaboration SocioPatterns a permis de développer une infrastructure mesurant, avec une très grande résolution temporelle, la proximité face-à-face d'individus volontaires, portant des badges de radio-identification. Cette infrastructure a été déployée dans divers contextes, tels que des conférences scientifiques, un musée, une école ou encore un service hospitalier. La simple analyse de ces données représente un enjeu majeur pour l'étude de la dynamique humaine et soulève des questions aussi fondamentales que la recherche d'outils et de techniques d'analyse adaptés. Cette thèse présente la caractérisation statistique de la dynamique de proximité physique, mise en relation avec le contexte et les autres métadonnées disponibles, telles que l'âge, le sexe des individus, ou bien la structure de leurs réseaux sociaux virtuels. Si la structure des contacts diffère considérablement selon le contexte, les distributions empiriques des durées des interactions et entre interactions sont très similaires. Un modèle individu-centré, présenté dans cette thèse, propose des règles d'interactions microscopiques simples susceptibles de donner lieu à cette structure macroscopique complexe des temps d'interaction. Enfin, la caractérisation de la dynamique des contacts entre individus constitue une étape cruciale pour comprendre les mécanismes de propagation de maladies telles que la grippe dans une population. / Modern technologies allow to access to more and more detailed information on human interactions. In this context, the SocioPatterns collaboration has allowed to develop an infrastructure based on radio-identification devices, that records human proximity patterns at a fine grained resolution, among voluntary individuals. This infrastructure has been deployed in diverse contexts, such as scientific conferences, a museum, a primary school, or a hospital department. The mere analysis of these data represents a high stake for the study of human dynamics and raises fundamental issues such as the need of adequate tools and analysis techniques. This thesis presents the statistical characterization of physical proximity dynamics, put into relation with the context and other available metadata such as the age, the gender of participants or the structure of their virtual social networks. Although contact patterns considerably differ amongst the various contexts, the empirical distributions of interaction durations and of inter-contact times are very similar. An agent-based model, presented in this thesis, suggests simple microscopic interaction rules able to produce the complex macrostructure of interaction durations. In the last place, the characterization of contact dynamics constitutes a determining step for understanding spreading mechanisms of diseases such as the influenza. The human proximity data have allowed to analyze the level of information needed on contact dynamics for the elaboration of epidemiological models of contagion. Such models allow to better estimate the impact of public health strategies, e.g. the closure of school classes and targeted vaccinations.

In this thesis we look at mobile agent solutions to black hole search and related problems. Mobile agents are computational entities that are autonomous, mobile, and can interact with their environment and each other. The black hole search problem is for a team of these agents to work together to map or explore a graph-like network environment where some elements of the network are dangerous to the agents. Most research into black hole search has focussed on finding a single dangerous node: a black hole. We look at the problem of finding multiple black holes and, in the case of dangerous graph exploration, multiple black links as well. We look at the dangerous graph exploration problem in the network model. The network model is based on a normal static computer network modelled as a simple graph. We give an optimal solution to the dangerous graph exploration problem using agents that start scattered on nodes throughout the network. We then make the problem more difficult by allowing an adversary to delete links during the execution of the algorithm and provide a solution using scattered agents. In the last decade or two, types of networks have emerged, such as ad hoc wireless networks, that are by their nature dynamic. These networks change quickly over time and can make distributed computations difficult. We look at black hole search in one type of dynamic network described by the subway model, which we base on urban subway systems. The model allows us to look at the cost of opportunistic movement by requiring the agents to move using carriers that follow routes among the network's sites, some of which are black holes. We show that there are basic limitations on any solution to black hole search in the subway model and prove lower bounds on any solution's complexity. We then provide two optimal solutions that differ in the agents' starting locations and how they communicate with one another. Our results provide a small window into the cost of deterministic distributed computing in networks that have dynamic elements, but which are not fully random.

In this thesis we look at mobile agent solutions to black hole search and related problems. Mobile agents are computational entities that are autonomous, mobile, and can interact with their environment and each other. The black hole search problem is for a team of these agents to work together to map or explore a graph-like network environment where some elements of the network are dangerous to the agents. Most research into black hole search has focussed on finding a single dangerous node: a black hole. We look at the problem of finding multiple black holes and, in the case of dangerous graph exploration, multiple black links as well. We look at the dangerous graph exploration problem in the network model. The network model is based on a normal static computer network modelled as a simple graph. We give an optimal solution to the dangerous graph exploration problem using agents that start scattered on nodes throughout the network. We then make the problem more difficult by allowing an adversary to delete links during the execution of the algorithm and provide a solution using scattered agents. In the last decade or two, types of networks have emerged, such as ad hoc wireless networks, that are by their nature dynamic. These networks change quickly over time and can make distributed computations difficult. We look at black hole search in one type of dynamic network described by the subway model, which we base on urban subway systems. The model allows us to look at the cost of opportunistic movement by requiring the agents to move using carriers that follow routes among the network's sites, some of which are black holes. We show that there are basic limitations on any solution to black hole search in the subway model and prove lower bounds on any solution's complexity. We then provide two optimal solutions that differ in the agents' starting locations and how they communicate with one another. Our results provide a small window into the cost of deterministic distributed computing in networks that have dynamic elements, but which are not fully random.

In this thesis we look at mobile agent solutions to black hole search and related problems. Mobile agents are computational entities that are autonomous, mobile, and can interact with their environment and each other. The black hole search problem is for a team of these agents to work together to map or explore a graph-like network environment where some elements of the network are dangerous to the agents. Most research into black hole search has focussed on finding a single dangerous node: a black hole. We look at the problem of finding multiple black holes and, in the case of dangerous graph exploration, multiple black links as well. We look at the dangerous graph exploration problem in the network model. The network model is based on a normal static computer network modelled as a simple graph. We give an optimal solution to the dangerous graph exploration problem using agents that start scattered on nodes throughout the network. We then make the problem more difficult by allowing an adversary to delete links during the execution of the algorithm and provide a solution using scattered agents. In the last decade or two, types of networks have emerged, such as ad hoc wireless networks, that are by their nature dynamic. These networks change quickly over time and can make distributed computations difficult. We look at black hole search in one type of dynamic network described by the subway model, which we base on urban subway systems. The model allows us to look at the cost of opportunistic movement by requiring the agents to move using carriers that follow routes among the network's sites, some of which are black holes. We show that there are basic limitations on any solution to black hole search in the subway model and prove lower bounds on any solution's complexity. We then provide two optimal solutions that differ in the agents' starting locations and how they communicate with one another. Our results provide a small window into the cost of deterministic distributed computing in networks that have dynamic elements, but which are not fully random.

Les systèmes distribués sont de plus en plus grands et complexes, alors que leur utilisation s'étend à de nombreux domaines (par exemple, les communications, la domotique, la surveillance, le ``cloud''). Par conséquent, les contextes d'exécution des systèmes distribués sont très divers. Dans cette thèse, nous nous focalisons sur des contextes incertains, autrement dit, le contexte n'est pas complètement connu au départ ou il est changeant. Plus précisément, nous nous focalisons sur deux principaux types d'incertitudes : une identification incomplète des processus et la présence de fautes. L'absence d'identification est fréquente dans de grands réseaux composés d'appareils produits et déployés en masse. De plus, l'anonymat est souvent une demande pour la sécurité et la confidentialité. De la même façon, les grands réseaux sont exposés aux pannes comme la panne définitive d'un processus ou une perte de connexion sans fil. Néanmoins, le service fourni doit rester disponible.Cette thèse est composée de quatre contributions principales. Premièrement, nous étudions le problème de l'élection de leader dans les anneaux unidirectionnels de processus homonymes (les processus sont identifiés mais leur ID n'est pas forcément unique). Par la suite, nous proposons un algorithme d'élection de leader silencieux et autostabilisant pour tout réseau connecté. Il s'agit du premier algorithme fonctionnant sous de telles conditions qui stabilise en un nombre polynomial de pas de calcul. La troisième contribution est une nouvelle propriété de stabilisation conçue pour les réseaux dynamiques qui garantit des convergences rapides et progressives après des changements topologiques. Nous illustrons cette propriété avec un algorithme de synchronisation d'horloges. Finalement, nous considérons la question de la concurrence dans les problèmes d'allocation de ressources. En particulier, nous étudions le niveau de concurrence qui peut être atteint dans une grande classe de problèmes d'allocation de ressources, l'allocation de ressources locales. / Distributed systems become increasingly wide and complex, while their usage extends to various domains (e.g., communication, home automation, monitoring, cloud computing). Thus, distributed systems are executed in diverse contexts. In this thesis, we focus on uncertain contexts, i.e., the context is not completely known a priori or is unsettled. More precisely, we consider two main kinds of uncertainty: processes that are not completely identified and the presence of faults. The absence of identification is frequent in large networks composed of massively produced and deployed devices. In addition, anonymity is often required for security and privacy. Similarly, large networks are exposed to faults (e.g, process crashes, wireless connection drop), but the service must remain available.This thesis is composed of four main contributions. First, we study the leader election problem in unidirectional rings of homonym processes, i.e., processes are identified but their ID is not necessarily unique. Then, we propose a silent self-stabilizing leader election algorithm for arbitrary connected network. This is the first algorithm under such conditions that stabilizes in a polynomial number of steps. The third contribution is a new stabilizing property designed for dynamic networks that ensures fast and gradual convergences after topological changes. We illustrate this property with a clock synchronizing algorithm. Finally, we consider the issue of concurrency in resource allocation problems. In particular, we study the level of concurrency that can be achieved in a wide class of resource allocation problem, i.e., the local resource allocation.

In this thesis we look at mobile agent solutions to black hole search and related problems. Mobile agents are computational entities that are autonomous, mobile, and can interact with their environment and each other. The black hole search problem is for a team of these agents to work together to map or explore a graph-like network environment where some elements of the network are dangerous to the agents. Most research into black hole search has focussed on finding a single dangerous node: a black hole. We look at the problem of finding multiple black holes and, in the case of dangerous graph exploration, multiple black links as well. We look at the dangerous graph exploration problem in the network model. The network model is based on a normal static computer network modelled as a simple graph. We give an optimal solution to the dangerous graph exploration problem using agents that start scattered on nodes throughout the network. We then make the problem more difficult by allowing an adversary to delete links during the execution of the algorithm and provide a solution using scattered agents. In the last decade or two, types of networks have emerged, such as ad hoc wireless networks, that are by their nature dynamic. These networks change quickly over time and can make distributed computations difficult. We look at black hole search in one type of dynamic network described by the subway model, which we base on urban subway systems. The model allows us to look at the cost of opportunistic movement by requiring the agents to move using carriers that follow routes among the network's sites, some of which are black holes. We show that there are basic limitations on any solution to black hole search in the subway model and prove lower bounds on any solution's complexity. We then provide two optimal solutions that differ in the agents' starting locations and how they communicate with one another. Our results provide a small window into the cost of deterministic distributed computing in networks that have dynamic elements, but which are not fully random.

Co-authorship networks are a particular sort of social networks representing authors collaborating on joint publications. Such networks are studied within the fields of bibliometrics and scientometrics. While it is possible to analyze co-authorship networks in their entirety, certain analytical tasks would benefit from representing such networks as dynamic graphs, which incorporate a temporal dimension and capture structural transformations unfolding over time. The importance of dynamic graphs has emerged in recent years, in graph theory at large as well as within application domains such as social sciences, for instance.Research regarding dynamic graphs has been identified as one of the major challenges within network theory since they are particularly useful for describing real-world systems.This thesis project revolves around dynamic co-authorship network analysis algorithms, which aim to extract various temporal aspects regarding author collaborations.It is the result of a proposal by the ISOVIS group at Linnaeus University, which is active within the fields of exploratory data analysis and information visualization, including the problem of visual analysis of scientific publication data. The algorithms developed in this project extract analytical data such as (1) joint publications among pairs of authors, (2) temporal trends on connected components (groups of authors) along with network centrality measurements, and (3) major events regarding emergence, mergers, and splits of connected components over time. Together with domain experts, the analysis regarding usability, performance, and scalability of the algorithms took place as part of the evaluation process to assure that the result met the needs which instigated this thesis project. The application of the algorithms on real data sets provided by the ISOVIS group was useful concerning the evaluation of the usability domain. In contrast, customized synthetic data sets was an excellent tool for evaluating performance and scalability.

No description available.