Many of the algorithms used for community detection in temporal networks have been adapted from static network theory. A common approach in dealing with the temporal dimension is to create multiple static networks from one temporal, based on a time condition. In this thesis, focus lies on identifying the optimal partitioning of a few temporal networks. This is done by utilizing the popular community detection algorithm called Generalized Louvain. Output of the Generalized Louvain comes in two parts. First, the created community structure, i.e. how the network is connected. Secondly, a measure called modularity, which is a scalar value representing the quality of the identified community structure. The methodology used is aimed at creating a comparable result by normalizing modularity. The normalization process can be explained in two major steps: 1) study the effects on modularity when partitioning a temporal network in an increasing number of slices. 2) study the effects on modularity when varying the number of connections (edges) in each time slice. The results show that the created methodology yields comparable results on two out of the four here tested temporal networks, implying that it might be more suited for some networks than others. This can serve as an indication that there does not exist a general model for community detection in temporal networks. Instead, the type of network is key to choosing the method.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第20893号 / 理博第4345号 / 新制||理||1624(附属図書館) / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)准教授 篠本 滋, 教授 佐々 真一, 教授 川上 則雄 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

Physical systems modeled by networks are fully dynamic in the sense that the process of adding edges and vertices never ends, and no edge or vertex is necessarily eternal. Temporal networks enable to explicitly study systems with a changing topology by capturing explicitly the temporal changes. The controllability of temporal networks is the study of driving the state of a temporal network to a target state at deadline t_f within △t = t_f - t₀ steps by stimulating key nodes called driver nodes. In this research, the author aims to understand and analyze temporal networks from the controllability perspective at the global and nodal scales. To analyze the controllability at global scale, the author provides an efficient heuristic algorithm to build driver node sets capable of fully controlling temporal networks. At the nodal scale, the author presents the concept of Complete Controllable Domain (CCD) to investigate the characteristics of Maximum Controllable Subspaces (MCSs) of a driver node. The author shows that a driver node can have an exponential number of MCSs and introduces a branch and bound algorithm to approximate the CCD of a driver node. The proposed algorithms are evaluated on real-world temporal networks induced from ant interactions in six colonies and in a set of e-mail communications of a manufacturing company. At the global scale, the author provides ways to determine the control regime in which a network operates. Through empirical analysis, the author shows that ant interaction networks operate under a distributed control regime whereas the e-mails network operates in a centralized regime. At the nodal scale, the analysis indicated that on average the number of nodes that a driver node always controls is equal to the number of driver nodes that always control a node. <br>

This thesis seeks to extend the application of Social Network Analysis (SNA) to temporal graphs, in particular providing new insights for the understanding of covert networks. The analyses undertaken reveal informative features and properties of individuals' affiliations under covertness that also illustrate how both individuals and events influence the network structure. The review of the literature on covert networks provided in the initial two chapters suggests the presence of some ambiguities concerning how authors define structural properties and dynamics of covert networks. Authors sometimes disagree and use their findings to explain opposite views about covert networks. The controversy in the field is used as a starting point in order to justify the methodological application of SNA to understand how individuals involved in criminal and illegal activities interact with each other. I attempt to use a deductive approach, without preconceived notions about covert network characteristics. In particular, I avoid considering covert networks as organisations in themselves or as cohesive groups. I focus on individuals and their linkages constructed from their common participation in illicit events such as secret meetings, bombing attacks and criminal operations. In order to tackle these processes I developed innovative methods for investigating criminals' behaviours over time and their willingness to exchange tacit information. The strategy implies the formulation of a network model in order to represent and incorporate in a graph three types of information: individuals, events, and the temporal dimension of events. The inclusion of the temporal dimension offers the possibility of adopting a more comprehensive theoretical framework for considering individuals and event affiliations. This thesis expands the analysis of bipartite covert networks by adopting several avenues to explore in this perspective. Chapter 3 proposes a different way to represent two-mode networks starting from the use of line-graphs, namely the bi-dynamic line-graph data representation (BDLG), through which it is possible to represent the temporal evolution of individual's trajectories. The following chapter 4 presents some reflections about the idea of cohesion and cohesive subgroups specific to the case of two-mode networks. Based on the affiliation matrices, the analysis of local clustering through bi-cliques offers an attempt to analyse the mechanism of selecting accomplices while taking into account time. Chapter 5 is concerned with the concept of centrality of individuals involved in flows of knowledge exchanges. The theoretical and analytical framework helps in elaborating how individuals share their acquired hands-on experiences with others by attending joint task activities over time. Chapter 6 provides an application of the approaches introduced in the preceding chapters to the specific case of the Noordin Top terrorist network. Here, the knowledge of experience flow centrality measure opens up a new way to quantify the transmission of information and investigate the formation of the criminal capital. Finally, the last Chapter 7 presents some future research extensions by illustrating the versatility of the proposed approaches in order to provide new insights for the understanding of criminals' behaviours.

Recent years have seen a huge increase in the amount of data collected from multiple sources: mobile phones are ubiquitous, social networks are widely used, cities are more and more connected and the mobility of people and goods has risen to a global scale. The Big Data Era has opened the doors to new kinds of studies that were unthinkable with previous qualitative methods: human behavior can now be analyzed with a fine-grained resolution, patterns of mobility and behavior can be extracted from the incredible amount of data collected every day. Modern large cities are becoming more and more interconnected and this phenomenon leads to an increasing communication and activities’ synchronization. Due to the amount of data available or for anonymization reasons, it is often necessary to aggregate data spatially and temporally. A natural representation of clustered mobility data is the temporal network representation. In this thesis we focus on these two aspects of spatial distance in human mobility: (i) we study the synchronization of 76 Italian cities, using mobile phone data, showing that both distance between cities and city size determine the synchronization in communication rhythms. Moreover, we show that the effect of the distance in synchronization decreases when the size of the city increases; (ii) we investigate how clustering continuous spatio-temporal data affects spatio-temporal network measures for real-life and synthetic datasets and analyze how spatio-temporal networks’ measures vary at different aggregation levels.

Temporal reasoning has been an active research area for over twenty years, with most work focussing on either enhancing the efficiency of current temporal reasoning algorithms or enriching the existing algebras. However, there has been little research into handling over-constrained temporal problems except to recognise that a problem is over-constrained and then to terminate. As many real-world temporal reasoning problems are inherently over-constrained, particularly in the scheduling domain, there is a significant need for approaches that can handle over-constrained situations. In this thesis, we propose two backtracking algorithms to gain partial solutions to over-constrained temporal problems. We also propose a new representation, the end-point ordering model, to allow the use of local search algorithms for temporal reasoning. Using this model we propose a constraint weighting local search algorithm as well as tabu and random-restart algorithms to gain partial solutions to over-constrained temporal problems. Specifically, the contributions of this thesis are: The introduction and empirical evaluation of two backtracking algorithms to solve over-constrained temporal problems. We provide two backtracking algorithms to close the gap in current temporal research to solve over-constrained problems; The representation of temporal constraint networks using the end-point ordering model. As current representation models are not suited for local search algorithms, we develop a new model such that local search can be applied efficiently to temporal reasoning; The development of a constraint weighting local search algorithm for under-constrained problems. As constraint weighting has proven to be efficient for solving many CSP problems, we implement a constraint weighting algorithm to solve under-constrained temporal problems; An empirical evaluation of constraint weighting local search against traditional backtracking algorithms. We compare the results of a constraint weighting algorithm with traditional backtracking approaches and find that in many cases constraint weighting has superior performance; The development of a constraint weighting local search, tabu search and random-restart local search algorithm for over-constrained temporal problems. We extend our constraint weighting algorithm to solve under-constrained temporal problems as well as implement two other popular local search algorithms: tabu search and random-restart; An empirical evaluation of all three local search algorithms against the two backtracking algorithms. We compare the results of all three local search algorithms with our twobacktracking algorithms for solving over-constrained temporal reasoning problems and find that local search proves to be considerably superior.

L’Internet a complètement révolutionné la façon dont nous communiquons. En parallèle, la croissance importante des réseaux mobiles s'est accompagnée d'une explosion du nombre d’usagers et d'une augmentation exponentielle de la demande. Cependant, l’Internet n'est pas encore, voire n'est pas toujours, universellement accessible. Par exemple, c'est le cas en ce qui concerne l’accès dans les économies émergentes ou dans les régions éloignées, les obstacles physiques empêchant le déploiement de réseaux mobiles et les désastres naturels. C'est dans ce contexte que les réseaux tolérants au délai ont été introduits pour faire face aux environnements caractérisés par des interruptions et des délais de transmission élevés. Ces réseaux, manquent souvent de routes pré-déterminées ou même de toute infrastructure pour permettre une communication de bout-en-bout. Dans ce contexte, tous les nœuds de ces réseaux peuvent interagir en utilisant leurs contacts comme une opportunité de communication. Le paradigme stockage/transport permet à ces nœuds d’exploiter des chemins spatio-temporels créés par ces possibilités de contact afin de livrer des messages au fil du temps. Dans ce travail, nous soulevons ici une question générique : pouvons-nous concevoir une infrastructure mobile et opportuniste qui pourrait aider à transmettre ces messages ? Afin de fournir une telle infrastructure, nous étudions l’application des marches aléatoires temporelles (TRWs) dans réseaux opportunistes. Nous explorons l’application et l’impact de la TRW pour fournir une infrastructure minimale et non-invasive à partir de deux points de vue : le stockage des données et leur transmission. / The Internet has entirely reshaped the way we communicate and interact with one another. The rapid development of the wireless infrastructure by network providers has being accompanied by an exponential growth in the number of mobile users. However, global Internet access and connectivity still face several challenges: scarce or poor quality connectivity in developing countries or places with limited accessibility, physical obstacles limiting the deployment of wireless networks and natural or man-made disasters. Delay tolerant networks (DTNs) were introduced to deal with environments where interruptions or disruptions of service were expected. Such networks usually lack of end-to-end paths or any infrastructure to help communications. In these networks, mobile nodes may interact using their contacts as a communication opportunity. The store-carry-forward paradigm allows nodes to exploit spatio-temporal paths created by contact opportunities in order to deliver messages over time. Instead we raise the question: can we design a mobile and opportunistic infrastructure that could help deliver messages? In the quest to provide such infrastructure, we study the application of temporal random walks (TRW) over the opportunistic networks. We explore the application and impact of TRW as a minimal and non invasive infrastructure from two points of view: data forwarding and data recollection/transmission.

Automated Planning is an active area within Artificial Intelligence. With the help of computers we can quickly find good plans in complicated problem domains, such as planning for search and rescue after a natural disaster. When planning in realistic domains the exact duration of an action generally cannot be predicted in advance. Temporal planning therefore tends to use upper bounds on durations, with the explicit or implicit assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false. If we finish cooking too early, the dinner will be cold before everyone is at home and can eat. Simple Temporal Networks with Uncertainty (STNUs) allow us to model such situations. An STNU-based planner must verify that the temporal problems it generates are executable, which is captured by the property of dynamic controllability (DC). If a plan is not dynamically controllable, adding actions cannot restore controllability. Therefore a planner should verify after each action addition whether the plan remains DC, and if not, backtrack. Verifying dynamic controllability of a full STNU is computationally intensive. Therefore, incremental DC verification algorithms are needed. We start by discussing two existing algorithms relevant to the thesis. These are the very first DC verification algorithm called MMV (by Morris, Muscettola and Vidal) and the incremental DC verification algorithm called FastIDC, which is based on MMV. We then show that FastIDC is not sound, sometimes labeling networks as dynamically controllable when they are not.  We analyze the algorithm to pinpoint the cause and show how the algorithm can be modified to correctly and efficiently detect uncontrollable networks. In the next part we use insights from this work to re-analyze the MMV algorithm. This algorithm is pseudo-polynomial and was later subsumed by first an n5 algorithm and then an n4 algorithm. We show that the basic techniques used by MMV can in fact be used to create an n4 algorithm for verifying dynamic controllability, with a new termination criterion based on a deeper analysis of MMV. This means that there is now a comparatively easy way of implementing a highly efficient dynamic controllability verification algorithm. From a theoretical viewpoint, understanding MMV is important since it acts as a building block for all subsequent algorithms that verify dynamic controllability. In our analysis we also discuss a change in MMV which reduces the amount of regression needed in the network substantially. In the final part of the thesis we show that the FastIDC method can result in traversing part of a temporal network multiple times, with constraints slowly tightening towards their final values.  As a result of our analysis we then present a new algorithm with an improved traversal strategy that avoids this behavior.  The new algorithm, EfficientIDC, has a time complexity which is lower than that of FastIDC. We prove that it is sound and complete.

Les contacts face-à-face entre individus permettent de caractériser les réseaux sociaux et jouent un rôle prépondérant dans la compréhension des mécanismes de propagation des épidémies dans une population. De récentes avancées technologiques ont rendu possible l'acquisition de données précises sur les interactions humaines. Cette thèse présente, dans un premier temps, l'analyse de données de contacts collectées trois années de suite (2011, 2012 et 2013) dans un lycée français entre des étudiants de classes préparatoires. L'analyse a montré que la plupart des contacts se produisent entre étudiants de même classe et que les structures des contacts sont très similaires d'un jour sur l'autre. Dans un second temps, on compare différentes méthodes de collecte de données qui permettent d'obtenir des informations de nature différente (par exemple existence d'un contact face-à-face vs existence d'une amitié).L'utilisation de données rapportant les amitiés entre les étudiants ne permet pas d'obtenir une bonne estimation du réseau de contact (i.e., les amitiés ne correspondent pas forcément à des contacts face-à-face et vice versa) résultant en une sous-estimation du risque épidémique dans cette population.Dans la dernière partie, nous essayons de reproduire les biais provenant du réseau d'amitié en échantillonnant le réseau de contact. Ceci pourrait nous donner des indications sur comment compenser ces biais et comment utiliser des données incomplètes pour obtenir des prédictions fiables sur le risque épidémique. / Face-to-face contacts between individuals contribute to shape social networks and play an important role in determining how infectious diseases can spread within a population. Recently, technological advances have made it possible to obtain accurate data on human interactions.This thesis first presents the analysis of contact data collected three years in a row (2011, 2012 and 2013) in a French high school among students of "classes préparatoires" (i.e., studies taking place after high school and preparing for admission to higher education colleges). The analysis showed that most contacts occur within students of same classes and that contact patterns are very similar from one day to the next.Then, we compare different methods of data collection which allow to gather information of different nature (for instance existence of a face-to-face contact vs existence of a friendship).The use of data reporting friendships does not allow to obtain a good estimation of the contact network (i.e., friendships do not correspond necessarily to face-to-face contacts and vice versa) resulting in an underestimation of the epidemic risk in that population.Finally, we try to reproduce the biases coming from the friendship network by sampling the contact network. This might give hints on how to compensate these biases and how to use the information contained in incomplete data sets to obtain accurate predictions of the epidemic risk.

Networks are models that help us understanding and thinking about relationships between entities in the real world. Many of these networks are dynamic, i.e. connectivity changes over time. Understanding changes in connectivity means to understand interactions between elements of complex systems; how people create and break up friendship relations, how signals get passed in the brain, how business collaborations evolve, or how food-webs restructure after environmental changes. However, understanding static networks is already difficult, due to size, density, attributes and particular motifs; changes over time very much increase this complexity. Quantification of change is often insufficient, but beyond an analysis that is driven by technology and algorithms, humans dispose a unique capability of understanding and interpreting information in data, based on vision and cognition. This dissertation explores ways to interactively explore dynamic networks by means of visualization. I develop and evaluate techniques to unfold the complexity of dynamic networks, making them understandable by looking at them from different angles, decomposing them into their parts and relating the parts in novel ways. While most techniques for dynamic network visualization rely on one particular type of view on the data, complementary visualizations allow for higher-level exploration and analysis. Covering three aspects Tasks, Visualization Design and Evaluation, I develop and evaluate the following unfolding techniques: (i) temporal navigation between individual time steps of a network and improved animated transitions to better understand changes, (ii) designs for the comparison of weighted graphs, (iii) the Matrix Cube, a space-time cube based on adjacency matrices, allowing to visualize dense dynamic networks by, as well as GraphCuisine, a system to (iv) generate synthetic networks with the primary focus on evaluating visualizations in user studies. In order to inform the design and evaluation of visualizations, we (v) provide a task taxonomy capturing users' tasks when exploring dynamic networks. Finally, (vi) the idea of unfolding networks with Matrix Cubes is generalized to other data sets that can be represented in space-time cubes (videos, geographical data, etc.). Visualizations in these domains can inspire visualizations for dynamic networks, and vice-versa. We propose a taxonomy of operations, describing how 3D space-time cubes are decomposed into a large variety of 2D visualizations. These operations help us exploring the design space for visualizing and interactively unfolding dynamic networks and other spatio-temporal data, as well as may serve users as a mental model of the data.