Arsiwalla, Xerxes | Analytic Solutions for Network Information Complexity | Abstract |
Belik, Vitaly | Recurrent epidemics on adaptive temporal networks | Abstract |
Conrad, Natasa | Cycle-based module detection in directed networks | Abstract |
Georgiou, Orestis | Maximum likelihood based multihop localization in wireless sensor networks | Abstract |
Giles, Alexander | Betweenness centrality in random geometric graphs at finite density | Abstract |
Jalan, Sarika | Synchronizability in multiplex networks | |
Klimm, Florian | Roles of nodes inside the multilayer structure | |
Sayama, Hiroki | Graph product multilayer networks | Abstract |
Taylor, Dane | Complex contagions for topological data analysis of networks | Abstract |
Analytic Solutions
for Network Information Complexity Arsiwalla, Xerxes (Universitat Pompeu Fabra, Barcelona, Spain) |
How much information does a dynamical network generate as a whole over the sum of its parts during a state transition? In this work, we seek to analytically quantify the information complexity of stochastic dynamical networks in terms of the network's dynamical and coupling parameters. Recently, measures of network complexity such as integrated information have been proposed. However, these approaches face several technical limitations and also cannot be implemented for large-scale networks. We develop a formulation starting from the Kullback-Leibler divergence and demonstrate explicit analytic computations of information complexity for several prototypical network topologies with stochastic dynamics and plastic connection weights. For stationary Gaussian dynamics our computations reveal that the network's dynamical complexity sharply rises at the edge of criticality. Our formulation can also be numerically extended for large complex networks. We comment on potential applications of these results, in particular, for stochastic biological networks. |
↑ Go to the top ↑ |
Recurrent epidemics on adaptive temporal networks Belik, Vitaly (TU Berlin, Institut für Theoretische Physik, Berlin, Germany) |
Recently a lot of attention is drawn to networks with internal time-varying topology. For these networks the precise time sequences of edge occurrences is important to describe dynamical processes on relevant time scales. We consider a recurrent contagious process on a temporal network. As a containment measure we propose an adaptive rewiring mechanism: after detection of the disease, infected nodes are temporary isolated via edge rewiring. In contrast to adaptive coevolutionary networks, where the initially static topology is changed due to feedback from the epidemic process, the temporal network possesses its own dynamics. As a real world application we use an animal trade network in Germany. One of the main results reveals heterogeneous performance of adaptation in respect to different starting locations of epidemics: some starting nodes lead to easily controllable epidemics and some not. We performed extensive sensitivity analysis to quantify the effect of adaptation for various parameter values. Our findings are important for designing containment strategies of infectious diseases. |
↑ Go to the top ↑ |
Cycle-based Module
Detection in Directed Networks Conrad, Natasa (Zuse Institute Berlin, Berlin, Germany) |
Finding network modules (or communities, clusters) is a challenging task, especially when modules do not form a full decomposition of the whole network [3]. In recent years many approaches for finding fuzzy network partitions have been developed, but most of them focus only on undirected networks [2]. Approaches for finding modules in directed networks are usually based on network symmetrization that does not take into account edge directions and thus ignore very important information. We will present a novel random-walk based approach for finding fuzzy partitions of directed, weighted networks into modules, where edge directions play a crucial role in defining how well nodes in a module are inter-connected [1]. More precisely, we will say that two nodes are well connected if the random-walk process can go fast through very few edges on the way from one node to the other one in both directions, i.e. if these nodes belong to a very short, often visited cycle. Using a cycle network decomposition we will introduce a new, symmetric measure of communication that we will use to define jump rates of our novel random-walk process on a given network. Despite the fact that the new random-walk process is time-reversible (defined on an undirected network), we will show that it inherits all necessary information about directions and structure of the original network. Additionally, we will show that spectral properties of our new process are related to the ones of the random-walk process defined on the adjoint cyclic network, which can be seen as a generalization of [4] used for finding fuzzy partitions in undirected networks. [1] R. Banisch and N. Djurdjevac Conrad, Cycle flow based module detection in directed recurrence networks, Europhysics Letters, Vol. 108, Num. 6, 2014. [2] N. Djurdjevac, S. Bruckner, T.O.F. Conrad and Ch. Schütte, Random walks on complex modular networks, Journal of Numerical Analysis, Industrial and Applied Mathematics, 6 (1-2): pp. 29-50, 2012. [3] M. Sarich, N. Djurdjevac, S. Bruckner, T. O. F. Conrad and Ch. Schütte, Use multilevel random walks to find modules and hubs in complex networks, Journal of Computational Dynamics, 1(1) pp. 191212, 2014. [4] T. S. Evans and R. Lambiotte, Line graphs, link partitions, and overlapping communities, Physical Review E, Vol. 80, 2009. |
↑ Go to the top ↑ |
Maximum likelihood based
multihop localization in wireless sensor networks Georgiou, Orestis (Bristol, United Kingdom) |
For data sets retrieved from wireless sensors to be insightful, it is often of paramount importance that the data be accurate and also location stamped. We describe a maximum-likelihood based multihop localization algorithm called kHopLoc for use in wireless sensor networks that is strong in both isotropic and anisotropic network deployment regions. During an initial training phase, a Monte Carlo simulation is utilized to produce multihop connection density functions. Then, sensor node locations are estimated by maximizing local likelihood functions of the hop counts to anchor nodes. |
↑ Go to the top ↑ |
Betweenness centrality in random geometric graphs at finite
density Giles, Alexander (University of Bristol, UK, Mathematics, Bristol, United Kingdom) |
We present analytic formulas for the betweenness centrality distribution of nodes within dense, random geometric graphs formed within the unit hypercube formed under the traditional unit disk connection model. In these graphs, N nodes are randomly distributed within the hypercube to form a point pattern of potentiallly linked pairs whose connection is determined by manifesting mutual displacement less that r ε R + . By considering a converging sum of integrals over the area of intersecting balls whose centers are separated in the Euclidean metric space by r ij ε R, we enumerate the total number of geodesic paths that connect nodes displaced by r ij , and then evaluate the distribution of probabilities P that a node placed at position r will have betweenness centrality g(r). We then compute the moments of the distribution, and discuss the implications of these formulas for the design of ad-hoc wireless networks. |
↑ Go to the top ↑ |
Graph Product
Multilayer Networks Sayama, Hiroki (Binghamton University, New York State, USA) |
We study graph product multilayer networks (GPMNs), an interesting family of multilayer networks that can be obtained as a graph product of two factor networks. Three product operators are considered: Cartesian, direct (tensor), and strong products. GPMNs have identical intra-layer networks, and are multiplex networks if Cartesian product is used (but not otherwise). They can be considered a (limited) generalization of "aspects" in multilayer networks, and can offer a approach that is complementary to recently proposed graph quotients. We have elucidated analytical/numerical relationships between GPMNs and their factor networks regarding their adjacency and Laplacian spectra, the latter of which hasn't been known in the literature (to the best of our knowledge). We also discuss asymptotic spectral properties of self-similar GPMNs, i.e., higher-order powers of a network, with the order increased to infinity. |
↑ Go to the top ↑ |
Complex contagions for topological data analysis
of networks Taylor, Dane (University of North Carolina at Chapel Hill, Mathematics, Chapel Hill, USA) |
Social and biological contagions are often strongly influenced by the spatial embeddedness of networks. In some cases, such as in the Black Death, they can spread as a wave through space. In many modern contagions, however, long-range edges e.g., due to airline transportation or communication media allow clusters of a contagion to arise in distant locations. We study these competing phenomena for the Watts threshold model (WTM) of complex contagions on empirical and synthetic noisy geometric networks, which are networks that are embedded in a manifold and which consist of both short-range and long-range, ÒnoisyÓ edges. Our approach involves using the WTM to construct contagion maps that use multiple contagions to map the nodes as a point cloud, which we analyze using tools from high-dimensional data analysis and computational homology. For contagions that predominantly exhibit wavefront propagation, we identify a noisy geometric networkÕs underlying manifold in the point cloud, highlighting our approach as a tool for inferring low-dimensional structure. Our approach makes it possible to obtain insights to aid in the modeling, forecast, and control of spreading processes, and it simultaneously leads to a novel technique for manifold learning in noisy geometric networks. |
↑ Go to the top ↑ |