Project topics and materials
Get Complete Project Material File(s) Now! »
Dynamical processes on complex networks
Not long after the eld of complex networks has been initiated by the Barabási- Albert’s and Watts and Strogatz’s articles, the research line went on dynamical processes evolving on networks, thus bridging the gap between complex networks and another domain of complex system modeling dealing with dynamical processes. I will briey mention some of the main dynamical processes that take place on networks, but the interested reader will nd much more in [Barrat 2008, Dorogovtsev 2008]. One of the favorite models of statistical physicists is the Ising model, in which particles have a spin that can take only two values, +1 or −1. Interaction exists between particles, and an external magnetic eld can be introduced and inuence spins to be in a specic direction. This model has been considered in the case in which the spins are located on the nodes of a network and analytically solved in equilibrium in some cases. In the case of a scale-free network, it has been shown that the phase transition, that is characteristic of the Ising model (except in the onedimensional case) and that divides the phase space into an ordered and a disordered behavior, depends on the exponent of the degree distribution [Bianconi 2002]. A slightly modied version of this model is also used to represent social inuence, and then goes by the name of the voter model. Other ingredients may be added to improve the phenomenology of social inuence, for example when one considers that only individuals having opinions that are not too opposite can inuence each other [Holme 2006, Vazquez 2008, Nardini 2008, Kozma 2008]. Similar models that
dene ordered and disordered phases have been studied. The synchronization of linearly coupled oscillators is, for instance, shown to be more eective in small world-networks than in standard deterministic graphs and purely random graphs [Barahona 2002].
This dependence of phase transition on topology is not specic of the Ising model. For example, the resilience and robustness of networks has been shown to depend on the topology of the network as well [Albert 2000]. This has considerable consequences for technological networks, such as the Internet, which have heavytailed degree distributions and thus are very sensitive to targeted attacks. Analogous results are obtained for simple epidemic models. The epidemic threshold of these models, that separates the phase space in a phase in which a disease spreading
vanishes after few transmissions, and another phase in which the disease reaches a sizable amount of persons, vanishes in case of highly heterogeneous scale-free networks [Pastor-Satorras 2001]. Another example of model is the random walk on networks. In such a discrete system, a random walker hops from node to node if those are connected by an edge. In the case of an uncorrelated network (where there is no correlation between a node degree and its neighbors’ degrees) and a random walker that selects any neighbor with the same probability, the probability that this walker lies, at a given time (when there is no dependence on the starting node), on a node of degree k is proportional to the degree [Noh 2004]. This feature has huge consequences for web search algorithms, such as PageRank, which much rely on such a random walk model.
Mining human interactions
During my PhD, I worked on a specic human interaction, namely face-to-face proximity. Various methodologies have been used to record human interactions. It is possible to classify them into two main categories. First, I review the most used pen-and-paper approaches: surveys and self-reported diaries. Second, I will shortly describe the automatic ways of recording interaction proxies, based on a dedicated technological design1. Third, the methodology that was used to create the datasets I worked on during my thesis, will be presented. Last but not least, the pros and the cons of this protocol with respect to more traditional approaches are discussed.
Before the technological era
The predominant and, likely, the oldest (dating back to Moreno seminal book [Moreno 1953]) method to investigate interactions among persons relies on surveys and questionnaires. Generally, it consists on one or more name generators followed by name interpreters. Name generators are questions asking for a list of persons, such as « Who would you ask for advice in case of a personal problem ». It may be limited in numbers (name up to X persons) or not. The name interpreters are questions to add specic information on the named persons (age, gender) and/or on the nature of the tie (duration of acquaintance, frequency of contacts), on the relationships be- tween named persons (do they know each other…). Without considering direct costs (to hire interviewers, recruit participants) this method is time-consuming. The time to pass such a questionnaire ranges from a dozen of minutes to an hour, in case of multiple name generators and name interpreters, to which we need to add the time to x appointments with the participants. This constraint is particularly important in the case of longitudinal data and limits considerably the number of persons that can be followed in time (see [Lubbers 2010] for recent questionnaire based longitudi- nal analysis on the integration of 25 Argentinians in Spain). While this was mostly a pen-and-paper approach, computers have been progressively introduced to facil- itate the interviews (generally computer assisted personal interviewing, which still requires the presence of interviewers). Progressively, softwares providing a visual representation of networks are used, and increase both the participation ratio and the quality of answers [Hogan 2007].
Using Bluetooth, WiFi and RFID devices
It has been a couple of years since, technological devices have been used in order to measure on a unsupervised manner human proximity. These devices, worn by individuals, are actively emitting and receiving data packets in a limited spatial range. This data exchange is then considered as a proxy of human proximity. I briey list the datasets I am aware of, with the technology they used. This list is limited to direct device-to-device contact datasets. It excludes access-point based datasets, such as WiFi logs [Henderson 2004, McNett 2005] and records of visible GSM cell towers [Eagle 2006]. The fact that two devices send information to a common antenna eectively means that these devices are in the same area, but given the size of the area, it only corresponds to a physical copresence in the same room/place. Table 1.1 summarizes the main characteristics of the datasets relying on direct device-to-device interaction.
Table of contents :
1 Introduction
1.1 A biased overview of the network science landscape
1.1.1 The complex network paradigm
1.1.2 Dynamical processes on complex networks
1.1.3 Network dynamics
1.2 Mining human interactions
1.2.1 Before the technological era
1.2.2 Using Bluetooth, WiFi and RFID devices
1.2.3 The SocioPatterns collaboration
1.2.4 Self-reported data vs behavioral data
1.3 Structure of the following chapters
2 Statistical analysis of face-to-face proximity data
2.1 Some useful network concepts
2.2 Interactions in dierent environments: museum and conferences
2.2.1 Dynamical burstiness
2.2.2 Network static characteristics
2.2.3 Distances network
2.2.4 Discussion
2.3 Primary school
2.3.1 School composition and category structure
2.3.2 Results
2.3.3 Discussion
2.4 Partial conclusion and perspectives
3 Testing socio-psychological theories
3.1 Motivations
3.1.1 Drivers of social networks
3.1.2 Socio-psychological theories on virtual networks
3.2 Gender homophily among children
3.2.1 Background about gender homophily among children
3.2.2 Results
3.2.3 Discussion
3.3 Physical interactions versus online social networks
3.3.1 The Live-Social Semantics platform
3.3.2 Results
3.3.3 Discussion
3.4 Partial conclusion and perspectives
4 Modeling the dynamics of encounters
4.1 Motivations
4.2 Model of interactions in a homogeneous population
4.2.1 Description of the model
4.2.2 Analytical solution with constant transition probabilities
4.2.3 Analytical solution with a rich-get-richer eect
4.2.4 Numerical simulations
4.2.5 Aggregated networks
4.3 Variation on the model
4.3.1 Heterogeneous population
4.3.2 Fluxes in the population
4.4 Partial conclusions and perspectives
5 Disease spreading
5.1 Motivation
5.1.1 Dynamic processes on networks
5.1.2 Modeling disease spreading
5.1.3 Toward more realism in contact patterns
5.1.4 The need of data on contact patterns
5.1.5 Why does contact dynamics matter?
5.2 Simulation of an SEIR model on empirical data
5.2.1 Data collection
5.2.2 Description of the model
5.2.3 Results
5.2.4 Limitations
5.3 Partial conclusion and perspectives
6 Conclusion
A List of publications
Publications
Glossary
Bibliography
