Bulletin of the American Physical Society
APS March Meeting 2017
Volume 62, Number 4
Monday–Friday, March 13–17, 2017; New Orleans, Louisiana
Session H15: Complex Networks and their Applications |
Hide Abstracts |
Sponsoring Units: GSNP Chair: Jason Hindes, Naval Research Lab Room: 274 |
Tuesday, March 14, 2017 2:30PM - 2:42PM |
H15.00001: Efficient Sampling of Ensembles of Large Graphs with Prescribed Degrees Weibin Zhang, Kevin E. Bassler Generating uniform ensembles of random graphs with prescribed structural constraints is essential for many network analyses. Unfortunately, problems with all known methods make it impractical to sample ensembles of large graphs. Recent advances that significantly improve direct construction or sequential importance sampling (SIS) methods will be discussed. SIS produces samples independently but not uniformly. Sampling uniformity can be achieved by reweighting. However, as the construction algorithms involve random multiplicative processes, the individual sample weights are generally log-normally distributed, implying that exponentially many samples are nominally required to calculate ensemble averages. Algorithmic improvements that substantially reduce the variance of the samplesâ€™ log-weights will be presented. Additionally, if the samplesâ€™ log-weight and the value of the quantity being measured can be assumed to have a bivariate normal distribution, then the efficiency of the sampling can be further improved by estimating the parameters of the distributions and using those estimates to estimate ensemble averages. With these improvements, prescribed degree scale-free networks with exponent $\gamma=2$ as large as a $10^6$ nodes can be effectively sampled. [Preview Abstract] |
Tuesday, March 14, 2017 2:42PM - 2:54PM |
H15.00002: Percolation transitions on multiplex lattices following the cascades of activations and deactivations Jeehye Choi, Kwang-Il Goh We introduce the percolation transitions of the multiplex viability model [B. Min and K.-I. Goh, Phys. Rev. E 89, 040802(R) (2014)] on two-layer square lattices. This model is a generalized percolation model on multiplex systems comprised of two distinct processes establishing the viability, the cascade of activations (CA) and the cascade of deactivations (CD), depending upon which different transition points and thereby hysteresis are observed. To address the universality issue of this model, here we perform extensive Monte Carlo simulations and show that in two-layer square lattices the two processes not only have different percolation transition points but also exhibit different critical behaviors with distinct sets of critical exponents. For CA, the transition is found to be in the same universality class as the ordinary percolation in 2D. For CD, the transition belongs to different universality class from OP but shows critical behaviors consistent with those of 2D mutual percolation model.To achieve a self-contained and self-consistent scaling picture of the transitions we introduce a novel definition of the cluster that properly addresses the critical properties. The obtained results are verified for consistency through scaling relations such as $d\nu=2\beta+\gamma$. [Preview Abstract] |
Tuesday, March 14, 2017 2:54PM - 3:06PM |
H15.00003: Failure of interdependent lattice networks in high dimensions Gabriel A Cwilich, Steven Lowinger, Sergey V Buldyrev We study the mutual percolation of two interdependent lattice networks for dimensions ranging from 2 to 7. We impose that the length of interdependency links connecting nodes in the two lattices be less than or equal to a certain value $r$. For each value of $D$ and $r$, we find the mutual percolation threshold, $p_c[D,r]$, below which the system completely collapses through a cascade of failures following an initial destruction of a fraction $ (1-p)$ of the nodes selected at random in one of the lattices. We find that for each dimension $D<6$ there is a value of $r=r_I>1$ such that for $r\geq r_I$ the cascading failures occur as a discontinuous first order transition, while for $r < r_I$ the system undergoes a continuous second order transition, as in the classical percolation theory. In all dimensions, the interdependent lattices reach maximal vulnerability (maximal $p_c[D,r]$) at a distance $r=r_{max}>r_I$, before beginning to decrease as $r\to\infty$. The decrease becomes less significant as $D$ increases and $p_c[D,r_{max}]-p_c[D,\infty]$ decreases exponentially with $D$. [Preview Abstract] |
Tuesday, March 14, 2017 3:06PM - 3:18PM |
H15.00004: Estimating the Severity of Cascading Failures Induced by Multi-Node Attacks in the Power Grid Alaa Moussawi, Noemi Derzsy, Xin Lin, Boleslaw Szymanski, Gyorgy Korniss Maintenance of power grid stability is essential for the success of global infrastructure, making prevention of cascading failures a high priority. Predicting the severity of cascading failures in a time frame enabling response is an essential part of mitigating risks present in the power grid. For a network of size N, there are $2^N$ different failure scenarios that can induce cascades in the network, a rapidly increasing number even for small network sizes. Thus far, methods of predicting network cascade extent based on initial network conditions have shown very meager results. We propose a method of estimating the severity of cascading failures induced by multiple node failures based upon the severities of the failures induced by the same number of single node failures in the network. Results show a strong correlation between the sum of the severity of the cascades induced by f individual nodes, and the severity of a cascade induced by the simultaneous failure of all f nodes. As the number of nodes inducing the multi-node failure increases, this correlation weakens. We approximate the extent of all $2^N$ cascade scenarios by sums of damages of the N single node failures, suggesting methods of estimating the general robustness of a given power grid. [Preview Abstract] |
Tuesday, March 14, 2017 3:18PM - 3:30PM |
H15.00005: Renormalization Group Approaches for Dynamics on Irregular Networks Madhurima Nath, Yihui Ren, Stephen Eubank Moore and Shannon's reliability polynomial can be used as a global statistic to explore the behaviour of a diffusive process on a network that represents a finite sized interacting system. It depends on both the network topology and the dynamics of the process and gives the probability that the system has a particular desired property. The estimation of the reliability polynomials for large graphs is feasible using Monte-Carlo simulation. By analogy with the partition function of a physical system, it is possible to define renormalization group approaches that map the parameters of one network onto another keeping the network reliability invariant. This transformation suggests a canonical form for the network reliability that can be used as a measure for non - random structure for different graphs. Further, this information about the existence of certain structured patterns provides knowledge about the community structures in the network. [Preview Abstract] |
Tuesday, March 14, 2017 3:30PM - 3:42PM |
H15.00006: Structure-based control of complex networks with nonlinear dynamics Jorge G. T. Zanudo, Gang Yang, Reka Albert What can we learn about controlling a system solely from its underlying network structure? Here we use a framework for control of networks governed by a broad class of nonlinear dynamics that includes the major dynamic models of biological, technological, and social processes. This feedback-based framework provides realizable node overrides that steer a system towards any of its natural long term dynamic behaviors, regardless of the dynamic details and system parameters. We use this framework on several real networks, identify the topological characteristics that underlie the predicted node overrides, and compare its predictions to those of classical structural control theory. Finally, we demonstrate this framework's applicability in dynamic models of gene regulatory networks and identify nodes whose override is necessary for control in the general case, but not in specific model instances. [Preview Abstract] |
Tuesday, March 14, 2017 3:42PM - 3:54PM |
H15.00007: Large Fluctuations and Rare-Events in Complex Networks Jason Hindes, Ira Schwartz Networks form the backbone of complex systems ranging from ecological food-webs to computer and social networks, and sustain a variety of important dynamical behaviors necessary for some function or task. However, many networks of interest often operate in noisy environments and fluctuate due to random internal interactions, both of which can cause sudden transitions from one network state to another. These noise induced events can be associated with desirable outcomes, such as the extinction of an epidemic, or undesirable, such as a drastic change in network consensus. In this talk, we discuss a general theory of rare-events occurring in complex networks, including extinction and rare-opinion switches, that captures the transition pathway through a network between states and predicts the characteristic time-scale for switching. Lastly, using the formalism, we demonstrate how to design optimal controls that leverage fluctuations in order to enhance or inhibit rare switches in networks. [Preview Abstract] |
Tuesday, March 14, 2017 3:54PM - 4:06PM |
H15.00008: Observation of the Braess Paradox in Electric Circuits Ladimer Nagurney, Anna Nagurney User-optimized network systems may exhibit counterintuitive phenomena such as the Braess Paradox where, when adding an additional link to the network, the cost increases for every user. While traffic networks are a prime example of networks exhibiting this paradox, it has been observed in telecommunications networks and in physical networks such as mechanical spring, fluid flow, and nanoscale networks. This work demonstrates that the Braess Paradox occurs in macroscopic electric circuits consisting of only passive components: resistors and diodes. We identify the electrical quantities that correspond to the network flows and costs and illustrate the mapping of the cost functions to ideal components. We use the solution of the Kirchoff Law nodal equations to demonstrate that the Braess Paradox will be observed in the electrical network of ideal components. These nodal equations also predict that the Braess Paradox can be observed in networks implemented using real components. We construct several macroscopic electric circuits that represent different cost functions and show that the Braess Paradox occurs when the experimentally measured voltage across the circuit increases as an additional link is added. We conclude by extending this work to cases where the demand is varied. [Preview Abstract] |
Tuesday, March 14, 2017 4:06PM - 4:18PM |
H15.00009: Influence Maximization in Ising Networks Christopher Lynn, Daniel Lee In the analysis of social networks, a fundamental problem is influence maximization: Which individuals should be influenced to maximally impact the collective opinions of an entire population? Traditionally, influence maximization has been studied in the context of contagion models and irreversible processes. However, by including stochastic noise in the opinion formation process, repeated interactions between individuals give rise to complex macroscopic patterns that are observed, for example, in the formation of political opinions. Here we map influence maximization in the presence of stochastic noise onto the Ising model, and the resulting problem has a natural physical interpretation as maximizing the magnetization given a budget of external magnetic field. Using the susceptibility matrix, we provide a gradient ascent algorithm for calculating optimal external fields in real-world social networks. Remarkably, we find that the optimal external field solutions undergo a phase transition from intuitively focusing on high-degree individuals at high temperatures to counterintuitively focusing on low-degree individuals at low temperatures, a feature previously neglected under the viral paradigm. [Preview Abstract] |
Tuesday, March 14, 2017 4:18PM - 4:30PM |
H15.00010: Developing algorithm for the critical care physician scheduling Hyojun Lee, Adam Pah, Luis Amaral |
Tuesday, March 14, 2017 4:30PM - 4:42PM |
H15.00011: Abstract Withdrawn Null models are established tools that have been used in network analysis to uncover various structural patterns. They quantify the deviance of an observed network measure to that given by the null model. We construct a null model for weighted, directed networks to identify biased links (carrying significantly different weights than expected according to the null model) and thus quantify the flatness of the system. Using this model, we study the flatness of Kiva, a large international crownfinancing network of borrowers and lenders, aggregated to the country level. The dataset spans the years from 2006 to 2013. Our longitudinal analysis shows that flatness of the system is reducing over time, meaning the proportion of biased inter-country links is growing. We extend our analysis by testing the robustness of the flatness of the network in perturbations on the links' weights or the nodes themselves. Examples of such perturbations are event shocks (e.g. erecting walls) or regulatory shocks (e.g. Brexit). We find that flatness is unaffected by random shocks, but changes after shocks target links with a large weight or bias. The methods we use to capture the flatness are based on analytics, simulations, and numerical computations using Shannon's maximum entropy. |
Tuesday, March 14, 2017 4:42PM - 4:54PM |
H15.00012: Editorial highlighting and highly cited papers Manolis Antonoyiannakis Editorial highlighting---the process whereby journal editors select, at the time of publication, a small subset of papers that are ostensibly of higher quality, importance or interest---is by now a widespread practice among major scientific journal publishers. Depending on the venue, and the extent to which editorial resources are invested in the process, highlighted papers appear as News {\&} Views, Research Highlights, Perspectives, Editors' Choice, IOP Select, Editors' Summary, Spotlight on Optics, Editors' Picks, Viewpoints, Synopses, Editors' Suggestions, etc. Here, we look at the relation between highlighted papers and highly influential papers, which we define at two levels: having received enough citations to be among the (i) top few percent of their journal, and (ii) top 1{\%} of all physics papers. Using multiple linear regression and multilevel regression modeling we examine the parameters associated with highly influential papers. We briefly comment on cause and effect relationships between citedness and highlighting of papers. [Preview Abstract] |
Tuesday, March 14, 2017 4:54PM - 5:06PM |
H15.00013: Quantifying patterns of research interest evolution Tao Jia, Dashun Wang, Boleslaw Szymanski Changing and shifting research interest is an integral part of a scientific career. Despite extensive investigations of various factors that influence a scientist's choice of research topics, quantitative assessments of mechanisms that give rise to macroscopic patterns characterizing research interest evolution of individual scientists remain limited. Here we perform a large-scale analysis of extensive publication records, finding that research interest change follows a reproducible pattern characterized by an exponential distribution. We identify three fundamental features responsible for the observed exponential distribution, which arise from a subtle interplay between exploitation and exploration in research interest evolution. We develop a random walk based model, which adequately reproduces our empirical observations. Our study presents one of the first quantitative analyses of macroscopic patterns governing research interest change, documenting a high degree of regularity underlying scientific research and individual careers. [Preview Abstract] |
Tuesday, March 14, 2017 5:06PM - 5:18PM |
H15.00014: Active Flows on Trees Aden Forrow, Francis Woodhouse, Joern Dunkel Coherent, large scale dynamics in many nonequilibrium physical, biological, or information transport networks are driven by small-scale local energy input. We introduce and explore a generic model for compressible active flows on tree networks. In contrast to thermally-driven systems, active friction selects discrete states with only a small number of oscillation modes activated at distinct fixed amplitudes. This state selection interacts with graph topology to produce different localized dynamical time scales in separate regions of large networks. Using perturbation theory, we systematically predict the stationary states of noisy networks and find good agreement with a Bayesian state estimation based on a hidden Markov model applied to simulated time series data on binary trees. While the number of stable states per tree scales exponentially with the number of edges, the mean number of activated modes in each state averages $\sim 1/4$ the number of edges. More broadly, these results suggest that the macroscopic response of active networks, from actomyosin force networks in cells to cytoplasmic flows, can be dominated by a significantly reduced number of modes, in stark contrast to energy equipartition in thermal equilibrium systems. [Preview Abstract] |
Tuesday, March 14, 2017 5:18PM - 5:30PM |
H15.00015: Damage Response in Fluid Flow Networks Tatyana Gavrilchenko, Eleni Katifori The networks found in biological fluid flow systems such as leaf venation and animal vasculature are characterized by hierarchically nested loops. This structure allows the system to be resilient against fluctuations in the flow of fluid and to be robust against damage. We analytically and computationally investigate how this loopy hierarchy determines the extent of disruption in fluid flow in the vicinity of a damage site. Perturbing the network with the removal of a single edge results in the differential flow as a function of distance from the perturbation decaying as a power law. The power law exponent is generally around -2 in 2D, but we find that it varies due to edge effects, initial edge conductivity, and local topology. We expect that these network flow findings, directly applicable to plant and animal veins, will have analogues in electrical grids, traffic flow and other transport networks. [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. |
© 2019 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
1 Research Road, Ridge, NY 11961-2701
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700