Bulletin of the American Physical Society
APS March Meeting 2018
Volume 63, Number 1
Monday–Friday, March 5–9, 2018; Los Angeles, California
Session S47: Networks |
Hide Abstracts |
Sponsoring Units: GSNP Chair: Reka Albert, Penn State Room: LACC 507 |
Thursday, March 8, 2018 11:15AM - 11:27AM |
S47.00001: Scaling of Local Network Density and the Familiarity Model Lazaros Gallos, Nina Fefferman, Shlomo Havlin Network inhomogeneity usually results in varying densities, depending on the scale of observation, but the scaling of link density has been shown to universally scale inversely with the number of nodes. If, however, we redefine the density as a metric that scales from 0 for a tree structure to 1 for a complete subgraph, the scaling can better distinguish between structures. Here we study how the subgraph network density scales as we vary the scale of observation. Two extreme cases are found: organized structures and random structures such as in Erdos-Renyi networks. We show that real networks usually fall within this range, and can be characterized by the value of a scaling exponent. The results indicate that some real networks, such as the Gnutella sharing network, show signs of random mixture of connections between nodes, while others, such as the Amazon co-purchase network, behave similar to a lattice in terms of density scaling with sample size. To understand the scaling of densities, we introduce the familiarity model which can generate networks with tunable density scaling and it can interpret the results obtained in real networks. |
Thursday, March 8, 2018 11:27AM - 11:39AM |
S47.00002: Mean-field Analysis of Network Reliability with respect to Connectivity against Stochastic Node Removals Satoshi Takabe, Takafumi Nakano, Tadashi Wadayama Connectivity of networks is one of the simplest properties of graphs and has been studied in random graph theory. In theoretical computer science, connectivity is regarded as reliability of wireless communication networks. Recently, Nozaki et. al studied connectivity of random graphs against stochastic node errors as a model of reliability of wireless sensor networks with unreliable relay nodes [1]. In the model, each node is removed independently with a constant probability. The average probability over random graphs that the resultant graphs are disconnected is named a network breakdown probability. In this presentation, we demonstrate a mean-field analysis of the network breakdown probability for random graphs with unbounded average degrees. The approximation formula is applicable to random graph ensembles with any degree distribution and well approximate numerical results. In addition, the asymptotic analysis of the approximation formula reveals that the phase transition of connectivity occurs at an average degree threshold which lies in the logarithmic regime of number of nodes. |
Thursday, March 8, 2018 11:39AM - 11:51AM |
S47.00003: Network community detection using modularity density measures Pramesh Singh, Tianlong Chen, Kevin Bassler Modularity, since its introduction, has remained one of the most widely used metrics to assess the quality of community structure in a complex network. However the resolution limit problem associated with modularity limits its applicability to networks with community sizes smaller than a certain scale. In the past various attempts have been made to solve this problem. More recently a new metric, modularity density, was introduced for the quality of community structure in networks in order to solve some of the known problems with modularity, particularly the resolution limit problem. Modularity density resolves some communities which are otherwise undetectable using modularity. However, we find that it does not solve the resolution limit problem completely by investigating some cases where it fails to detect expected community structures. To address this problem, we introduce a variant of this metric and show that it further reduces the resolution limit problem, effectively eliminating the problem in a wide range of networks. |
Thursday, March 8, 2018 11:51AM - 12:03PM |
S47.00004: Centrality measures identifying dominant promoters and inhibitors in signed networks Greg Morrison Identifying the global regulatory importance of nodes in a regulatory network is important in many biological and competitive social networks, but the majority of measures of social networks are not easily adaptable to signed networks. In this talk, I use the concept of `social balance' to identify important regulators in signed networks, which can be understood as `the inhibitor of my inhibitor is my promotor' in signed networks. This approach is used to define two related measures of centrality incorporating the topology and signs of the links in a manner similar to Katz and betweenness centrality. To illustrate the utility of this approach in identifying important nodes in a signed network, I generate an ensemble of hierarchical majority-rule networks divided into top regulators, middle men (both both regulators and regulated), and workhorses (only regulated). I show that signed Katz centrality is able to identify the net effect of node removal, where nodes with large positive centrality are overall downstream promoters, nodes with very negative centrality are overall downstream inhibitors, and nodes with near-zero centrality have mixed effects. This measure of network centrality provides a new method for understanding complex signed networks in a variety of contexts. |
Thursday, March 8, 2018 12:03PM - 12:15PM |
S47.00005: Algorithmic Design for Neuromorphic Hardware Using Spiking Spin-Glass Models Kathleen Hamilton, Neena Imam, Travis Humble Neural processors compute using discrete time signals, and algorithms for these machines must efficiently incorporate spiking data. We draw upon the dynamics of Hopfield networks to design a spiking neuron Potts-model for use in community detection and label propagation algorithms. Our approach to neural network design avoids the need for large training data sets to determine the hyper-parameters associated with our model, opting instead for heuristic weight-setting rules and analytical parameter setting based on the nonlinear dynamics of coupled systems of leaky-integrate and fire neurons. We have tested our approach on graphs with 128 vertices. For graphs with known ground truths, we can identify community labels sets with accuracy near 100%. |
Thursday, March 8, 2018 12:15PM - 12:27PM |
S47.00006: Network Analysis on Interpreting Atypical
Language Reorganization Case Caused by
Brain Tumor Growth Qiongge Li, Gino Del Ferraro, Kyung Peck, Andrei Holodny, Hernan Makse Neuroplasticity has been observed in many clinical cases such as |
Thursday, March 8, 2018 12:27PM - 12:39PM |
S47.00007: Dynamics and synchronization patterns in oscillator networks with heterogeneous inputs Elizabeth Davison, Zahra Aminzare, Biswadip Dey, Naomi Leonard In networks of nonlinear oscillators, complex dynamics emerge as a function of the interplay between network structure and distributions of external input. We study the dynamics and synchronization patterns that emerge in networks of coupled neuronal oscillators described by the FitzHugh-Nagumo (FN) model, a two-dimensional reduction of the higher-dimensional Hodgkin-Huxley model for neuronal membrane potential dynamics. In the uncoupled setting, the FN model exhibits three qualitatively distinct input-dependent regimes in its dynamical behavior: quiescence, firing, and saturation. When multiple FN oscillators are connected through diffusive coupling, the resulting dynamics exhibit complex behaviors, which include mixed-mode oscillations and asymptotically periodic dynamics. Using techniques from bifurcation theory and singular perturbation theory and leveraging multiple time scales in the dynamics, we identify the possible behavioral regimes of the oscillators in the network and characterize the ones where the system exhibits complex behavior. We further explore how transitions between regimes depend on heterogeneous external inputs, coupling strength, and time-scale separation parameters. Our work furthers the understanding of the dynamics of coupled oscillatory systems. |
Thursday, March 8, 2018 12:39PM - 12:51PM |
S47.00008: State- and Distance-Dependent Adaptive Rewiring in Spatial Networks Evangelia Papadopoulos, Danielle Bassett Many systems can be modeled as a collection of dynamical units coupled via a network. In adaptive systems, network connectivity and dynamics are interdependent. For example, in neuroanatomical systems, the coupling between neural units influences their dynamical patterns, which can in turn reshape network structure via processes such as activity-dependent rewiring. However, another important aspect of many real-world networks is that they are embedded into space and may be subject to tradeoffs between material costs and efficiency. To take into account this feature, here we consider adaptive, but spatially-embedded networks of Kuramoto oscillators. Beginning with a random topology, we simulate a coevolution process that depends on both the dynamical states of coupled units, as well as spatial distances between them. In particular, edges tend to break between less dynamically coherent units, and are reformed based on proximity, such that short distance connections are favored. We examine the resulting dynamics of the system and the structural properties of the evolving network. We find that the interplay between dynamics, connectivity, and spatial constraints can generate interesting organizational features, such as spatially-localized modules. |
Thursday, March 8, 2018 12:51PM - 1:03PM |
S47.00009: Tunability in Topologically Complex Flow Networks. Miguel Ruiz Garcia, Henrik Ronellenfitsch, Jason Rocks, Andrea Liu, Eleni Katifori Animal vasculature and power grids are examples of natural and man-made flow networks whose optimal operation requires them to be adaptable, i.e. to tune their response according to dynamical changes in demand. Inspired by such systems, in this talk we explore the ability of complex flow networks to be tuned so that, given some specified boundary conditions, the pressure drops along a number of selected edges have predetermined values. In particular, we examine how the topology of the underlying network (e.g. from regular to small world to Erdos-Renyi) affects the ability of the network to be tuned. |
Thursday, March 8, 2018 1:03PM - 1:15PM |
S47.00010: Measuring and Modeling the Flow of Information Online and on Networks James Bagrow, Lewis Mitchell We propose a model for the flow of information in the form of symbolic data. Nodes in a graph representing, e.g., a social network take turns generating words, leading to a symbolic time series associated with each node. Information propagates over the graph via a quoting mechanism, where nodes randomly copy short symbolic sequences from each other. We characterize information flows from these data via information-theoretic estimators, and we derive analytic relationships between model parameters and the values of these estimators. We explore and validate the model with simulations on small network motifs and larger random graphs. Tractable models such as ours that generate symbolic data while controlling the information flow allow us to test and compare measures of information flow applicable to realistic data. In particular, by choosing different network structures, we can develop test scenarios to determine whether or not measures of information flow can distinguish between true and spurious interactions, and how topological network properties relate to information flow. |
Thursday, March 8, 2018 1:15PM - 1:27PM |
S47.00011: Finding the Logic Backbone of a Boolean Network. Parul Maheshwari, Réka Albert Cellular behaviors, governed by various interaction networks among biomolecules, are often modeled using Boolean networks, where the future state of a node is determined by a logic function of the current states of its regulator nodes. Dynamic simulations of the system's trajectory in state space and methods that link the structure and the dynamics of the network have proven insightful. For example, stable motifs by Zanudo et. al. determine the steady states of the system. Here we propose a complementary method, namely the identification and representation of the backbone logical structure of a network, based on categorizing edges as sufficient or necessary. A sufficient activating (inhibitory) relationship means that the ON state of the regulator implies the ON (OFF) state of the target. A necessary activating (inhibitory) relationship means that the OFF state of the regulator implies the OFF (ON) state of the target. We identify (complex) subnetworks distillable into a causal relationship. This way, we represent a signal transduction network as a backbone network of external signals, stable motifs, and the output nodes. Furthermore, we use this framework to identify crucial nodes that can drive the system from one steady state to another. |
Thursday, March 8, 2018 1:27PM - 1:39PM |
S47.00012: Higher Order Structure Distorts Local Information in Networks Xin-Zeng Wu, Allon Percus, Kristina Lerman Local information available to individual nodes in a network may significantly differ from the global information. Such local information bias can significantly affect collective phenomena in networks, including the outcomes of contagious processes and opinion dynamics. To quantify local information bias, we investigate the strong friendship paradox in networks, which occurs when a majority of a node's neighbors have more neighbors than it does itself. Our analysis identified certain properties that determine the strength of the paradox in a network: attribute-degree correlation, network degree-degree correlation and neighbor-neighbor degree correlation, which are degree correlations one step beyond those of neighboring nodes. We develop models that can accurately infer the strength of the paradoxes in synthetic and real-world networks from the network structural features. In addition, we also discovered that the neighbor-neighbor degree correlation is significant in real world networks. Understanding how the paradox biases local observations can inform better measurements of network structure and our understanding of collective phenomena. |
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. |
© 2021 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