Bulletin of the American Physical Society
APS March Meeting 2010
Volume 55, Number 2
Monday–Friday, March 15–19, 2010; Portland, Oregon
Session D13: Focus Session: Complex Networks II |
Hide Abstracts |
Sponsoring Units: GSNP Chair: Corey S. O'Hern, Yale University Room: B112 |
Monday, March 15, 2010 2:30PM - 2:42PM |
D13.00001: Origins of Chaos in Autonomous Boolean Networks Joshua Socolar, Hugo Cavalcante, Daniel Gauthier, Rui Zhang Networks with nodes consisting of ideal Boolean logic gates are known to display either steady states, periodic behavior, or an ultraviolet catastrophe where the number of logic-transition events circulating in the network per unit time grows as a power-law. In an experiment, non-ideal behavior of the logic gates prevents the ultraviolet catastrophe and may lead to deterministic chaos. We identify certain non-ideal features of real logic gates that enable chaos in experimental networks. We find that short-pulse rejection and the asymmetry between the logic states tends to engender periodic behavior. On the other hand, a memory effect termed ``degradation'' can generate chaos. Our results strongly suggest that deterministic chaos can be expected in a large class of experimental Boolean-like networks. Such devices may find application in a variety of technologies requiring fast complex waveforms or flat power spectra. The non-ideal effects identified here also have implications for the statistics of attractors in large complex networks. [Preview Abstract] |
Monday, March 15, 2010 2:42PM - 2:54PM |
D13.00002: Non-Equilibrium Statistical Physics of Currents in Network Queuing Michael Chertkov, Vladimir Chernyak, David Goldberg, Konstantin Turitsyn We present a framework for studying large deviations of currents in a queuing network viewed as a non-equilibrium system of interacting particles. The network is completely specified by its underlying graphical structure, the number of servers (type of interaction) at each node, and the Poisson transition rates between nodes/stations. We focus on analyzing the statistics of currents over the network for the class of stable (statistically steady) networks. Some of our results are general (and surprising) explicit statements and some are conjectures, validated on a network with feedback which allows an independent spectral analysis. In particular, we show that for sufficiently strong atypical currents the system experiences a dynamical transition into a ``congested" regime, characterized by the saturation of certain servers in the network. We also discuss possible applications of these results for the analysis and control of traffic flows in transportation networks and of scheduling power flows in electric grids. [Preview Abstract] |
Monday, March 15, 2010 2:54PM - 3:06PM |
D13.00003: The Phase Transitions of Self-similar Small-world Networks Trent Brunson, Stefan Boettcher A novel set of self-similar networks called Hanoi networks\footnote{S. Boettcher, B Gon\c{c}alves, Europhysics Letters \textbf{84}, 30002 (2008).} (HN) have been developed to study the critical phenomena of small-world networks using the renormalization group (RG). Physically, HNs contain a more desirable geometry than random small-world networks. Their structure consists of a one-dimensional backbone with a hierarchy of long-range bonds, which allows the flexibility of studying planar and non-planar networks with either a regular or exponential degree distribution. The RG and Ising model simulation results for HNs reveal unique phase transitions and non-universal behavior, which can be attributed to their hierarchical structure.\footnote{See also http://www.physics.emory.edu/faculty/boettcher/.} [Preview Abstract] |
Monday, March 15, 2010 3:06PM - 3:18PM |
D13.00004: A totally asymmetric exclusion process with hierarchical long range connections Jakub Otwinowski, Stefan Boettcher A non-equilibrium particle transport model, the totally asymmetric exclusion process, is studied on a one-dimensional lattice with a hierarchy of fixed long-range connections\footnote{Journal of Statistical Mechanics, P07010 (2009).}. This model breaks the particle-hole symmetry observed on an ordinary one-dimensional lattice and results in a surprisingly simple phase diagram, without a maximum-current phase. Numerical simulations of the model with open boundary conditions reveal an emergent disorder in the density profile, which is confirmed analytically. [Preview Abstract] |
Monday, March 15, 2010 3:18PM - 3:30PM |
D13.00005: Impact of commuting in epidemic invasion threshold Duygu Balcan, Alessandro Vespignani Structured metapopulation models constitute one of the main approaches to the modeling of epidemic spread. While the contagion dynamics in each subpopulation is realized in a coarse-grained scheme, these models rely on the integration of multi-layered mobility data and accurate representations of human movements in different scales. Different scales are not just embedded in the spatial component of the process (long-range versus short-range movements) but also in the duration of the trips (long versus short visits). In this context, commuting, the daily movement of people between home and workplace or home and school, is one of the essential ingredients in multi-scale mobility networks. We consider an SIR-epidemic in a metapopulation system whose subpopulations are coupled by commuting. We investigate analytically and numerically the global epidemic invasion threshold. [Preview Abstract] |
Monday, March 15, 2010 3:30PM - 3:42PM |
D13.00006: Comparing large-scale computational approaches to epidemic modeling: agent based versus structured metapopulation models Bruno Gon\c calves, Marco Ajelli, Duygu Balcan, Vittoria Colizza, Hao Hu, Jos\'e Ramasco, Stefano Merler, Alessandro Vespignani We provide for the first time a side by side comparison of the results obtained with a stochastic agent based model and a structured metapopulation stochastic model for the evolution of a baseline pandemic event in Italy. The Agent Based model is based on the explicit representation of the Italian population through highly detailed data on the socio-demographic structure. The metapopulation simulations use the GLobal Epidemic and Mobility (GLEaM) model, based on high resolution census data worldwide, and integrating airline travel flow data with short range human mobility patterns at the global scale. Both models provide epidemic patterns that are in very good agreement at the granularity levels accessible by both approaches, with differences in peak timing of the order of few days. The age breakdown analysis shows that similar attack rates are obtained for the younger age classes. [Preview Abstract] |
Monday, March 15, 2010 3:42PM - 3:54PM |
D13.00007: Catastrophic cascade of failures in interdependent networks Sergey V. Buldyrev, Shlomo Havlin, Roni Parshani, Gerald Paul, H. Eugene Stanley Many complex systems are coupled together and therefore should be modeled by multiple interdependent networks. For example, a power network in which the nodes are power stations and a communication network in which the nodes are computers, are interdependent. In interdependent networks, failure of nodes in one network, cause failure of dependent nodes in another network. This may happen recursively and can lead to a cascade of failures: a failure of a very small fraction of nodes in one network may lead to the complete fragmentation of a system. We provide a framework for understanding the robustness of interacting networks subject to such cascading failures and provide a basic analytic approach that may be useful in future work. We present exact analytical solutions for the critical fraction of nodes that upon removal will lead to a failure cascade and to a complete fragmentation of two randomly connected interdependent networks in terms of the generating functions of their degree distributions. Surprisingly, networks with broad degree distributions are more vulnerable to random failures than networks with narrow degree distributions. [Preview Abstract] |
Monday, March 15, 2010 3:54PM - 4:06PM |
D13.00008: Cluster aggregation model for first-order percolation transitions Byungnam Kahng The evolution of the Erdos-Renyi (ER) network by adding edges can be viewed as a cluster aggregation process. Such ER processes can be described by a rate equation for the evolution of the cluster-size distribution, in which the connection kernel K$_{ij}\sim $ij, the product of the sizes of two merging clusters. Here, we study more general cases in which K$_{ij}$ is sub-linear as K$_{ij}\sim $ (ij)$^{w}$ with 0 $\le $ w $<$ 1/2, finding that the percolation transition (PT) is discontinuous. Moreover, when the ER dynamics evolves from proper initial conditions, PT is also discontinuous. The rate equation approach for such discontinuous PTs enables us to uncover the mechanism underneath the explosive PT under the Achlioptas process (AP). We also study the AP problem in scale-free networks, finding that a first-order transition does not always occur: a continuous transition is also possible depending on the degree distribution of the scale-free network. This originates from the competition between the AP that discourages the formation of a giant component and the existence of hubs that encourages it. We also estimate the value of the characteristic degree exponent that separates the two transition types. [Preview Abstract] |
Monday, March 15, 2010 4:06PM - 4:18PM |
D13.00009: A fixed point theorem for a general epidemic model Adam Lucas We provide a rigorous axiomatic framework to study the critical behavior of disease spreading on top of a complex network. A necessary and sufficient condition for our general epidemic model to undergo a phase transition is proven. It is known that an {\it epidemic state} undergoes a phase transition when the infection rate surpasses the epidemic threshold. However, for networks having degree-degree correlations, the epidemic threshold has never formally been defined. We define the epidemic threshold as, $\lambda_c := 1/\lambda'$ with $\lambda'$ denoting the largest positive eigenvalue of an operator $T$ given in the axioms of our model. When the {\it epidemic state} is a strictly positive solution to a fixed point equation our model is guaranteed to have a single phase transition. Percolation as well as SIS/SIR epidemic models on complex correlated networks satisfy the axioms of our model. A benefit of our axiomatic framework is that it highlights commonalities in a variety of interacting particle systems. [Preview Abstract] |
Monday, March 15, 2010 4:18PM - 4:30PM |
D13.00010: Dynamical interaction networks Ginestra Bianconi, Juliette Stehle, Alain Barrat We present a modeling framework for dynamical networks in the context of agent based models of social interactions. Agents can be either isolated or in groups of diverse sizes. Each agent's may change state at each time step with probabilities depending on its state and on the time since the last change. Different microscopic laws lead to different behaviors, in particular to different distributions of contact times between individuals. In particular observed fat distributions of interaction times are described by a history dependent transition probability and a reinforcement dynamics that is grounded in a underling cognitive Hebbian mechanism. The modeling framework can be easily extended, and paves the way for systematic investigations of dynamical processes occurring on dynamical networks, and of the role of the networks characteristics such as narrow or broad distributions of contact durations. [Preview Abstract] |
Monday, March 15, 2010 4:30PM - 4:42PM |
D13.00011: Dynamic and topological complexity Malgorzata Turalska, Elvis Geneston, Paolo Grigolini Cooperative phenomena in complex networks are expected to display unusual characteristics, associated with the peculiar topology of these systems. In this context we study networks of interacting stochastic two-state units as a model of cooperative decision making. Each unit in isolation generates a Poisson process with rate $g$. We show that when the cooperation is introduced, the decision-making process becomes intermittent. The decision-time distribution density characterized by inverse power-law behavior is defined as a dynamic complexity. Further, the onset of intermittency, expressed in terms of the coupling parameter $K,$ is used as a measure of dynamic efficiency of investigated topologies. We find that the dynamic complexity emerges from regular and small-world topologies. In contrast, both random and scale-free networks correspond to fast transition into exponential decision-time distribution. This property is accompanied by high dynamic efficiency of the decision-making process. Our results indicate that complex dynamical processes occurring on networks could be related to relatively simple topologies. [Preview Abstract] |
Monday, March 15, 2010 4:42PM - 4:54PM |
D13.00012: Mesoscopic Structure in Complex Networks Joerg Reichardt, Roberto Alamino, David Saad In a complex network, not all nodes are created equal. Rather, they play diverse roles in a network's function which in turn are reflected as patterns in its connectivity. Structural analysis allows to infer the latent roles and functions of nodes purely based on connectivity data. Current research on network structure is either focused at the macro-scale studying global network properties or at the micro level studying properties of individual nodes. The study of the meso-scale, which aims at studying joint properties of groups of nodes, so far has been limited to the detection of cohesive subgroups of nodes, so-called communities. The talk will show that, though important, communities are only one special case of a much wider class of mesoscopic structures called ``stochastic block models'' - after the salient block structure encountered when ordering rows and columns of the adjacency matrix according to the nodes' latent roles. We present an effective and accurate algorithm for latent role inference employing purely Bayesian approach, show that it outperforms competing approaches and present applications to real world data sets that open new frontiers of research in the study of both structure, function and evolution of complex networks from a mesoscopic perspective. [Preview Abstract] |
Monday, March 15, 2010 4:54PM - 5:06PM |
D13.00013: Efficient sampling of graphs with arbitrary degree sequence Charo Del Genio, Hyunju Kim, Zolt\'an Toroczkai, Kevin Bassler Uniform sampling of graphs from a given degree sequence is a fundamental component of measurements on networks, with applications ranging from epidemics through social networks to Internet modeling. Existing graph sampling methods are ill-controlled, with typically unknown mixing times for edge-swap methods and uncontrolled rejections for stub-matching ones. We propose an efficient, polynomial time algorithm that generates statistically independent graph samples from any given degree sequence. The algorithm provides a weight for each sample, allowing observables to be measured uniformly or following any desired distribution over the graph ensemble. Unlike other algorithms, this method always produces a sample, without back-trackings or rejections. For large number of nodes and degree sequences admitting many realizations, the sample weights follow a lognormal distribution. We also propose a fast implementation of the Erd\H{o}s-Gallai degree sequence graphicality test that is used in our algorithm, but is also of general utility. [Preview Abstract] |
Monday, March 15, 2010 5:06PM - 5:18PM |
D13.00014: Robustness of Heterogeneous Supply Networks--New Metrics and Model Kang Zhao, Akhil Kumar, John Yen Existing research on the robustness of complex networks often assumes that nodes in a network have homogeneous roles. Using a supply network as an example, this research develops new robustness metrics, including availability, proximity, accessibility, and connectivity, to reflect the heterogeneous roles of supply nodes and demand nodes in a supply chain. In addition, we propose a new supply network model, which is based on the rewiring of the scale-free network. With the help of computational simulations, we evaluate the new network's robustness under the new metrics. The results show that it outperforms a pure scale-free topology on the metrics of availability and connectivity when both random and targeted disruptions are likely to occur. The unique feature of our approach is that by tuning the rewiring parameter of our model, it is possible to design networks with very similar performance on the availability and accessibility metrics in the presence of both types of disruptions. [Preview Abstract] |
Monday, March 15, 2010 5:18PM - 5:30PM |
D13.00015: Dynamical networks of person to person interactions from RFID sensor networks Lorenzo Isella, Ciro Cattuto, Alain Barrat We present a scalable experimental framework for gathering real-time data on face-to-face social interactions with tunable spatial and temporal resolution. We use active Radio Frequency Identification (RFID) devices that assess mutual proximity in a distributed fashion by exchanging low-power radio packets. We show results on the analysis of the dynamical networks of person-to-person interaction obtained in four high- resolution experiments carried out at different orders of magnitude in community size. [Preview Abstract] |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2024 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700