Thursday: 9:10 – 9:35

Description and simulation of dynamic mobility networks A. Scherrer1 P. Borgnat1 , E. Fleury2 , J.-L. Guillaume 3 and C. Robardet 4

1 Universite de Lyon, ENS Lyon, Laboratoire de Physique (UMR 5672 CNRS), France 2 Universite de Lyon, ENS Lyon, INRIA/ARES, LIP (UMR 5668 CNRS), France 3 Universite Pierre & Marie Curie, LIP6 (UMR 7606 CNRS), France 4 Universite de Lyon, INSA-Lyon, LIRIS (UMR 5205 CNRS), France

Abstract

During the last decade, the study of large scale complex networks has attracted a substantial amount of attention and works from several domains. Most of such complex networks are inherently dynamic, with new vertices and links appearing while some old ones disappear. Until recently, the dynamic of these networks was less studied. Most studies that address dynamic networks consider growing models, such as the preferential attachment model or analyze the aggregation of all interactions. Both approaches may miss the real dynamic behavior and there is a strong need for dynamic network models in order to sustain protocol performance evaluations and fundamental analyzes in all the research domains listed above. In this talk, we address the description and the simulation of sensor mobility networks, in which nodes are human beings and relationships (links) are the ability of a wireless communication to take place. Even though such networks have obvious specificities, the in-depth study of their dynamic is an original work, and can have a broader impact on the complex system community. A first contribution is to propose and study a set of rigorous and coherent properties usable as a practical basis for the analysis of dynamic mobility networks that can be easily extended to large complex networks. We introduce some simple methods to describe the network dynamics, based mainly on two approaches. First, we study graph properties, such as the number of links or the average degree, as function of time (possibly in a multivariate way), so as to give an empirical statistical characterization of the dynamics. Second, we compute global indicators from the dynamics of the network (stability of connected components, triangles creations, existence of communities) and more specially the activities of the link – indicators that are not simply related to a succession of static snapshots of networks. The proposed methods come from various research domains (signal processing, graph theory and data mining). This emphasizes the necessity of interdisciplinary research since dynamic networks are becoming a central point of interest, not only for engineers and computer scientists but also for people in many other fields. We applied those methods on two real-life dynamic mobility networks, based on sensor measurements. The chosen analysis, directly from the data of real dynamical networks, has the interest that it is independent from any modeling of the dynamics, or of individual agents. The second contribution is to propose simulation models founded on the observations made though our extensive set of analyzes. These models aim at reproducing the major properties of the dynamic mobility network under study. By introducing several models, we are able to highlight the diversity of properties that are needed to characterize such networks. Furthermore, our models provide insight into existing notions of dynamic networks and demonstrate that the structure and the dynamics are complex and are not a direct consequence of the contact and inter-contact durations. Proposing such models is crucial since it enables a validation of the ongoing research conducted in the various areas that deal with dynamic networks. It has also many applications in performance evaluation for instance.

_________________________________________________________________________________________

Thursday: 9:40 – 10:20

Follow the Money: Using Dollars as Proxies for Human Dispersal and Epidemic Modeling T. Geisel

Max Planck Institute for Dynamics and Self-Organization & Faculty of Physics, University of Göttingen & Bernstein Center for Computational Neuroscience Göttingen

Abstract

The efficiency of epidemic modelling and forecasts has suffered in the past from a poor description of the spatial dynamics. Accurate models are needed e.g. to test potential strategies to control the spread of an epidemic. While the local infection dynamics is well understood for many diseases, little was known about the statistical laws by which humans and their germs disperse. We have simulated the dispersal of pathogens by international air traffic in a comprehensive network model and used it to forecast the spreading of SARS; it can be used to test the efficiency of various control strategies. To obtain a better spatiotemporal resolution we need the statistical laws governing human travel on all scales, i.e. by all means of transportation. As accurate data were previously not available, we have studied this problem empirically and theoretically using the dispersal of dollar bills as a proxy. The time dependent probability density obtained in this way exhibits pronounced spatiotemporal scaling and superdiffusive spreading, which we model by an ambivalent Lévy random walk. The empirical data can be described very accurately in terms of a bifractional diffusion equation with few parameters.

References: [1] D. Brockmann, L. Hufnagel, and T. Geisel, "The scaling laws of human travel", Nature 439, 462 (2006). [2] L. Hufnagel, D. Brockmann, and T. Geisel, "Forecast and control of epidemics in a globalized world", PNAS, 101, 15124 (2004).

_________________________________________________________________________________________

Thursday: 10:50 – 11:30

From complex networks to human dynamics A.-L. Barabasi

Center for Complex Network Research, Northeastern University

_________________________________________________________________________________________

Thursday: 11:30 – 12:10

Dynamics of the network of interactions in a simple model of flocking M. Nagy and T. Vicsek

Department of Biological Physics, Eoetvoes University

Abstract

The collective motion of self-propelled particles with simple velocity alignment and soft-core repulsion rules result in realistic flocks displaying rich behavioral patterns. The formation and disintegration of the groups of particles and the evolving system of interactions can be best captured by analyzing the underlying network dynamics, where two nodes (particles) are linked if they are at the given moment within the interaction radius. Many interesting questions arise, including aspects involving percolation theory (whether communication between particles at distant point is possible) or link stability (whether interacting particles stay in touch for a long or a short time, etc.). In this talk we shall address such questions demonstrating that a network approach combined with simulations of simple flocking models can give a useful insight into the interesting details of the dynamics of interacting mobile entities.

_________________________________________________________________________________________

Thursday: 12:15 – 12:40

Correlation clustering on scale-free networks Z. Néda, M. Ercsey-Ravasz, M. Varga and B. Molnár

Babeş-Bolyai University, Department of Theoretical Physics

Abstract

Correlation clustering [1-3] is studied on randomly diluted and scale-free networks. The network has positive as well negative links, and the problem is to produce a clustering of the vertices which maximizes the number of positive edges within clusters and also the number of negative edges between clusters. The problem is known to be NP hard. Here simulated annealing and Monte Carlo renormalization methods are used to find the optimal clusterization of the agents. Previously this problem was considered for globally coupled networks [4], and it was observed that the relative size of the dominant cluster (r) in function of the density of positive links (q) exhibits a phase transition type behavior. Considering diluted and scale-free networks with a constant dilution density, the phase transition will be similar with the one observed for globally coupled networks. In the thermodynamic limit the r(q) curves show a sharp step-like variation in the vicinity of the q=0.5 density of the positive connections (r=0 if q<0.5 and r=1 if q>0.5) . A more interesting result is obtained, when fixing the average number of connections per node. In this case a non-trivial phase transition is observed. The location of the transition point shifts more and more toward the higher values of q, and after this transition point the r(q) curves for different system sizes overlap with each other. It was established that in such cases also the topology of the networks has an important role. The results obtained with the simulated annealing and Monte Carlo optimization methods are also in good agreement with the results obtained by a novel Molecular Dynamics optimization approach [5] to correlation clustering.

References: [1] N. Bansal, A. Blum and S. Chawla, Machine Learning, Special Issue on clustering, vol. 56 (2004) 89. [2] M. Charikar, V. Guruswami and A. Wirth, Journal of Computer and System Sciences, vol. 71 (3) (2005) 360. [3]. I. Giotis and V. Guruswami, Theory of Computing, vol. 2 (2006) 249. [4] Z. Neda, R. Florian, M. Ravasz, A. Libal and G. Gyorgyi; Physica A, vol. 362 (2) (2006) 357. [5] R. Sumi and Z. Neda, Molecular Dynamics approach to correlation clustering, Int. J. Mod. Phys. C, in press.

_________________________________________________________________________________________

Thursday: 14:00 – 14:25

Information spreading in dynamical networks of mobile agents F. Peruani, G. Sibona, S. Sadhu and N. Ganguly

Institute of Complex Systems Paris, Ile-de-France & CEA

Abstract

The understanding of information propagation through a system of moving agents is crucial for many applications, ranging from chemical reactions to epidemic spreading. A particular example of such a process is the propagation of an information package through a system of mobile agents (as in peer-to-peer SMS mobile telephony). Here we will assume a very simple information dynamics in which agents have three states (analogous to excitable media): quiescent (agent without message and susceptible to receive one), excited (agent holding the message), and refractory (agent not able to receive or transmit the message). The dynamics is such that once excited an agent becomes first refractory, and then quiescent again. I will focus on the study of an stochastic information transmission in which the information is transmitted only when a susceptible agent keeps physical contact with an infected one during a non-vanishing time. The model allows us to explore a wide range of densities, bridging the gap between non-spatial and lattice models. I will show that the information dynamics can be described by a mean-field approach, and give expressions for the steady states which strongly depend on the spatial agent dynamics. In particular I will show that there exist three regimes with the agent active speed v: "information extinction" for small v, an "endemic" regime in which the number of non-informed agents is inversely proportional to v, and a third regime, model dependent, for large v, proportional to v to the power A-1, where A is the scaling exponent of the mean collision time with v. These results can be applied to estimate the mean broadcasting time (i.e., time at which all agents have been informed), and the mean routing time between an agent A and an agent B separated by a distance d.

References: [1] F. Peruani and G. Sibona, ,"Dynamics and Steady States in Excitable Mobile Agent System", Phys. Rev. Lett. 100, 168103 (2008). [2] Sanjib Sadhu, Niloy Ganguly, Fernando Peruani, Romit Roy Choudhury, “Information delivery using SIRS dynamics in DTN” (2008).

_________________________________________________________________________________________

Thursday: 14:30 – 14:55

Synchronization and Consensus in Time-Varying Networks F. M. Atay

Max Planck Institute for Mathematics in the Sciences, Germany

Abstract

The complexity of networks arises not only from the complexity of the topological structure, but also from the time evolution of the topology. Such networks are common, for instance, in systems of moving agents, particles, mobile phone users, etc. The dynamics taking place on networks is correspondingly more complicated when the network structure itself is changing in time. In particular, the study of collective behavior such as synchronization and consensus on time-varying networks is a challenging topic with many practical implications. This talk will present our recent results in this area. We will introduce a quantitative measure of network synchronizability that is rigorously justified, and use it to analyze several network models, including i.i.d. sequences of random graphs with fixed wiring probability, groups of graphs with random switches between the individual graphs, and graphs with temporary random failures of nodes. We find that the temporal variation and randomness of the connection topology can enhance synchronizability in many cases; however, there are also instances where they reduce synchronizability.

References: [1] W. Lu, F.M. Atay, and J. Jost, "Chaos synchronization in networks of coupled maps with time-varying topologies." European Physical Journal B, 63:399-406, 2008. [2] W. Lu, F.M. Atay, and J. Jost, "Synchronization of discrete-time dynamical networks with time-varying couplings." SIAM J. Math. Analysis, 39(4):1231-1259, 2007.

_________________________________________________________________________________________

Thursday: 15:00 – 15:25

Global Feedback Control of Turbulence on Complex Networks at the Edge of Chaos S. Gil and A. S. Mikhailov

Abteilung Physikalische Chemie, Fritz-haber-Institut der Max-Planck-Gesellschaft, Germany

Abstract

The effect of global feedback on a high-dimensional chaotic (turbulent) system of phase oscillators is studied on random networks. We show that chaos can be suppressed and a transition to synchronous oscillations can be induced. Our attention is focused on the transition scenario and the properties of patterns which are found at the edge of chaos. The emerging coherent patterns represent various self-organized active (sub)networks whose size and behavior can be controlled.

_________________________________________________________________________________________

Thursday: 15:30 – 15:55

Structural distance of networks retraces the evolutionary relationships A. Banerjee

Max Planck Institute of Molecular Genetics, Germany

Abstract

In self-organized systems, some hidden dynamics play a role to organize the connections between the components of that system. Due to the interplay between the structure and dynamics, biological and other networks from different areas followed by different dynamics are expected to have different structures while networks constructed from the same evolutionary process have structural similarities. Studying the common features and universal qualities shared by a particular class of networks in biological and other domain is one of the important aspects for evolutionary study. Measuring the structural differences one can retrace the evolutionary relation between two systems. Here we introduce a method, to estimate the topological commonality, that quantify the difference between two network structures of different sizes. Applying this measurement procedure we show that the architectures of the networks are more similar within the same class than the outside of their class. We analyze 43 cellular networks from different species and mark the prominent separation of three groups, Bacteria, Archaea and Eukarya. That is well captured in our findings that support the other cladistic results based on gene content and ribosomal RNA sequences. Thus we show that how evolutionary relationship can be elucidated from the structural distances measured by our method.

_________________________________________________________________________________________

Thursday: 16:00 – 16:25

The Blind Watchmaker network: scale-freeness and evolution P. Minnhagen and S. Bernhardsson

Department of Theoretical Physics, Umeå University, Sweden & Center for Models of Life, Denmark

Abstract

To characterize the structure of a network, researchers often measure its degree distribution N(k), the number of nodes with k links attached. Numerous studies have found that real-world networks often have very broad degree distributions for larger k, N(k) ∝ kγ These fat tailed distributions approximate a power law in their structure [1]. Biological networks are particularly interesting because the structure of these networks have, directly or indirectly, arisen through the process of evolution by natural selection. These networks have been constructed as if by a blind watchmaker, through the interplay between a random stochastic evolution and a natural selection process [2]. So what can we learn from the observation that a biological network such as the network of the metabolism of a cell has a power law distribution [3]? In order to answer this question we define and investigate a blind watchmaker network. In this paper [4] we demonstrate that the empirically observed degree distributions for networks of the cellular metabolism for simple organisms are good approximations of this random structure. We start from a simplified network model, the constrained-ball-in-boxes (CBB) model [5]. Here, nodes are viewed as boxes and the link ends attaching to these nodes are numerated (distinguishable) balls in this boxes. The balls in the boxes are given a ranking which can been seen as a time order of the connections. In this way several different definitions of a state can be made and we introduce a way of solving the maximum entropy problem using a random process. One definition of a state, together with a process constraint, gives a power-law distribution with slope 2. Network constraints are also introduced and the result is compared to a set of 107 metabolic networks, with a striking similarity. This means that the random process, driven by mutations, that governs the dynamics of the networks treats this definitions of a state unbiased and hence the result will have the maximum entropy. It also means that natural selection has had no or little effect on the networks node degree distribution. The degree distribution is not the only network property that is important for the network function. In order for the Blind watchmaker network to make sense, any other measured network property for real networks should be reachable within this scheme without destroying the power-law shape of the degree distribution. Some network properties, like the clustering coefficient, will be discussed and compared (unpublished).

References: [1] MEJ Newman, A.-L.. Barabási and DJ. Watts (2006): The Structure and dynamics of networks. Princeton: Princeton University press. [2] R. Dawkins (1985): The blind watchmaker: Why the evidence of evolution reveals a universe without design. Norton. [3] A. Wagner (2003): Does selection mold molecular networks. Science STKE 41. [4] P. Minnhagen and S. Bernhardsson (2008): The Blind Watchmaker Network: Scale-freeness and Evolution, PLoS ONE 3(2): e1690. [5] P. Minnhagen and S. Bernhardsson (2007): Optimization and scale-freeness for complex networks. Chaos 17. [6] H. Ma and A.P. Zeng (2003): Reconstruction of metabolic networks from genome

_________________________________________________________________________________________

Thursday: 17:00 – 17:25

Oscillation Patterns in Genetic Feed-Back Networks M. H. Jensen

Niels Bohr Institute, University of Copenhagen, Denmark

Abstract

We model ultradian oscillations in four different eucaryotic systems: Hes1, p53-mdm2, NF-kB and Wnt-Notch. In each of the systems we identify the feed-back loops for the genetic regulations. Oscillations are possible when time delays are present, either by directly introducing a delay, by many steps in the loops or by saturated degradation. The oscillations are important for apoptosis and control of inflammation. The Wnt-Notch system is essential in embryo segmentation and we introduce a model in which the Wnt oscillates by itself but drives the Notch cycle out of phase with the Wnt cycle, in good agreement with experimental observations. We further identify the feed-back dynamics by means of symbolic dynamic and derive general symbolic rules for the oscillatory patterns.

References: [1] S. Krishna, M.H. Jensen and K. Sneppen, "Spiky oscillations in NF-kappaB signalling", Proc.Nat.Acad.Sci. 103, 10840-10845 (2006). [2] S. Pigolotti, S. Krishna and M.H. Jensen, "Oscillation patterns in negative feedback loops", Proc.Nat.Acad.Sci. 104, 6533-6537 (2007). [3] G. Tiana, S. Krishna, S. Pigolotti, M.H. Jensen and K. Sneppen, "Oscillations and temporal signalling in cells", Physical Biology 4, R1-R17 (2007)

_________________________________________________________________________________________

Thursday: 17:30 – 17:55

Theory of α-BiNs: Alphabetic Bipartite Networks A. Mukherjee, F. Peruani, M. Choudhury, A. Maiti, A. Deutsch, and N. Ganguly

Indian Institute of Technology Kharagpur, India

Abstract

Life and language are discrete combinatorial systems (DCSs) in which the basic building blocks are finite sets of elementary units: nucleotides or codons in a DNA sequence and letters or words in a language. Different combinations of these finite units give rise to potentially infinite numbers of genes or sentences. This type of DCS can be represented as an Alphabetic Bipartite Network (α-BiN) where there are two kinds of nodes representing the elementary units and their combinations. There is an edge between a node corresponding to an elementary unit u and a node corresponding to a particular combination v, if u is present in v. The partition consisting of the nodes representing elementary units is fixed, while the other partition is allowed to grow unboundedly. Here, we extend recently derived analytical findings [1] for α-BiNs and empirically investigate two real world systems: the codon-gene network and the phoneme-language network [2]. The evolution equations for α-BiNs under different growth rules are derived, and the corresponding degree distributions computed. It is shown that asymptotically the degree distribution of α-BiNs can be described as a family of beta distributions. The one-mode projections of the theoretical as well as the real world α-BiNs are also studied. We propose a comparison of the real world degree distributions and our theoretical predictions as a means for inferring the mechanisms underlying the growth of real world systems.

References: [1] F. Peruani, M. Choudhury, A. Mukherjee and N. Ganguly, “Emergence of a non-scaling degree distribution in bipartite networks: A numerical and analytical study”, Europhys. Lett. 79, 28001 (2007). [2] A. Mukherjee, M. Choudhury, A. Basu, and N. Ganguly, Journal of Quantitative Linguistics (forthcoming), http://arxiv.org/abs/physics/0610120.

_________________________________________________________________________________________

Thursday: 18:00 – 18:25

Games on endogenous networks D. Chavalarias1 and J. P. Cointet 2

1 Institute of Complex Systems Paris, Ile-de-France & CREA, France 2 TSV, INRA, France

Abstract

Aggregated phenomena in social science and economics are highly dependent on the way individuals interact. To help understanding the interplay between socio-economic activities and underlying social networks, we propose an analytical and computational insight into the role of endogenous networks formation in emergence and sustainability of cooperation and exhibits an alternative to the role of cliquishness in sustaining cooperation that push forward the role of frequencies of interactions. The study focuses on heterogeneous equilibriums and emergence of cooperation that are the two stylized facts that this model successfully reconstructs.

_________________________________________________________________________________________

Friday: 9:00 – 9:25

Topological efficiency and efficient spatial organization in self organized networks of termites A. Perna1,2, C. Jost1, S. Douady3, S. Valverde1,4, P. Kuntz 2, G. Theraulaz1

1 Centre de Recherches sur la Cognition Animale, CNRS UMR 5169, Universite Paul Sabatier, France 2 Ecole Polytechnique de l’Universite de Nantes, France 3 Laboratoire Matiere et Systemes Complexes, Universite Paris 7, France 4 ICREA-Complex Systems Lab, Universitat Pompeu Fabra, Spain

Abstract

Transportation networks are a key component of human societies that enable efficient communication at a low cost. Like humans, also most animal species build transportation networks. However, unlike human built transportation networks where planning and decision contribute to shape the final network topology, animal built networks only result from the interactions between animals and the environment and are completely un-planned and self-organized. Here we study the topological properties of networks of galleries in termite nests. These are characterised by the fact of being one of the few known examples of three-dimensional transportation networks. Networks built by the termite Cubitermes have far better than random transportation efficiency, but they do not reach theoretical optimal performance. We suggest that the topology of these networks is shaped from a multiobjective optimisation process where a number of requirements, such as resilience to external attacks and the presence of spatial constraints, limit the ability of the system to achieve maximal transportation performance. In addition, Cubitermes networks present a detectable organisation in layers interconnected by vertical ramps of different length. The efficiency of the layered organisation depends on how well single ramps ensure fast connections between many different layers and is related to -but distinct from- the more classical measure of topological network efficiency. The complex network approach appears to be a promising tool to understand complex termite built structures.

_________________________________________________________________________________________

Friday: 9:30 – 9:55

Modelling the diffusion of epidemic considering change in behaviour: The case study of Poland K.Rakocy1, J. Zając2, A. Nowak 3

1 Center for Complex Systems, Institute of Social Studies, University of Warsaw, Poland 2 Dept. of Psychology, University of Warsaw, Poland 3 Center for Complex Systems, Institute of Social Studies, University of Warsaw, Poland

Abstract

The existing models of infectious diseases emphasize inevitability of pandemics, yet they do not take into consideration the dynamic nature of social behaviour. We use dynamical network approach and multi-agent simulation to examine how the classical SIR model of epidemics changes when effects of media coverage are considered. The latter influences behaviours such as social contacts, internal migration and fleeing and in consequence modifying the probability of contact and infection. In our model high granularity data on commuting and travelling in the whole country gathered by road transport authorities are included. Moreover, the SIR model is validated by medical statistics on number of influenza cases in each county. Additionally, data concerning change of behaviour as effect of exposure on information about pandemic was collected in 2 surveys. The data regarding social behaviour is based on 2 sources: general national representative survey (CAPI; N=10000) and more specific Web survey (N=3000), with manipulation regarding distance from the site of epidemics. We take a class of small-world networks as a basis for modeling to create data driven model. We improve current model enabling modifications of transport networks (evolution of weighted network) and therefore flows of people between locations as the epidemics spreads. An instant messenger communication network, with high resolution (aggregated on county level) is used to compare with travelling network. These mixes of network and survey data enable us to test influence of different strategies of prevention and mass media communication on epidemic spread.

References: [1] Bailey, N. T. J. 1975 The Mathematical Theory of Infectious Diseases and Its Applications, Hafner Press, New York [2] Ball F., Mollison D., Scalla-Tomba G, Epidemics with two levels of mixing The Annals of Applied Probability 1997, vol 7, no 1., 46-89 [3] Cohen R., Erez K.,ben-Avraham D., Havlin S., Resilience of the Internet to Random Breakdowns, Physical Review Letters, Volume 85, Number 21, 2000. [4] Colizza, Barrat, Barthelemy & Vespignani, 2006. [5] Pastor-Satorras R,, Vespignani A. Epidemic Spreading in Scale-Free Networks, Psychical Review Letters, volume 86, number 14, 2001

_________________________________________________________________________________________

Friday: 10:00 – 10:25

Dynamics Of Packet Traffic In A Data Network Model Under Normal & DDoS Attack Conditions A. T. Lawniczak1, H. Wu1, B. Di Stefano2

1 Department of Mathematics and Statistics, University of Guelph, Canada 2 Nuptek Systems Ltd., Toronto

Abstract

Dynamics of packet traffic in data communication networks can be complex and often are not well understood. Understanding these complex dynamics is important for their control, prediction purposes, detection of denial of service (DoS) attacks, and for the data networks design. The most common implementation of DoS attack is distributed DoS (DDoS) attack in which the attack is carried by using many computers located at various nodes of the network. These computers are used without any knowledge of their legitimate owners and they are called “zombies”. Since DDoS attacks are network-wide attacks it is very difficult to detect and stop them. They affect packet traffic dynamics significantly and lead to very congested areas of the network. The engineering community has described data networks architectures and studied them by means of a layered and hierarchical abstraction called OSI (Open Systems Interconnection) Reference Model. The Network Layer of the OSI Reference Model is responsible for routing packets across the network from their sources to their destinations and for control of congestion in data networks. Using an abstraction of the Network Layer and its modification allowing modeling DDoS attacks, that we developed, we investigate packet traffic spatio-temporal dynamics in our data network models of packet switching type under normal and anomalous conditions, i.e. DDoS attacks. Under normal conditions we explore how these dynamics are affected by network connection topology and routing algorithms, in particular near the phase transition point from free flow to congestion. Under anomalous conditions we focus on the “ping” DDoS attacks in which “huge” numbers of “ping” requests are directed to the victim computers rendering them effectively unavailable to legitimate traffic. We explore how “ping” DDoS attacks change “natural” spatio-temporal dynamics of packet traffic patterns. Additionally, we study the effects of DDoS attacks on network performance indicators. We consider various network connection topologies and dynamic and static routing algorithms. We present selected simulation results and analyze them.

_________________________________________________________________________________________

Friday: 10:50 – 11:15

Sequential spreading processes and the impact of non-Poissonian activity on them Y. Berchenko and M. Teicher

Interdisciplinary Brain Research Center, Bar Ilan University, Israel

Abstract

Many epidemiological models assume a parallel transmission where an infected individual can infect several susceptible individuals in a single time step. Often, such as in the case of sexually transmitted diseases, this is inappropriate and a sequential process should be considered. In such a sequential process an individual creates new contacts one at a time, according to a renewal process with a random waiting time τc . Assuming a large population, we can view the spreading of the disease as a branching process, and obtain the distribution of the number of infections that an infected individual cause. Thus we can determine wether a disease starting at a single individual will result in an epidemic. The case where an infected individual remains infected (and infectious) forever is quite Straight-forward. However, if we allow him to remain infectious only for a (random) period τinf - things become non-trivial. We now find that: i) Poissonian statistics - if τc and τinf are both distributed exponentially, as they are usually assumed, than the case where they have the same distribution (i.e. with the same mean) is the critical case, and will not result in an outbreak of an epidemic. ii) Non-Poissonian statistics - in contrast to (i), if the distributions of τc and τinf are not Poissonian, but rather fat tailed, and they have the same distribution than this will result in an outbreak of an epidemic. This is especially interesting since the reality is that many, if not most, of the processes, such as meeting new contacts, follow a fat-tailed statistic and not Poissonian and time homogenous. In addition, we also find that case (iii), where τc follows an exponential distribution and τinf follows a fat-tailed distribution, can be easily adapted to serve as a very parsimonious model for the evolution of networks with a scale free degree distribution.

_________________________________________________________________________________________

Friday: 11:20 – 11:45

Stability anaysis of peer to peer networks Bivas Mitra, Fernando Peruani and N. Ganguly

Indian Institute of Technology, Kharagpur, India

Abstract

Understanding the dynamics of large scale complex networks is a major challenge in front of the network research communities. Many important networks like Internet consisting of a large number of computers, Web networks, pee to peer networks, social networks, biological networks are conceptualized as large scale complex networks. In peer to peer networks, participating nodes may leave the network (peer churn) without any central coordination. This frequently partitions the network into small disconnected components and it makes the overlay network highly dynamic in nature. Attack mounted upon important nodes also disrupts the connectivity of the networks. In our work, we develop an analytical framework to examine the stability of the various overlay structures against the dynamic behavior of peers like churn and attack. In order to do that, we compute the structure of the deformed network due to these various node disrupting events. We model overlay topologies with the help of random graphs like Erdos Renyi graph, scale free network, superpeer networks, etc. Similarly we model various node disrupting events with the help of a uniform probability framework. In peer churn, probability of removal of a node is constant; on the other hand the highly connected nodes are removed in case of attack. We employ percolation theory and complex network theory to propose the analytical framework. The analytical results are validated with the help of simulation.

References: [1] B. Mitra, F. Peruani, S. Ghose, and N. Ganguly,"Analyzing the Vulnerability of Superpeers Networks Against Attack", proceeding at CCS 07 (14th ACM Conference on Computer and Communications Security). [2] B. Mitra, N. Ganguly, S. Ghose and F. Peruani,"Generalized theory for node disruption in finite complex networks", Phys. Rev. E 78, 026115 (2008). [3] B. Mitra, N. Ganguly, S. Ghose and F. Peruani, "Stability Analysis of Peer-to-Peer Networks Against Churn", Pramana - J. Phys. 71, 263 (2008).

_________________________________________________________________________________________

Friday: 11:50 – 12:15

Guiding the Emergence of Structured Network Topologies: A Programmed Attachment Approach R. Doursat1 and M. Ulieru2

1 Complex Systems Institute, CNRS & Ecole Polytechnique, France 2 Canada Research Chair, Canada

Abstract

Emergent collective behavior, such as dynamic network self-organization, can result from the interactions between a multitude of agents driven by simple rules, a fact that is often touted as the hallmark of complex systems. However, a closer look reveals that in many well-known families of models (pattern formation, swarm intelligence, complex networks, etc.) “complexity” translates into emerging patterns that are either freely random, or determined by boundary conditions—or anywhere in-between. On the one hand, spots and stripes, meandering bird flocks, or hub-forming social encounters are fairly homogeneous or self-similar phenomena that can be described by statistical laws. They are typically stochastic, generating order from amplified fluctuations. On the other hand, the formation and stabilization of ant trails is constrained by landmarks such as the nest and food sources. Many other examples present a mix of internal homogeneity and external constraints. Cases exhibiting an intrinsic architecture that is neither repetitive nor imposed by the environment are much less frequent or studied. One salient exception is the development of living organisms. Biological morphogenesis demonstrates the possibility of self-organized and elaborate structure formation. Segments and organs self-assemble in a decentralized fashion, arranging themselves in specific structures that resemble the products of human engineering design. This is because the agents (cells) carry a sophisticated set of rules (DNA) that endows them with a repertoire of non-trivial behaviors, and guide how they differentiate through various signals representing relative positional information. There is great demand for such capabilities of guided self-assembly in many distributed computing systems, e.g., arrays of micro-processors, mobile sensors, internet security hosts, reconfigurable robot modules, or swarm robots. Such capabilities are also essential to the management and engineering of complex techno-social networks made of myriads of mobile devices, software agents and human users, all relying on local rules and peer-to-peer communication, e.g., the design of self-reconfiguring manufacturing plants, self-regulating energy grids, or self-deploying emergency taskforces. We present preliminary results of an original model of autonomous network construction and dynamics, in which nodes execute the same program in parallel, however develop into different types according to their (limited) positional awareness. In our model, nodes exchange messages and dynamically create or remove links, based on “ports” and a set of internal state variables derived from discrete “gradients”. Ports and gradients guide the new nodes to specific attachment locations in the network. As the network expands and node positions change, they adapt by switching different subsets of rules on or off—similar to gene activation/inhibition in biological DNA—thus triggering the growth of specific structures such as chains, lattices, and more complicated composite topologies. Simple positive and negative-feedback rules are not sufficient in themselves to create elaborate architectures. Code-carrying nodes and programmed attachment could be the key to unraveling an “eNetwork DNA” that fosters controllable and reproducible self-organization in complex networks.

_________________________________________________________________________________________

Friday: 12:20 – 12:45

FKPP front Propagation on Trees – Extinction Transition Caused by Diffusion Y. E. Marukva1, R. Cohen2, N. M. Shnerb1

1 Department of Physics, Bar-Ilan University, Israel 2 Department of Mathematics, Bar-Ilan University, Israel

Abstract There is a growing interest in dynamical processes taking place on a network, and not only in the dynamics of the network itself. In our work, we embedded the FKPP (Fisher Kolmogorov Petrovsky Piskunov) equation on a tree topology. The FKPP equation is the most generic reaction-diffusion equation, and it is the continuum limit for many discrete processes. The Fisher front velocity in Cayly trees was calculated, and a puzzling difference between the behavior of a single node and of the layer as a whole was found. For a large enough diffusion coefficient, the direction of the Fisher velocity on single nodes is opposite to that on the layers. This phenomenon leads to zero occupation of the single nodes, although the population in the whole network grows. The transition point was found analytically for Cayly trees. For random trees (with a Poison number of branches with average z), we discovered that the Fisher velocity converges to the Cayly tree (with exactly z branches) velocity. We also found numerically the deviation of the transition point of random trees from that of Cayly trees.