Bulletin of the American Physical Society
APS March Meeting 2014
Volume 59, Number 1
Monday–Friday, March 3–7, 2014; Denver, Colorado
Session Y16: Complex Networks and their Applications I |
Hide Abstracts |
Sponsoring Units: GSNP Chair: Kevin Bassler Room: 401 |
Friday, March 7, 2014 8:00AM - 8:12AM |
Y16.00001: Targeted Control of Complex Networks Jianxi Gao, Yangyu Liu, Raissa M. D'Souza, Albert-Laszlo Barabasi Network controllability is typically formulated as the ability to drive an entire network from any initial state to any desired final state in finite time, using a minimum number of inputs. However, in many circumstances it is neither feasible nor necessary to control the entire network. This prompts us to explore how to efficiently control a subset of nodes in a network, i.e., ``targeted controllability.'' We develop an alternate ``k-walk'' theory based on the fact that a single node can control a set of nodes provided the path length from the control node to each target node is unique. For the general case, we develop a greedy algorithm, based on k-walk theory, to identify the approximate minimal set of necessary driver nodes. We demonstrate that partial controllability has fundamentally different features when compared to full controllability. For example, we find that degree heterogeneous networks can be partially controllable with higher efficiency than degree homogeneous networks. Moreover we show that the structures of many real-world networks are highly efficient for targeted control. [Preview Abstract] |
Friday, March 7, 2014 8:12AM - 8:24AM |
Y16.00002: Energy Spectrum of Complex Systems Control Georgios Tsekenis, Baruch Barzel, Yang-Yu Liu, Jean-Jacques Slotine, Albert-Laszlo Barabasi Understanding how to control a complex network is a fundamental scientific question with a wealth of potential applications in man-made and natural systems. When controlling a complex system one has to steer it from one point of its state space to another by an appropriate set of inputs. The state space complex systems operate in is high-dimensional with dimensionality equal to the system's size. The energy of control across directions span several decades of orders of magnitude exhibiting an extremely wide range. The control energy spectrum is dominated by a fat-tail that is largely independent of the properties of the network. As a result control is easy in most directions while it is very hard in few of them. Naturally the energy of control decreases by increasing the number of driver nodes. [Preview Abstract] |
Friday, March 7, 2014 8:24AM - 8:36AM |
Y16.00003: Cascading Failures Due to Multiple Causes in Interdependent Networks Yosef Kornbluth, Sergey Buldyrev In recent years, several models of network failure have been introduced. Some of these models are based on overload, in which increased traffic destroys nodes, while others are based on partial isolation, in which a node needs several functional neighbors to survive. In these systems, failure of a small fraction of nodes can cause a cascade of failures which may completely destroy the network. The majority of these models are studied in single networks. However, many real-world systems are comprised of multiple interdependent networks. Recent studies based on the concept of mutual percolation show that these systems are much more vulnerable than a single network. We numerically and analytically investigate how multiple causes of failure simultaneously acting in a system of interdependent networks affect their vulnerability. [Preview Abstract] |
Friday, March 7, 2014 8:36AM - 8:48AM |
Y16.00004: Fractional dynamics of complex networks Malgorzata Turalska, Bruce J. West The relation between the behavior of a single element and the global dynamics of its host network is an open problem in the science of complex networks. Typically one attempts to infer the global dynamics by combining the behavior of single elements within the system, following a bottom-up approach. Here we address an inverse problem. We show that for a generic model within the Ising universality class it is possible to construct a description of the dynamics of an individual element, given the information about the network's global behavior. We demonstrate that the individual trajectory response to the collective motion of the network is described by a linear fractional differential equation, whose analytic solution is the Mittag-Leffler function. This solution is obtained through a subordination procedure without the necessity of linearizing the underlying dynamics, that is, the solution retains the influence of the nonlinear network dynamics on the individual. Moreover the solutions to the fractional equation of motion suggest a new direction for designing control mechanisms for complex networks. The implications of this new perspective are explored by introducing a control signal into a small number of network elements and analyzing the subsequent change in the network dynamics. [Preview Abstract] |
Friday, March 7, 2014 8:48AM - 9:00AM |
Y16.00005: Random Regular Networks with Distance-limited Interdependent Links Steven Lowinger, Yosef Kornbluth, Gabriel Cwilich, Sergey Buldyrev We study the mutual percolation of a system composed of two interdependent random regular networks. We introduce a notion of distance, $d$, to explore the effects of the proximity of interdependent nodes on the cascade of failures after an initial attack. The nature of the transition through which the networks disintegrate depends on the parameters of the system, which are the degree of the nodes and the maximum distance between interdependent nodes. As the distance and degree increase, the collapse at the critical threshold changes from a second-order transition to a first-order one. The critical threshold monotonically increases with distance. We find a transitional case, in which a novel type of phase transition appears. The case $d=$1 can be completely solved analytically and it maps into a discrete version of the R\'{e}nyi parking problem [1]. \\[4pt] [1] A. R\'{e}nyi, Publ. Math. Inst. Hung. Acad. Sci. 3, 109-127(1958). [Preview Abstract] |
Friday, March 7, 2014 9:00AM - 9:12AM |
Y16.00006: n-tangle: A network comparison method Lazaros K. Gallos, Nina H. Fefferman The ability to compare systems has always been a strong driving force in science. Network analysis has allowed researchers across fields to quantify and characterize numerous patterns of interactions among individuals. The comparison of different networks, though, still remains a puzzling problem. Here, we introduce the n-tangle method to directly compare two networks for structural similarity, based on the distribution of edge density in network subgraphs. The crux of this method is to capture how many affiliations we expect to find when we isolate any given size of connected sub-group. We demonstrate that this method can efficiently introduce comparative analysis into network science and opens the road for many new applications. Our approach avoids inherent constraints of other methods and can be applied to networks of different size and structure. Our method can be expanded to study a multitude of additional properties, such as network classification, changes during time evolution, convergence of growth models, and detection of structural changes during damage. [Preview Abstract] |
Friday, March 7, 2014 9:12AM - 9:24AM |
Y16.00007: Symmetry in Critical Random Boolean Networks Dynamics Kevin E. Bassler, Shabnam Hossein Using Boolean networks as prototypical examples, the role of symmetry in the dynamics of heterogeneous complex systems is explored. We show that symmetry of the dynamics, especially in critical states, is a controlling feature that can be used to both greatly simplify analysis and to characterize different types of dynamics. Symmetry in Boolean networks is found by determining the frequency at which the various Boolean output functions occur. Classes of functions occur at the same frequency. These classes are orbits of the controlling symmetry group. We find the nature of the symmetry that controls the dynamics of critical random Boolean networks by determining the frequency of output functions utilized by nodes that remain active on dynamical attractors. This symmetry preserves canalization, a form of network robustness. We compare it to a different symmetry known to control the dynamics of an evolutionary process that allows Boolean networks to organize into a critical state. Our results demonstrate the usefulness and power of using symmetry to characterize complex network dynamics, and introduce a novel approach to the analysis of heterogeneous complex systems. [Preview Abstract] |
Friday, March 7, 2014 9:24AM - 9:36AM |
Y16.00008: Critical Behavior in a Class of Heterogeneous Complex Systems Shabnam Hossein, Florian Greil, Kevin E. Bassler Dynamical critical behavior of a prototypical heterogeneous complex system, random Boolean networks, is studied. Using analytical arguments, we show that the networks, at the boundary between their frozen and chaotic dynamical phases, display universal critical behavior in their attractor period distribution, which has the functional form of a decaying power-law. Using a known result that nodes relevant to the dynamics on attractors at criticality can be divided into separate components, we analyze the structure of these relevant components and how their dynamics combine to find the distribution of attractor periods. This is accomplished by mapping the problem to the enumeration of binary Lyndon words. We show that the attractor period distribution becomes scale-free in the large network limit with a decay described by a critical exponent of 1. Results of numerical simulations that support this finding, but that also show that substantial finite-size corrections exist, will also be presented. The universal nature of this behavior is demonstrated by comparison to that of the evolved critical state achieved through the playing of an adaptive game that selects for diversity of node behavior. [Preview Abstract] |
Friday, March 7, 2014 9:36AM - 9:48AM |
Y16.00009: Eigenvalue Separation in the Laplacian Spectra of Random Geometric Graphs Amy Nyberg, Kevin E. Bassler The graph Laplacian spectra of networks are important for characterizing both their structural and dynamical properties. We investigate the spectra of random geometric graphs (RGGs), which are prototypical examples of networks with strong correlations and describe networks whose nodes have a random physical location and are connected to other nodes that are within a threshold distance. RGGs model transportation grids, wireless networks, and biological processes. The spectrum consists of two parts, a discrete part consisting of a collection of integer valued delta function peaks centered about the average degree and a continuous part that exhibits the phenomenon of eigenvalue separation. We find that the number of eigenvalues in each separated peak depends on the dimension and boundary conditions of the embedding space of the RGG. Partly because of the bounds it places on connectivity, the smallest nonzero eigenvalue, or algebraic connectivity, is of particular interest. We find that in the regime of separation, the algebraic connectivity varies as a power of the average degree. This power depends on the dimension of the embedding space. [Preview Abstract] |
Friday, March 7, 2014 9:48AM - 10:00AM |
Y16.00010: Laplacian Spectra of Random Hyperbolic Geometric Networks Florian Greil, Kevin E. Bassler Random geometric networks embedded in hyperbolic 2D space have been suggested as models of social networks where the spatial metric implements an interplay between popularity and similarity. [F. Papadopulos et. al., Nature {\bf 489}, 589 (2012)] We show that the eigenvalue spectrum of their combinatorial Laplacian matrix can be employed as a useful tool to understand the structural and dynamical properties of these networks. Features of the spectrum, including eigenvalue separation and localization, are associated with specific network properties. These properties are studied as a function of average node connectivity and curvature of the embedding space. For large networks, a transition in the properties of the network is found as the curvature varies. This transition is indicated by the development of power-law spectra at high curvature. [Preview Abstract] |
Friday, March 7, 2014 10:00AM - 10:12AM |
Y16.00011: Extracting connectivity of networks from dynamics of nodes Emily S.C. Ching, P.-Y. Lai, C.Y. Leung The knowledge of how the different nodes of a network interact or connect with one another is crucial for the understanding of the collective behavior and the functionality of a network. We have recently developed a method that extracts network connectivity using only measurements of the dynamics of the nodes for bidirectional networks with uniform coupling strength. Our method is built upon a noise-induced relation between the Laplacian matrix $L_{ij}$ of the network and the pseudoinverse of the dynamical covariance matrix $C_{ij}^+$: $L_{ij}=\sigma^2/(2g)C_{ij}^+ $, where $\sigma$ is the noise amplitude and $g$ the coupling strength. This relation is exact for consensus dynamics. The extraction of connectivity is based on the separation of $r_{ij}\equiv C_{ij}^+/C_{ii}^+$, for each node $i$, into two groups depending on whether node $j$ is connected to node $i$ or not. Such a separation is guaranteed by the above relation, and has been found to exist even in networks with nonlinear dynamics. Using examples of different networks and dynamics, we have demonstrated that our method can give accurate local connectivity information as well as global network properties of the degree distribution and eigenvalue spectrum of the adjacency matrix for a wide range of $\sigma$ and $g$. [Preview Abstract] |
Friday, March 7, 2014 10:12AM - 10:24AM |
Y16.00012: Distributions of Betweenness in Cascades of Overload Failure in Random Regular Networks Gilad Barach, Mark Tuchman, Gabriel Cwilich, Sergey Buldyrev We study the Motter and Lai [1] model of cascading failures of a network by overload based on the betweenness centrality of the nodes, for the case of a random regular network. ~We study numerically by several means~the disintegration of the network as a function of the fraction~$p$~of the nodes that survive an initial random attack: the size of the final giant component, the number of cascade stages, and the distribution of the betweenness of the nodes for different stages of the cascade. ~We find that the nature of the transition through which the network disintegrates changes from first order to second order as the tolerance increases. After this large drop, in which a substantial part of the network disintegrates, we find that the size of the final~giant component does not decrease monotonically when increasing~the size of the initial attack~\textit{(1-p)}, but rather presents a series of maxima and minima as a function of~$p$. [1] Cascade-based attacks on complex networks, Phys. Rev. \textbf{E 66}, 065102(R) (2002) [Preview Abstract] |
Friday, March 7, 2014 10:24AM - 10:36AM |
Y16.00013: Controlling Contagion Processes in Time-Varying Networks Nicola Perra, Suyu Liu, Marton Karsai, Alessandro Vespignani The vast majority of strategies aimed at controlling contagion processes on networks considers the connectivity pattern of the system as either quenched or annealed. However, in the real world many networks are highly dynamical and evolve in time concurrently to the contagion process. Here, we derive an analytical framework for the study of control strategies specifically devised for time-varying networks. We consider the removal/immunization of individual nodes according the their activity in the network and develop a block variable mean-field approach that allows the derivation of the equations describing the evolution of the contagion process concurrently to the network dynamic. We derive the critical immunization threshold and assess the effectiveness of the control strategies. Finally, we validate the theoretical picture by simulating numerically the information spreading process and control strategies in both synthetic networks and a large-scale, real-world mobile telephone call dataset. [Preview Abstract] |
Friday, March 7, 2014 10:36AM - 10:48AM |
Y16.00014: Cascades in the Threshold Model with Multiple Initiators and Heterogeneous Threshold Values P. Karampourniotis, S. Sreenivasan, B.K. Szymanski, G. Korniss The threshold model (TM) is a classical opinion diffusion model, under which a node adopts an opinion only when its threshold is lower than the fraction of its neighbors already possessing that opinion. The TM has been thoroughly investigated for uniform thresholds with small sizes ($< 0.01)$ of initially active nodes (initiators) (Watts, 2002) and with multiple initiators (Singh, 2013). However, a model with uniform threshold does not capture the complex nature of social influencing when multiple initiators are present. We find that for sufficiently large spread in the threshold distribution, the tipping point in the social influencing process disappears and crosses over to a smooth transition governed by the size of initiators. Specifically, we study cascades in the TM when nodes are assigned a threshold value drawn from the Normal Distribution with varying mean threshold $\varphi $ and standard deviation $\sigma $. We analyze both synthetic and empirical networks using different sizes of initiators. We observe a non-monotonic change in the cascade size for varying $\sigma $ that for small initiator sizes follows Watts Cascade Condition. In addition, we find that, unlike the case of uniform thresholds, for large enough $\sigma $, a critical initiator size beyond which cascades become global ceases to exist. [Preview Abstract] |
Friday, March 7, 2014 10:48AM - 11:00AM |
Y16.00015: Stability of Dominating Sets in Complex Networks against Random and Targeted Attacks F. Molnar, N. Derzsy, B.K. Szymanski, G. Korniss Minimum dominating sets (MDS) are involved in efficiently controlling and monitoring many social and technological networks. However, MDS influence over the entire network may be significantly reduced when some MDS nodes are disabled due to random breakdowns or targeted attacks against nodes in the network. We investigate the stability of domination in scale-free networks in such scenarios. We define stability as the fraction of nodes in the network that are still dominated after some nodes have been removed, either randomly, or by targeting the highest-degree nodes. We find that although the MDS is the most cost-efficient solution (requiring the least number of nodes) for reaching every node in an undamaged network, it is also very sensitive to damage. Further, we investigate alternative methods for finding dominating sets that are less efficient (more costly) than MDS but provide better stability. Finally we construct an algorithm based on greedy node selection that allows us to precisely control the balance between domination stability and cost, to achieve any desired stability at minimum cost, or the best possible stability at any given cost. Analysis of our method shows moderate improvement of domination cost efficiency against random breakdowns, but substantial improvements against targeted attacks. [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