Measuring importance in complex networks
NASA Astrophysics Data System (ADS)
Morrison, Greg; Dudte, Levi; Mahadevan, L.
2013-03-01
A variety of centrality measures can be defined on a network to determine the global `importance' of a node i. However, the inhomogeneity of complex networks implies that not all nodes j will consider i equally important. In this talk, we use a linearized form of the Generalized Erdos numbers [Morrison and Mahadevan EPL 93 40002 (2011)] to define a pairwise measure of the importance of a node i from the perspective of node j which incorporates the global network topology. This localized importance can be used to define a global measure of centrality that is consistent with other well-known centrality measures. We illustrate the use of the localized importance in both artificial and real-world networks with a complex global topology.
Hierarchy Measure for Complex Networks
Mones, Enys; Vicsek, Lilla; Vicsek, Tamás
2012-01-01
Nature, technology and society are full of complexity arising from the intricate web of the interactions among the units of the related systems (e.g., proteins, computers, people). Consequently, one of the most successful recent approaches to capturing the fundamental features of the structure and dynamics of complex systems has been the investigation of the networks associated with the above units (nodes) together with their relations (edges). Most complex systems have an inherently hierarchical organization and, correspondingly, the networks behind them also exhibit hierarchical features. Indeed, several papers have been devoted to describing this essential aspect of networks, however, without resulting in a widely accepted, converging concept concerning the quantitative characterization of the level of their hierarchy. Here we develop an approach and propose a quantity (measure) which is simple enough to be widely applicable, reveals a number of universal features of the organization of real-world networks and, as we demonstrate, is capable of capturing the essential features of the structure and the degree of hierarchy in a complex network. The measure we introduce is based on a generalization of the m-reach centrality, which we first extend to directed/partially directed graphs. Then, we define the global reaching centrality (GRC), which is the difference between the maximum and the average value of the generalized reach centralities over the network. We investigate the behavior of the GRC considering both a synthetic model with an adjustable level of hierarchy and real networks. Results for real networks show that our hierarchy measure is related to the controllability of the given system. We also propose a visualization procedure for large complex networks that can be used to obtain an overall qualitative picture about the nature of their hierarchical structure. PMID:22470477
Measuring distances between complex networks
NASA Astrophysics Data System (ADS)
Andrade, Roberto F. S.; Miranda, José G. V.; Pinho, Suani T. R.; Lobão, Thierry Petit
2008-08-01
A previously introduced concept of higher order neighborhoods in complex networks, [R.F.S. Andrade, J.G.V. Miranda, T.P. Lobão, Phys. Rev. E 73 (2006) 046101] is used to define a distance between networks with the same number of nodes. With such measure, expressed in terms of the matrix elements of the neighborhood matrices of each network, it is possible to compare, in a quantitative way, how far apart in the space of neighborhood matrices two networks are. The distance between these matrices depends on both the network topologies and the adopted node numberings. While the numbering of one network is fixed, a Monte Carlo algorithm is used to find the best numbering of the other network, in the sense that it minimizes the distance between the matrices. The minimal value found for the distance reflects differences in the neighborhood structures of the two networks that arise only from distinct topologies. This procedure ends up by providing a projection of the first network on the pattern of the second one. Examples are worked out allowing for a quantitative comparison for distances among distinct networks, as well as among distinct realizations of random networks.
Measure of robustness for complex networks
NASA Astrophysics Data System (ADS)
Youssef, Mina Nabil
Critical infrastructures are repeatedly attacked by external triggers causing tremendous amount of damages. Any infrastructure can be studied using the powerful theory of complex networks. A complex network is composed of extremely large number of different elements that exchange commodities providing significant services. The main functions of complex networks can be damaged by different types of attacks and failures that degrade the network performance. These attacks and failures are considered as disturbing dynamics, such as the spread of viruses in computer networks, the spread of epidemics in social networks, and the cascading failures in power grids. Depending on the network structure and the attack strength, every network differently suffers damages and performance degradation. Hence, quantifying the robustness of complex networks becomes an essential task. In this dissertation, new metrics are introduced to measure the robustness of technological and social networks with respect to the spread of epidemics, and the robustness of power grids with respect to cascading failures. First, we introduce a new metric called the Viral Conductance (VCSIS ) to assess the robustness of networks with respect to the spread of epidemics that are modeled through the susceptible/infected/susceptible (SIS) epidemic approach. In contrast to assessing the robustness of networks based on a classical metric, the epidemic threshold, the new metric integrates the fraction of infected nodes at steady state for all possible effective infection strengths. Through examples, VCSIS provides more insights about the robustness of networks than the epidemic threshold. In addition, both the paradoxical robustness of Barabasi-Albert preferential attachment networks and the effect of the topology on the steady state infection are studied, to show the importance of quantifying the robustness of networks. Second, a new metric VCSIR is introduced to assess the robustness of networks with respect
Measuring multiple evolution mechanisms of complex networks
Zhang, Qian-Ming; Xu, Xiao-Ke; Zhu, Yu-Xiao; Zhou, Tao
2015-01-01
Numerous concise models such as preferential attachment have been put forward to reveal the evolution mechanisms of real-world networks, which show that real-world networks are usually jointly driven by a hybrid mechanism of multiplex features instead of a single pure mechanism. To get an accurate simulation for real networks, some researchers proposed a few hybrid models by mixing multiple evolution mechanisms. Nevertheless, how a hybrid mechanism of multiplex features jointly influence the network evolution is not very clear. In this study, we introduce two methods (link prediction and likelihood analysis) to measure multiple evolution mechanisms of complex networks. Through tremendous experiments on artificial networks, which can be controlled to follow multiple mechanisms with different weights, we find the method based on likelihood analysis performs much better and gives very accurate estimations. At last, we apply this method to some real-world networks which are from different domains (including technology networks and social networks) and different countries (e.g., USA and China), to see how popularity and clustering co-evolve. We find most of them are affected by both popularity and clustering, but with quite different weights. PMID:26065382
Riemannian-geometric entropy for measuring network complexity
NASA Astrophysics Data System (ADS)
Franzosi, Roberto; Felice, Domenico; Mancini, Stefano; Pettini, Marco
2016-06-01
A central issue in the science of complex systems is the quantitative characterization of complexity. In the present work we address this issue by resorting to information geometry. Actually we propose a constructive way to associate with a—in principle, any—network a differentiable object (a Riemannian manifold) whose volume is used to define the entropy. The effectiveness of the latter in measuring network complexity is successfully proved through its capability of detecting a classical phase transition occurring in both random graphs and scale-free networks, as well as of characterizing small exponential random graphs, configuration models, and real networks.
Analyzing complex networks through correlations in centrality measurements
NASA Astrophysics Data System (ADS)
Furlan Ronqui, José Ricardo; Travieso, Gonzalo
2015-05-01
Many real world systems can be expressed as complex networks of interconnected nodes. It is frequently important to be able to quantify the relative importance of the various nodes in the network, a task accomplished by defining some centrality measures, with different centrality definitions stressing different aspects of the network. It is interesting to know to what extent these different centrality definitions are related for different networks. In this work, we study the correlation between pairs of a set of centrality measures for different real world networks and two network models. We show that the centralities are in general correlated, but with stronger correlations for network models than for real networks. We also show that the strength of the correlation of each pair of centralities varies from network to network. Taking this fact into account, we propose the use of a centrality correlation profile, consisting of the values of the correlation coefficients between all pairs of centralities of interest, as a way to characterize networks. Using the yeast protein interaction network as an example we show also that the centrality correlation profile can be used to assess the adequacy of a network model as a representation of a given real network.
Range-limited centrality measures in complex networks
NASA Astrophysics Data System (ADS)
Ercsey-Ravasz, Mária; Lichtenwalter, Ryan N.; Chawla, Nitesh V.; Toroczkai, Zoltán
2012-06-01
Here we present a range-limited approach to centrality measures in both nonweighted and weighted directed complex networks. We introduce an efficient method that generates for every node and every edge its betweenness centrality based on shortest paths of lengths not longer than ℓ=1,...,L in the case of nonweighted networks, and for weighted networks the corresponding quantities based on minimum weight paths with path weights not larger than wℓ=ℓΔ, ℓ=1,2...,L=R/Δ. These measures provide a systematic description on the positioning importance of a node (edge) with respect to its network neighborhoods one step out, two steps out, etc., up to and including the whole network. They are more informative than traditional centrality measures, as network transport typically happens on all length scales, from transport to nearest neighbors to the farthest reaches of the network. We show that range-limited centralities obey universal scaling laws for large nonweighted networks. As the computation of traditional centrality measures is costly, this scaling behavior can be exploited to efficiently estimate centralities of nodes and edges for all ranges, including the traditional ones. The scaling behavior can also be exploited to show that the ranking top list of nodes (edges) based on their range-limited centralities quickly freezes as a function of the range, and hence the diameter-range top list can be efficiently predicted. We also show how to estimate the typical largest node-to-node distance for a network of N nodes, exploiting the afore-mentioned scaling behavior. These observations were made on model networks and on a large social network inferred from cell-phone trace logs (˜5.5×106 nodes and ˜2.7×107 edges). Finally, we apply these concepts to efficiently detect the vulnerability backbone of a network (defined as the smallest percolating cluster of the highest betweenness nodes and edges) and illustrate the importance of weight-based centrality measures in
Range-limited centrality measures in complex networks.
Ercsey-Ravasz, Mária; Lichtenwalter, Ryan N; Chawla, Nitesh V; Toroczkai, Zoltán
2012-06-01
Here we present a range-limited approach to centrality measures in both nonweighted and weighted directed complex networks. We introduce an efficient method that generates for every node and every edge its betweenness centrality based on shortest paths of lengths not longer than ℓ=1,...,L in the case of nonweighted networks, and for weighted networks the corresponding quantities based on minimum weight paths with path weights not larger than w(ℓ)=ℓΔ, ℓ=1,2...,L=R/Δ. These measures provide a systematic description on the positioning importance of a node (edge) with respect to its network neighborhoods one step out, two steps out, etc., up to and including the whole network. They are more informative than traditional centrality measures, as network transport typically happens on all length scales, from transport to nearest neighbors to the farthest reaches of the network. We show that range-limited centralities obey universal scaling laws for large nonweighted networks. As the computation of traditional centrality measures is costly, this scaling behavior can be exploited to efficiently estimate centralities of nodes and edges for all ranges, including the traditional ones. The scaling behavior can also be exploited to show that the ranking top list of nodes (edges) based on their range-limited centralities quickly freezes as a function of the range, and hence the diameter-range top list can be efficiently predicted. We also show how to estimate the typical largest node-to-node distance for a network of N nodes, exploiting the afore-mentioned scaling behavior. These observations were made on model networks and on a large social network inferred from cell-phone trace logs (∼5.5×10(6) nodes and ∼2.7×10(7) edges). Finally, we apply these concepts to efficiently detect the vulnerability backbone of a network (defined as the smallest percolating cluster of the highest betweenness nodes and edges) and illustrate the importance of weight-based centrality
Measurement of organization in complex and co-evolving networks
NASA Astrophysics Data System (ADS)
Georgiev, Georgi
2012-02-01
We apply a new method for measurement of organization of complex and co-evolving networks using the quantity of physical action. We consider simple arrangements of elements in a network and constraints to their motion along paths and calculate the amount of organization in each system using the following measure: organization is the inverse of the average sum of physical actions of all elements in a system per unit motion multiplied by the Planck's constant. The meaning of quantity of organization here is the number of quanta of action per one unit motion along a path of an element. A unit motion along a path for a network, such as internet, is the transmission of one bit of information. The calculation can be expanded to systems consisting of many elements and constraints and also can be followed as a function of time with improvement of the organization of a system or connected systems and networks. Thus, the principle of least action becomes the driving force, and the least action state of the system, the attractor for all of the paths of its elements and states of its constraints. We consider also the rate of constraint minimization, or decrease of action per element and motion, as a function of the number of elements i.e. quality as a function of quantity. Increase of quantity, within specified limits, leads to increase of level of organization and vice versa.
Unraveling chaotic attractors by complex networks and measurements of stock market complexity
Cao, Hongduo; Li, Ying
2014-03-15
We present a novel method for measuring the complexity of a time series by unraveling a chaotic attractor modeled on complex networks. The complexity index R, which can potentially be exploited for prediction, has a similar meaning to the Kolmogorov complexity (calculated from the Lempel–Ziv complexity), and is an appropriate measure of a series' complexity. The proposed method is used to research the complexity of the world's major capital markets. None of these markets are completely random, and they have different degrees of complexity, both over the entire length of their time series and at a level of detail. However, developing markets differ significantly from mature markets. Specifically, the complexity of mature stock markets is stronger and more stable over time, whereas developing markets exhibit relatively low and unstable complexity over certain time periods, implying a stronger long-term price memory process.
Offdiagonal complexity: A computationally quick complexity measure for graphs and networks
NASA Astrophysics Data System (ADS)
Claussen, Jens Christian
2007-02-01
A vast variety of biological, social, and economical networks shows topologies drastically differing from random graphs; yet the quantitative characterization remains unsatisfactory from a conceptual point of view. Motivated from the discussion of small scale-free networks, a biased link distribution entropy is defined, which takes an extremum for a power-law distribution. This approach is extended to the node-node link cross-distribution, whose nondiagonal elements characterize the graph structure beyond link distribution, cluster coefficient and average path length. From here a simple (and computationally cheap) complexity measure can be defined. This offdiagonal complexity (OdC) is proposed as a novel measure to characterize the complexity of an undirected graph, or network. While both for regular lattices and fully connected networks OdC is zero, it takes a moderately low value for a random graph and shows high values for apparently complex structures as scale-free networks and hierarchical trees. The OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates.
Measuring the significance of community structure in complex networks
NASA Astrophysics Data System (ADS)
Hu, Yanqing; Nie, Yuchao; Yang, Hua; Cheng, Jie; Fan, Ying; di, Zengru
2010-12-01
Many complex systems can be represented as networks, and separating a network into communities could simplify functional analysis considerably. Many approaches have recently been proposed to detect communities, but a method to determine whether the detected communities are significant is still lacking. In this paper, an index to evaluate the significance of communities in networks is proposed based on perturbation of the network. In contrast to previous approaches, the network is disturbed gradually, and the index is defined by integrating all of the similarities between the community structures before and after perturbation. Moreover, by taking the null model into account, the index eliminates scale effects. Thus, it can evaluate and compare the significance of communities in different networks. The method has been tested in many artificial and real-world networks. The results show that the index is in fact independent of the size of the network and the number of communities. With this approach, clear communities are found to always exist in social networks, but significant communities cannot be found in protein interactions and metabolic networks.
Multi-attribute integrated measurement of node importance in complex networks
NASA Astrophysics Data System (ADS)
Wang, Shibo; Zhao, Jinlou
2015-11-01
The measure of node importance in complex networks is very important to the research of networks stability and robustness; it also can ensure the security of the whole network. Most researchers have used a single indicator to measure the networks node importance, so that the obtained measurement results only reflect certain aspects of the networks with a loss of information. Meanwhile, because of the difference of networks topology, the nodes' importance should be described by combining the character of the networks topology. Most of the existing evaluation algorithms cannot completely reflect the circumstances of complex networks, so this paper takes into account the degree of centrality, the relative closeness centrality, clustering coefficient, and topology potential and raises an integrated measuring method to measure the nodes' importance. This method can reflect nodes' internal and outside attributes and eliminate the influence of network structure on the node importance. The experiments of karate network and dolphin network show that networks topology structure integrated measure has smaller range of metrical result than a single indicator and more universal. Experiments show that attacking the North American power grid and the Internet network with the method has a faster convergence speed than other methods.
Multi-attribute integrated measurement of node importance in complex networks.
Wang, Shibo; Zhao, Jinlou
2015-11-01
The measure of node importance in complex networks is very important to the research of networks stability and robustness; it also can ensure the security of the whole network. Most researchers have used a single indicator to measure the networks node importance, so that the obtained measurement results only reflect certain aspects of the networks with a loss of information. Meanwhile, because of the difference of networks topology, the nodes' importance should be described by combining the character of the networks topology. Most of the existing evaluation algorithms cannot completely reflect the circumstances of complex networks, so this paper takes into account the degree of centrality, the relative closeness centrality, clustering coefficient, and topology potential and raises an integrated measuring method to measure the nodes' importance. This method can reflect nodes' internal and outside attributes and eliminate the influence of network structure on the node importance. The experiments of karate network and dolphin network show that networks topology structure integrated measure has smaller range of metrical result than a single indicator and more universal. Experiments show that attacking the North American power grid and the Internet network with the method has a faster convergence speed than other methods. PMID:26627565
An Attractor-Based Complexity Measurement for Boolean Recurrent Neural Networks
Cabessa, Jérémie; Villa, Alessandro E. P.
2014-01-01
We provide a novel refined attractor-based complexity measurement for Boolean recurrent neural networks that represents an assessment of their computational power in terms of the significance of their attractor dynamics. This complexity measurement is achieved by first proving a computational equivalence between Boolean recurrent neural networks and some specific class of -automata, and then translating the most refined classification of -automata to the Boolean neural network context. As a result, a hierarchical classification of Boolean neural networks based on their attractive dynamics is obtained, thus providing a novel refined attractor-based complexity measurement for Boolean recurrent neural networks. These results provide new theoretical insights to the computational and dynamical capabilities of neural networks according to their attractive potentialities. An application of our findings is illustrated by the analysis of the dynamics of a simplified model of the basal ganglia-thalamocortical network simulated by a Boolean recurrent neural network. This example shows the significance of measuring network complexity, and how our results bear new founding elements for the understanding of the complexity of real brain circuits. PMID:24727866
McDonough, Ian M.; Nashiro, Kaoru
2014-01-01
An emerging field of research focused on fluctuations in brain signals has provided evidence that the complexity of those signals, as measured by entropy, conveys important information about network dynamics (e.g., local and distributed processing). While much research has focused on how neural complexity differs in populations with different age groups or clinical disorders, substantially less research has focused on the basic understanding of neural complexity in populations with young and healthy brain states. The present study used resting-state fMRI data from the Human Connectome Project (Van Essen et al., 2013) to test the extent that neural complexity in the BOLD signal, as measured by multiscale entropy (1) would differ from random noise, (2) would differ between four major resting-state networks previously associated with higher-order cognition, and (3) would be associated with the strength and extent of functional connectivity—a complementary method of estimating information processing. We found that complexity in the BOLD signal exhibited different patterns of complexity from white, pink, and red noise and that neural complexity was differentially expressed between resting-state networks, including the default mode, cingulo-opercular, left and right frontoparietal networks. Lastly, neural complexity across all networks was negatively associated with functional connectivity at fine scales, but was positively associated with functional connectivity at coarse scales. The present study is the first to characterize neural complexity in BOLD signals at a high temporal resolution and across different networks and might help clarify the inconsistencies between neural complexity and functional connectivity, thus informing the mechanisms underlying neural complexity. PMID:24959130
A new closeness centrality measure via effective distance in complex networks
NASA Astrophysics Data System (ADS)
Du, Yuxian; Gao, Cai; Chen, Xin; Hu, Yong; Sadiq, Rehan; Deng, Yong
2015-03-01
Closeness centrality (CC) measure, as a well-known global measure, is widely applied in many complex networks. However, the classical CC presents many problems for flow networks since these networks are directed and weighted. To address these issues, we propose an effective distance based closeness centrality (EDCC), which uses effective distance to replace conventional geographic distance and binary distance obtained by Dijkstra's shortest path algorithm. The proposed EDCC considers not only the global structure of the network but also the local information of nodes. And it can be well applied in directed or undirected, weighted or unweighted networks. Susceptible-Infected model is utilized to evaluate the performance by using the spreading rate and the number of infected nodes. Numerical examples simulated on four real networks are given to show the effectiveness of the proposed EDCC.
NASA Astrophysics Data System (ADS)
Zemp, D. C.; Wiedermann, M.; Kurths, J.; Rammig, A.; Donges, J. F.
2014-09-01
In many real-world networks nodes represent agents or objects of different sizes or importance. However, the size of the nodes is rarely taken into account in network analysis, possibly inducing bias in network measures and confusion in their interpretation. Recently, a new axiomatic scheme of node-weighted network measures has been suggested for networks with undirected and unweighted edges. However, many real-world systems are best represented by complex networks which have directed and/or weighted edges. Here, we extend this approach and suggest new versions of the degree and the clustering coefficient associated to network motifs for networks with directed and/or weighted edges and weighted nodes. We apply these measures to a spatially embedded network model and a real-world moisture recycling network. We show that these measures improve the representation of the underlying systems' structure and are of general use for studying any type of complex network.
Measuring mixing patterns in complex networks by Spearman rank correlation coefficient
NASA Astrophysics Data System (ADS)
Zhang, Wen-Yao; Wei, Zong-Wen; Wang, Bing-Hong; Han, Xiao-Pu
2016-06-01
In this paper, we utilize Spearman rank correlation coefficient to measure mixing patterns in complex networks. Compared with the widely used Pearson coefficient, Spearman coefficient is rank-based, nonparametric, and size-independent. Thus it is more effective to assess linking patterns of diverse networks, especially for large-size networks. We demonstrate this point by testing a variety of empirical and artificial networks. Moreover, we show that normalized Spearman ranks of stubs are subject to an interesting linear rule where the correlation coefficient is just the Spearman coefficient. This compelling linear relationship allows us to directly produce networks with any prescribed Spearman coefficient. Our method apparently has an edge over the well known uncorrelated configuration model.
NASA Astrophysics Data System (ADS)
Zemp, Delphine; Wiedermann, Marc; Donges, Jonathan; Schleussner, Carl-Friedrich; Rammig, Anja
2014-05-01
In many real-world networks, nodes represents agents of different sizes or importance. However, the sizes of the node are rarely taken into account in networks analysis, inducing bias in network measures and confusion in their interpretation. Recently, a new axiomatic scheme of node-weighted network measures have been suggested for networks with undirected and unweighted edges. However, many real-world systems are best represented by complex networks which have directed and/or weighted edges. Here, we extend this approach and suggest node-centrality measures for the networks with directed and/or weighted edges and weighted nodes. We apply these measures on a artificial spatially embedded network and a real-world moisture recycling network. We show that these measures improve the representation of the underlying physical systems and can be used for any types of complex networks.
Local difference measures between complex networks for dynamical system model evaluation.
Lange, Stefan; Donges, Jonathan F; Volkholz, Jan; Kurths, Jürgen
2015-01-01
A faithful modeling of real-world dynamical systems necessitates model evaluation. A recent promising methodological approach to this problem has been based on complex networks, which in turn have proven useful for the characterization of dynamical systems. In this context, we introduce three local network difference measures and demonstrate their capabilities in the field of climate modeling, where these measures facilitate a spatially explicit model evaluation.Building on a recent study by Feldhoff et al. [8] we comparatively analyze statistical and dynamical regional climate simulations of the South American monsoon system [corrected]. types of climate networks representing different aspects of rainfall dynamics are constructed from the modeled precipitation space-time series. Specifically, we define simple graphs based on positive as well as negative rank correlations between rainfall anomaly time series at different locations, and such based on spatial synchronizations of extreme rain events. An evaluation against respective networks built from daily satellite data provided by the Tropical Rainfall Measuring Mission 3B42 V7 reveals far greater differences in model performance between network types for a fixed but arbitrary climate model than between climate models for a fixed but arbitrary network type. We identify two sources of uncertainty in this respect. Firstly, climate variability limits fidelity, particularly in the case of the extreme event network; and secondly, larger geographical link lengths render link misplacements more likely, most notably in the case of the anticorrelation network; both contributions are quantified using suitable ensembles of surrogate networks. Our model evaluation approach is applicable to any multidimensional dynamical system and especially our simple graph difference measures are highly versatile as the graphs to be compared may be constructed in whatever way required. Generalizations to directed as well as edge- and node
Local Difference Measures between Complex Networks for Dynamical System Model Evaluation
Lange, Stefan; Donges, Jonathan F.; Volkholz, Jan; Kurths, Jürgen
2015-01-01
A faithful modeling of real-world dynamical systems necessitates model evaluation. A recent promising methodological approach to this problem has been based on complex networks, which in turn have proven useful for the characterization of dynamical systems. In this context, we introduce three local network difference measures and demonstrate their capabilities in the field of climate modeling, where these measures facilitate a spatially explicit model evaluation. Building on a recent study by Feldhoff et al. [1] we comparatively analyze statistical and dynamical regional climate simulations of the South American monsoon system. Three types of climate networks representing different aspects of rainfall dynamics are constructed from the modeled precipitation space-time series. Specifically, we define simple graphs based on positive as well as negative rank correlations between rainfall anomaly time series at different locations, and such based on spatial synchronizations of extreme rain events. An evaluation against respective networks built from daily satellite data provided by the Tropical Rainfall Measuring Mission 3B42 V7 reveals far greater differences in model performance between network types for a fixed but arbitrary climate model than between climate models for a fixed but arbitrary network type. We identify two sources of uncertainty in this respect. Firstly, climate variability limits fidelity, particularly in the case of the extreme event network; and secondly, larger geographical link lengths render link misplacements more likely, most notably in the case of the anticorrelation network; both contributions are quantified using suitable ensembles of surrogate networks. Our model evaluation approach is applicable to any multidimensional dynamical system and especially our simple graph difference measures are highly versatile as the graphs to be compared may be constructed in whatever way required. Generalizations to directed as well as edge- and node
Correlation dimension of complex networks.
Lacasa, Lucas; Gómez-Gardeñes, Jesús
2013-04-19
We propose a new measure to characterize the dimension of complex networks based on the ergodic theory of dynamical systems. This measure is derived from the correlation sum of a trajectory generated by a random walker navigating the network, and extends the classical Grassberger-Procaccia algorithm to the context of complex networks. The method is validated with reliable results for both synthetic networks and real-world networks such as the world air-transportation network or urban networks, and provides a computationally fast way for estimating the dimensionality of networks which only relies on the local information provided by the walkers. PMID:23679650
Entropy measures for networks: toward an information theory of complex topologies.
Anand, Kartik; Bianconi, Ginestra
2009-10-01
The quantification of the complexity of networks is, today, a fundamental problem in the physics of complex systems. A possible roadmap to solve the problem is via extending key concepts of information theory to networks. In this Rapid Communication we propose how to define the Shannon entropy of a network ensemble and how it relates to the Gibbs and von Neumann entropies of network ensembles. The quantities we introduce here will play a crucial role for the formulation of null models of networks through maximum-entropy arguments and will contribute to inference problems emerging in the field of complex networks. PMID:19905379
PAFit: A Statistical Method for Measuring Preferential Attachment in Temporal Complex Networks
Pham, Thong; Sheridan, Paul; Shimodaira, Hidetoshi
2015-01-01
Preferential attachment is a stochastic process that has been proposed to explain certain topological features characteristic of complex networks from diverse domains. The systematic investigation of preferential attachment is an important area of research in network science, not only for the theoretical matter of verifying whether this hypothesized process is operative in real-world networks, but also for the practical insights that follow from knowledge of its functional form. Here we describe a maximum likelihood based estimation method for the measurement of preferential attachment in temporal complex networks. We call the method PAFit, and implement it in an R package of the same name. PAFit constitutes an advance over previous methods primarily because we based it on a nonparametric statistical framework that enables attachment kernel estimation free of any assumptions about its functional form. We show this results in PAFit outperforming the popular methods of Jeong and Newman in Monte Carlo simulations. What is more, we found that the application of PAFit to a publically available Flickr social network dataset yielded clear evidence for a deviation of the attachment kernel from the popularly assumed log-linear form. Independent of our main work, we provide a correction to a consequential error in Newman’s original method which had evidently gone unnoticed since its publication over a decade ago. PMID:26378457
Eigencentrality based on dissimilarity measures reveals central nodes in complex networks
NASA Astrophysics Data System (ADS)
Alvarez-Socorro, A. J.; Herrera-Almarza, G. C.; González-Díaz, L. A.
2015-11-01
One of the most important problems in complex network’s theory is the location of the entities that are essential or have a main role within the network. For this purpose, the use of dissimilarity measures (specific to theory of classification and data mining) to enrich the centrality measures in complex networks is proposed. The centrality method used is the eigencentrality which is based on the heuristic that the centrality of a node depends on how central are the nodes in the immediate neighbourhood (like rich get richer phenomenon). This can be described by an eigenvalues problem, however the information of the neighbourhood and the connections between neighbours is not taken in account, neglecting their relevance when is one evaluates the centrality/importance/influence of a node. The contribution calculated by the dissimilarity measure is parameter independent, making the proposed method is also parameter independent. Finally, we perform a comparative study of our method versus other methods reported in the literature, obtaining more accurate and less expensive computational results in most cases.
Eigencentrality based on dissimilarity measures reveals central nodes in complex networks
Alvarez-Socorro, A. J.; Herrera-Almarza, G. C.; González-Díaz, L. A.
2015-01-01
One of the most important problems in complex network’s theory is the location of the entities that are essential or have a main role within the network. For this purpose, the use of dissimilarity measures (specific to theory of classification and data mining) to enrich the centrality measures in complex networks is proposed. The centrality method used is the eigencentrality which is based on the heuristic that the centrality of a node depends on how central are the nodes in the immediate neighbourhood (like rich get richer phenomenon). This can be described by an eigenvalues problem, however the information of the neighbourhood and the connections between neighbours is not taken in account, neglecting their relevance when is one evaluates the centrality/importance/influence of a node. The contribution calculated by the dissimilarity measure is parameter independent, making the proposed method is also parameter independent. Finally, we perform a comparative study of our method versus other methods reported in the literature, obtaining more accurate and less expensive computational results in most cases. PMID:26603652
Complex networks: Patterns of complexity
NASA Astrophysics Data System (ADS)
Pastor-Satorras, Romualdo; Vespignani, Alessandro
2010-07-01
The Turing mechanism provides a paradigm for the spontaneous generation of patterns in reaction-diffusion systems. A framework that describes Turing-pattern formation in the context of complex networks should provide a new basis for studying the phenomenon.
A quantitative measure for organization of complex and co-evolving networks
NASA Astrophysics Data System (ADS)
Georgiev, Georgi
2012-02-01
To define evolution and self-organization in complex networks a quantitative measure for organization is necessary. Two systems should be numerically distinguishable by their degree of organization and their rate of self-organization. Here we apply as a measure for quantity of organization the inverse of the average sum of physical actions of all elements in a system per unit motion multiplied by the Planck's constant. The meaning of quantity of organization here is the number of quanta of action per one unit motion of an element. For example, a unit motion for electrons on a computer chip is the one necessary for one computation. This definition can be applied to the organization in any complex system. Systems self-organize to decrease the average action per element per unit motion in them. This is the attractor for a dynamical, nonlinear system evolving in time. Constraints increase this average action, so constraint minimization is a basic mechanism for action minimization. Increase of quantity of elements in the network, leads to faster constraint minimization through grouping, decrease of average action per element and motion and therefore faster self-organization and evolution.
Attack vulnerability of complex networks
NASA Astrophysics Data System (ADS)
Holme, Petter; Kim, Beom Jun; Yoon, Chang No; Han, Seung Kee
2002-05-01
We study the response of complex networks subject to attacks on vertices and edges. Several existing complex network models as well as real-world networks of scientific collaborations and Internet traffic are numerically investigated, and the network performance is quantitatively measured by the average inverse geodesic length and the size of the largest connected subgraph. For each case of attacks on vertices and edges, four different attacking strategies are used: removals by the descending order of the degree and the betweenness centrality, calculated for either the initial network or the current network during the removal procedure. It is found that the removals by the recalculated degrees and betweenness centralities are often more harmful than the attack strategies based on the initial network, suggesting that the network structure changes as important vertices or edges are removed. Furthermore, the correlation between the betweenness centrality and the degree in complex networks is studied.
Measuring microscopic evolution processes of complex networks based on empirical data
NASA Astrophysics Data System (ADS)
Chi, Liping
2015-04-01
Aiming at understanding the microscopic mechanism of complex systems in real world, we perform the measurement that characterizes the evolution properties on two empirical data sets. In the Autonomous Systems Internet data, the network size keeps growing although the system suffers a high rate of node deletion (r = 0.4) and link deletion (q = 0.81). However, the average degree keeps almost unchanged during the whole time range. At each time step the external links attached to a new node are about c = 1.1 and the internal links added between existing nodes are approximately m = 8. For the Scientific Collaboration data, it is a cumulated result of all the authors from 1893 up to the considered year. There is no deletion of nodes and links, r = q = 0. The external and internal links at each time step are c = 1.04 and m = 0, correspondingly. The exponents of degree distribution p(k) ∼ k-γ of these two empirical datasets γdata are in good agreement with that obtained theoretically γtheory. The results indicate that these evolution quantities may provide an insight into capturing the microscopic dynamical processes that govern the network topology.
Forman curvature for complex networks
NASA Astrophysics Data System (ADS)
Sreejith, R. P.; Mohanraj, Karthikeyan; Jost, Jürgen; Saucan, Emil; Samal, Areejit
2016-06-01
We adapt Forman’s discretization of Ricci curvature to the case of undirected networks, both weighted and unweighted, and investigate the measure in a variety of model and real-world networks. We find that most nodes and edges in model and real networks have a negative curvature. Furthermore, the distribution of Forman curvature of nodes and edges is narrow in random and small-world networks, while the distribution is broad in scale-free and real-world networks. In most networks, Forman curvature is found to display significant negative correlation with degree and centrality measures. However, Forman curvature is uncorrelated with clustering coefficient in most networks. Importantly, we find that both model and real networks are vulnerable to targeted deletion of nodes with highly negative Forman curvature. Our results suggest that Forman curvature can be employed to gain novel insights on the organization of complex networks.
Emergent Complex Network Geometry
NASA Astrophysics Data System (ADS)
Wu, Zhihao; Menichetti, Giulia; Rahmede, Christoph; Bianconi, Ginestra
2015-05-01
Networks are mathematical structures that are universally used to describe a large variety of complex systems such as the brain or the Internet. Characterizing the geometrical properties of these networks has become increasingly relevant for routing problems, inference and data mining. In real growing networks, topological, structural and geometrical properties emerge spontaneously from their dynamical rules. Nevertheless we still miss a model in which networks develop an emergent complex geometry. Here we show that a single two parameter network model, the growing geometrical network, can generate complex network geometries with non-trivial distribution of curvatures, combining exponential growth and small-world properties with finite spectral dimensionality. In one limit, the non-equilibrium dynamical rules of these networks can generate scale-free networks with clustering and communities, in another limit planar random geometries with non-trivial modularity. Finally we find that these properties of the geometrical growing networks are present in a large set of real networks describing biological, social and technological systems.
Emergent Complex Network Geometry
Wu, Zhihao; Menichetti, Giulia; Rahmede, Christoph; Bianconi, Ginestra
2015-01-01
Networks are mathematical structures that are universally used to describe a large variety of complex systems such as the brain or the Internet. Characterizing the geometrical properties of these networks has become increasingly relevant for routing problems, inference and data mining. In real growing networks, topological, structural and geometrical properties emerge spontaneously from their dynamical rules. Nevertheless we still miss a model in which networks develop an emergent complex geometry. Here we show that a single two parameter network model, the growing geometrical network, can generate complex network geometries with non-trivial distribution of curvatures, combining exponential growth and small-world properties with finite spectral dimensionality. In one limit, the non-equilibrium dynamical rules of these networks can generate scale-free networks with clustering and communities, in another limit planar random geometries with non-trivial modularity. Finally we find that these properties of the geometrical growing networks are present in a large set of real networks describing biological, social and technological systems. PMID:25985280
Organization of complex networks
NASA Astrophysics Data System (ADS)
Kitsak, Maksim
Many large complex systems can be successfully analyzed using the language of graphs and networks. Interactions between the objects in a network are treated as links connecting nodes. This approach to understanding the structure of networks is an important step toward understanding the way corresponding complex systems function. Using the tools of statistical physics, we analyze the structure of networks as they are found in complex systems such as the Internet, the World Wide Web, and numerous industrial and social networks. In the first chapter we apply the concept of self-similarity to the study of transport properties in complex networks. Self-similar or fractal networks, unlike non-fractal networks, exhibit similarity on a range of scales. We find that these fractal networks have transport properties that differ from those of non-fractal networks. In non-fractal networks, transport flows primarily through the hubs. In fractal networks, the self-similar structure requires any transport to also flow through nodes that have only a few connections. We also study, in models and in real networks, the crossover from fractal to non-fractal networks that occurs when a small number of random interactions are added by means of scaling techniques. In the second chapter we use k-core techniques to study dynamic processes in networks. The k-core of a network is the network's largest component that, within itself, exhibits all nodes with at least k connections. We use this k-core analysis to estimate the relative leadership positions of firms in the Life Science (LS) and Information and Communication Technology (ICT) sectors of industry. We study the differences in the k-core structure between the LS and the ICT sectors. We find that the lead segment (highest k-core) of the LS sector, unlike that of the ICT sector, is remarkably stable over time: once a particular firm enters the lead segment, it is likely to remain there for many years. In the third chapter we study how
Oscillations of complex networks
NASA Astrophysics Data System (ADS)
Wang, Xingang; Lai, Ying-Cheng; Lai, Choy Heng
2006-12-01
A complex network processing information or physical flows is usually characterized by a number of macroscopic quantities such as the diameter and the betweenness centrality. An issue of significant theoretical and practical interest is how such quantities respond to sudden changes caused by attacks or disturbances in recoverable networks, i.e., functions of the affected nodes are only temporarily disabled or partially limited. By introducing a model to address this issue, we find that, for a finite-capacity network, perturbations can cause the network to oscillate persistently in the sense that the characterizing quantities vary periodically or randomly with time. We provide a theoretical estimate of the critical capacity-parameter value for the onset of the network oscillation. The finding is expected to have broad implications as it suggests that complex networks may be structurally highly dynamic.
Immunization of complex networks
NASA Astrophysics Data System (ADS)
Pastor-Satorras, Romualdo; Vespignani, Alessandro
2002-03-01
Complex networks such as the sexual partnership web or the Internet often show a high degree of redundancy and heterogeneity in their connectivity properties. This peculiar connectivity provides an ideal environment for the spreading of infective agents. Here we show that the random uniform immunization of individuals does not lead to the eradication of infections in all complex networks. Namely, networks with scale-free properties do not acquire global immunity from major epidemic outbreaks even in the presence of unrealistically high densities of randomly immunized individuals. The absence of any critical immunization threshold is due to the unbounded connectivity fluctuations of scale-free networks. Successful immunization strategies can be developed only by taking into account the inhomogeneous connectivity properties of scale-free networks. In particular, targeted immunization schemes, based on the nodes' connectivity hierarchy, sharply lower the network's vulnerability to epidemic attacks.
Complexity measures of the central respiratory networks during wakefulness and sleep
NASA Astrophysics Data System (ADS)
Dragomir, Andrei; Akay, Yasemin; Curran, Aidan K.; Akay, Metin
2008-06-01
Since sleep is known to influence respiratory activity we studied whether the sleep state would affect the complexity value of the respiratory network output. Specifically, we tested the hypothesis that the complexity values of the diaphragm EMG (EMGdia) activity would be lower during REM compared to NREM. Furthermore, since REM is primarily generated by a homogeneous population of neurons in the medulla, the possibility that REM-related respiratory output would be less complex than that of the awake state was also considered. Additionally, in order to examine the influence of neuron vulnerabilities within the rostral ventral medulla (RVM) on the complexity of the respiratory network output, we inhibited respiratory neurons in the RVM by microdialysis of GABAA receptor agonist muscimol. Diaphragm EMG, nuchal EMG, EEG, EOG as well as other physiological signals (tracheal pressure, blood pressure and respiratory volume) were recorded from five unanesthetized chronically instrumented intact piglets (3-10 days old). Complexity of the diaphragm EMG (EMGdia) signal during wakefulness, NREM and REM was evaluated using the approximate entropy method (ApEn). ApEn values of the EMGdia during NREM and REM sleep were found significantly (p < 0.05 and p < 0.001, respectively) lower than those of awake EMGdia after muscimol inhibition. In the absence of muscimol, only the differences between REM and wakefulness ApEn values were found to be significantly different.
Combining classification with fMRI-derived complex network measures for potential neurodiagnostics.
Fekete, Tomer; Wilf, Meytal; Rubin, Denis; Edelman, Shimon; Malach, Rafael; Mujica-Parodi, Lilianne R
2013-01-01
Complex network analysis (CNA), a subset of graph theory, is an emerging approach to the analysis of functional connectivity in the brain, allowing quantitative assessment of network properties such as functional segregation, integration, resilience, and centrality. Here, we show how a classification framework complements complex network analysis by providing an efficient and objective means of selecting the best network model characterizing given functional connectivity data. We describe a novel kernel-sum learning approach, block diagonal optimization (BDopt), which can be applied to CNA features to single out graph-theoretic characteristics and/or anatomical regions of interest underlying discrimination, while mitigating problems of multiple comparisons. As a proof of concept for the method's applicability to future neurodiagnostics, we apply BDopt classification to two resting state fMRI data sets: a trait (between-subjects) classification of patients with schizophrenia vs. controls, and a state (within-subjects) classification of wake vs. sleep, demonstrating powerful discriminant accuracy for the proposed framework. PMID:23671641
Controllability of Complex Networks
NASA Astrophysics Data System (ADS)
Liu, Yang; Slotine, Jean-Jacques; Barabasi, Albert-Laszlo
2011-03-01
The ultimate proof of our understanding of natural or technological systems is reflected in our ability to control them. While control theory offers mathematical tools to steer engineered systems towards a desired state, we lack a general framework to control complex self-organized systems, like the regulatory network of a cell or the Internet. Here we develop analytical tools to study the controllability of an arbitrary complex directed network, identifying the set of driver nodes whose time-dependent control can guide the system's dynamics. We apply these tools to real and model networks, finding that sparse inhomogeneous networks, which emerge in many real complex systems, are the most difficult to control. In contrast, dense and homogeneous networks can be controlled via a few driver nodes. Counterintuitively, we find that in both model and real systems the driver nodes tend to avoid the hubs. We show that the robustness of control to link failure is determined by a core percolation problem, helping us understand why many complex systems are relatively insensitive to link deletion. The developed approach offers a framework to address the controllability of an arbitrary network, representing a key step towards the eventual control of complex systems.
Compressively sensed complex networks.
Dunlavy, Daniel M.; Ray, Jaideep; Pinar, Ali
2010-07-01
The aim of this project is to develop low dimension parametric (deterministic) models of complex networks, to use compressive sensing (CS) and multiscale analysis to do so and to exploit the structure of complex networks (some are self-similar under coarsening). CS provides a new way of sampling and reconstructing networks. The approach is based on multiresolution decomposition of the adjacency matrix and its efficient sampling. It requires preprocessing of the adjacency matrix to make it 'blocky' which is the biggest (combinatorial) algorithm challenge. Current CS reconstruction algorithm makes no use of the structure of a graph, its very general (and so not very efficient/customized). Other model-based CS techniques exist, but not yet adapted to networks. Obvious starting point for future work is to increase the efficiency of reconstruction.
Synchronization in complex networks
Arenas, A.; Diaz-Guilera, A.; Moreno, Y.; Zhou, C.; Kurths, J.
2007-12-12
Synchronization processes in populations of locally interacting elements are in the focus of intense research in physical, biological, chemical, technological and social systems. The many efforts devoted to understand synchronization phenomena in natural systems take now advantage of the recent theory of complex networks. In this review, we report the advances in the comprehension of synchronization phenomena when oscillating elements are constrained to interact in a complex network topology. We also overview the new emergent features coming out from the interplay between the structure and the function of the underlying pattern of connections. Extensive numerical work as well as analytical approaches to the problem are presented. Finally, we review several applications of synchronization in complex networks to different disciplines: biological systems and neuroscience, engineering and computer science, and economy and social sciences.
Synchronization in complex networks
NASA Astrophysics Data System (ADS)
Arenas, Alex; Díaz-Guilera, Albert; Kurths, Jurgen; Moreno, Yamir; Zhou, Changsong
2008-12-01
Synchronization processes in populations of locally interacting elements are the focus of intense research in physical, biological, chemical, technological and social systems. The many efforts devoted to understanding synchronization phenomena in natural systems now take advantage of the recent theory of complex networks. In this review, we report the advances in the comprehension of synchronization phenomena when oscillating elements are constrained to interact in a complex network topology. We also take an overview of the new emergent features coming out from the interplay between the structure and the function of the underlying patterns of connections. Extensive numerical work as well as analytical approaches to the problem are presented. Finally, we review several applications of synchronization in complex networks to different disciplines: biological systems and neuroscience, engineering and computer science, and economy and social sciences.
Information Horizons in Complex Networks
NASA Astrophysics Data System (ADS)
Sneppen, Kim
2005-03-01
We investigate how the structure constrain specific communication in social-, man-made and biological networks. We find that human networks of governance and collaboration are predictable on teat-a-teat level, reflecting well defined pathways, but globally inefficient (1). In contrast, the Internet tends to have better overall communication abilities, more alternative pathways, and is therefore more robust. Between these extremes are the molecular network of living organisms. Further, for most real world networks we find that communication ability is favored by topology on small distances, but disfavored at larger distances (2,3,4). We discuss the topological implications in terms of modularity and the positioning of hubs in the networks (5,6). Finally we introduce some simple models which demonstarte how communication may shape the structure of in particular man made networks (7,8). 1) K. Sneppen, A. Trusina, M. Rosvall (2004). Hide and seek on complex networks [cond-mat/0407055] 2) M. Rosvall, A. Trusina, P. Minnhagen and K. Sneppen (2004). Networks and Cities: An Information Perspective [cond-mat/0407054]. In PRL. 3) A. Trusina, M. Rosvall, K. Sneppen (2004). Information Horizons in Networks. [cond-mat/0412064] 4) M. Rosvall, P. Minnhagen, K. Sneppen (2004). Navigating Networks with Limited Information. [cond-mat/0412051] 5) S. Maslov and K. Sneppen (2002). Specificity and stability in topology of protein networks Science 296, 910-913 [cond-mat/0205380]. 6) A. Trusina, S. Maslov, P. Minnhagen, K. Sneppen Hierarchy Measures in Complex Networks. Phys. Rev. Lett. 92, 178702 [cond-mat/0308339]. 7) M. Rosvall and K. Sneppen (2003). Modeling Dynamics of Information Networks. Phys. Rev. Lett. 91, 178701 [cond-mat/0308399]. 8) B-J. Kim, A. Trusina, P. Minnhagen, K. Sneppen (2003). Self Organized Scale-Free Networks from Merging and Regeneration. nlin.AO/0403006. In European Journal of Physics.
Complex Networks and Socioeconomic Applications
NASA Astrophysics Data System (ADS)
Almendral, Juan A.; López, Luis; Mendes, Jose F.; Sanjuán, Miguel A. F.
2003-04-01
The study and characterization of complex systems is a fruitful research area nowadays. Special attention has been paid recently to complex networks, where graph and network analysis plays an important role since they reduce a given system to a simpler problem. Using a simple model for the information flow on social networks, we show that the traditional hierarchical topologies frequently used by companies and organizations, are poorly designed in terms of efficiency. Moreover, we prove that this type of structures are the result of the individual aim of monopolizing as much information as possible within the network. As the information is an appropriate measurement of centrality, we conclude that this kind of topology is so attractive for leaders because the global influence each actor has within the network is completely determined by the hierarchical level occupied. The effect on the efficiency caused by a change in a traditional hierarchical topology is also analyzed. In particular, by introducing the possibility of communication on the same level of the hierarchy.
Role models for complex networks
NASA Astrophysics Data System (ADS)
Reichardt, J.; White, D. R.
2007-11-01
We present a framework for automatically decomposing (“block-modeling”) the functional classes of agents within a complex network. These classes are represented by the nodes of an image graph (“block model”) depicting the main patterns of connectivity and thus functional roles in the network. Using a first principles approach, we derive a measure for the fit of a network to any given image graph allowing objective hypothesis testing. From the properties of an optimal fit, we derive how to find the best fitting image graph directly from the network and present a criterion to avoid overfitting. The method can handle both two-mode and one-mode data, directed and undirected as well as weighted networks and allows for different types of links to be dealt with simultaneously. It is non-parametric and computationally efficient. The concepts of structural equivalence and modularity are found as special cases of our approach. We apply our method to the world trade network and analyze the roles individual countries play in the global economy.
Complex networks in brain electrical activity
NASA Astrophysics Data System (ADS)
Ray, C.; Ruffini, G.; Marco-Pallarés, J.; Fuentemilla, L.; Grau, C.
2007-08-01
This letter reports a method to extract a functional network of the human brain from electroencephalogram measurements. A network analysis was performed on the resultant network and the statistics of the cluster coefficient, node degree, path length, and physical distance of the links, were studied. Even given the low electrode count of the experimental data the method was able to extract networks with network parameters that clearly depend on the type of stimulus presented to the subject. This type of analysis opens a door to studying the cerebral networks underlying brain electrical activity, and links the fields of complex networks and cognitive neuroscience.
Online Community Detection for Large Complex Networks
Pan, Gang; Zhang, Wangsheng; Wu, Zhaohui; Li, Shijian
2014-01-01
Complex networks describe a wide range of systems in nature and society. To understand complex networks, it is crucial to investigate their community structure. In this paper, we develop an online community detection algorithm with linear time complexity for large complex networks. Our algorithm processes a network edge by edge in the order that the network is fed to the algorithm. If a new edge is added, it just updates the existing community structure in constant time, and does not need to re-compute the whole network. Therefore, it can efficiently process large networks in real time. Our algorithm optimizes expected modularity instead of modularity at each step to avoid poor performance. The experiments are carried out using 11 public data sets, and are measured by two criteria, modularity and NMI (Normalized Mutual Information). The results show that our algorithm's running time is less than the commonly used Louvain algorithm while it gives competitive performance. PMID:25061683
Jun Kang, Yang; Yeom, Eunseop; Lee, Sang-Joon
2013-01-01
Blood viscosity has been considered as one of important biophysical parameters for effectively monitoring variations in physiological and pathological conditions of circulatory disorders. Standard previous methods make it difficult to evaluate variations of blood viscosity under cardiopulmonary bypass procedures or hemodialysis. In this study, we proposed a unique microfluidic device for simultaneously measuring viscosity and flow rate of whole blood circulating in a complex fluidic network including a rat, a reservoir, a pinch valve, and a peristaltic pump. To demonstrate the proposed method, a twin-shaped microfluidic device, which is composed of two half-circular chambers, two side channels with multiple indicating channels, and one bridge channel, was carefully designed. Based on the microfluidic device, three sequential flow controls were applied to identify viscosity and flow rate of blood, with label-free and sensorless detection. The half-circular chamber was employed to achieve mechanical membrane compliance for flow stabilization in the microfluidic device. To quantify the effect of flow stabilization on flow fluctuations, a formula of pulsation index (PI) was analytically derived using a discrete fluidic circuit model. Using the PI formula, the time constant contributed by the half-circular chamber is estimated to be 8 s. Furthermore, flow fluctuations resulting from the peristaltic pumps are completely removed, especially under periodic flow conditions within short periods (T < 10 s). For performance demonstrations, the proposed method was applied to evaluate blood viscosity with respect to varying flow rate conditions [(a) known blood flow rate via a syringe pump, (b) unknown blood flow rate via a peristaltic pump]. As a result, the flow rate and viscosity of blood can be simultaneously measured with satisfactory accuracy. In addition, the proposed method was successfully applied to identify the viscosity of rat blood, which circulates in a
Statistical mechanics of complex networks
NASA Astrophysics Data System (ADS)
Albert, Réka; Barabási, Albert-László
2002-01-01
Complex networks describe a wide range of systems in nature and society. Frequently cited examples include the cell, a network of chemicals linked by chemical reactions, and the Internet, a network of routers and computers connected by physical links. While traditionally these systems have been modeled as random graphs, it is increasingly recognized that the topology and evolution of real networks are governed by robust organizing principles. This article reviews the recent advances in the field of complex networks, focusing on the statistical mechanics of network topology and dynamics. After reviewing the empirical data that motivated the recent interest in networks, the authors discuss the main models and analytical tools, covering random graphs, small-world and scale-free networks, the emerging theory of evolving networks, and the interplay between topology and the network's robustness against failures and attacks.
Coupled adaptive complex networks
NASA Astrophysics Data System (ADS)
Shai, S.; Dobson, S.
2013-04-01
Adaptive networks, which combine topological evolution of the network with dynamics on the network, are ubiquitous across disciplines. Examples include technical distribution networks such as road networks and the internet, natural and biological networks, and social science networks. These networks often interact with or depend upon other networks, resulting in coupled adaptive networks. In this paper we study susceptible-infected-susceptible (SIS) epidemic dynamics on coupled adaptive networks, where susceptible nodes are able to avoid contact with infected nodes by rewiring their intranetwork connections. However, infected nodes can pass the disease through internetwork connections, which do not change with time: The dependencies between the coupled networks remain constant. We develop an analytical formalism for these systems and validate it using extensive numerical simulation. We find that stability is increased by increasing the number of internetwork links, in the sense that the range of parameters over which both endemic and healthy states coexist (both states are reachable depending on the initial conditions) becomes smaller. Finally, we find a new stable state that does not appear in the case of a single adaptive network but only in the case of weakly coupled networks, in which the infection is endemic in one network but neither becomes endemic nor dies out in the other. Instead, it persists only at the nodes that are coupled to nodes in the other network through internetwork links. We speculate on the implications of these findings.
Approaching human language with complex networks
NASA Astrophysics Data System (ADS)
Cong, Jin; Liu, Haitao
2014-12-01
The interest in modeling and analyzing human language with complex networks is on the rise in recent years and a considerable body of research in this area has already been accumulated. We survey three major lines of linguistic research from the complex network approach: 1) characterization of human language as a multi-level system with complex network analysis; 2) linguistic typological research with the application of linguistic networks and their quantitative measures; and 3) relationships between the system-level complexity of human language (determined by the topology of linguistic networks) and microscopic linguistic (e.g., syntactic) features (as the traditional concern of linguistics). We show that the models and quantitative tools of complex networks, when exploited properly, can constitute an operational methodology for linguistic inquiry, which contributes to the understanding of human language and the development of linguistics. We conclude our review with suggestions for future linguistic research from the complex network approach: 1) relationships between the system-level complexity of human language and microscopic linguistic features; 2) expansion of research scope from the global properties to other levels of granularity of linguistic networks; and 3) combination of linguistic network analysis with other quantitative studies of language (such as quantitative linguistics).
Quantifying networks complexity from information geometry viewpoint
Felice, Domenico Mancini, Stefano; Pettini, Marco
2014-04-15
We consider a Gaussian statistical model whose parameter space is given by the variances of random variables. Underlying this model we identify networks by interpreting random variables as sitting on vertices and their correlations as weighted edges among vertices. We then associate to the parameter space a statistical manifold endowed with a Riemannian metric structure (that of Fisher-Rao). Going on, in analogy with the microcanonical definition of entropy in Statistical Mechanics, we introduce an entropic measure of networks complexity. We prove that it is invariant under networks isomorphism. Above all, considering networks as simplicial complexes, we evaluate this entropy on simplexes and find that it monotonically increases with their dimension.
ERIC Educational Resources Information Center
Doskey, Steven Craig
2014-01-01
This research presents an innovative means of gauging Systems Engineering effectiveness through a Systems Engineering Relative Effectiveness Index (SE REI) model. The SE REI model uses a Bayesian Belief Network to map causal relationships in government acquisitions of Complex Information Systems (CIS), enabling practitioners to identify and…
Quantization Effects on Complex Networks.
Wang, Ying; Wang, Lin; Yang, Wen; Wang, Xiaofan
2016-01-01
Weights of edges in many complex networks we constructed are quantized values of the real weights. To what extent does the quantization affect the properties of a network? In this work, quantization effects on network properties are investigated based on the spectrum of the corresponding Laplacian. In contrast to the intuition that larger quantization level always implies a better approximation of the quantized network to the original one, we find a ubiquitous periodic jumping phenomenon with peak-value decreasing in a power-law relationship in all the real-world weighted networks that we investigated. We supply theoretical analysis on the critical quantization level and the power laws. PMID:27226049
Quantization Effects on Complex Networks
NASA Astrophysics Data System (ADS)
Wang, Ying; Wang, Lin; Yang, Wen; Wang, Xiaofan
2016-05-01
Weights of edges in many complex networks we constructed are quantized values of the real weights. To what extent does the quantization affect the properties of a network? In this work, quantization effects on network properties are investigated based on the spectrum of the corresponding Laplacian. In contrast to the intuition that larger quantization level always implies a better approximation of the quantized network to the original one, we find a ubiquitous periodic jumping phenomenon with peak-value decreasing in a power-law relationship in all the real-world weighted networks that we investigated. We supply theoretical analysis on the critical quantization level and the power laws.
Quantization Effects on Complex Networks
Wang, Ying; Wang, Lin; Yang, Wen; Wang, Xiaofan
2016-01-01
Weights of edges in many complex networks we constructed are quantized values of the real weights. To what extent does the quantization affect the properties of a network? In this work, quantization effects on network properties are investigated based on the spectrum of the corresponding Laplacian. In contrast to the intuition that larger quantization level always implies a better approximation of the quantized network to the original one, we find a ubiquitous periodic jumping phenomenon with peak-value decreasing in a power-law relationship in all the real-world weighted networks that we investigated. We supply theoretical analysis on the critical quantization level and the power laws. PMID:27226049
Core percolation on complex networks.
Liu, Yang-Yu; Csóka, Endre; Zhou, Haijun; Pósfai, Márton
2012-11-16
We analytically solve the core percolation problem for complex networks with arbitrary degree distributions. We find that purely scale-free networks have no core for any degree exponents. We show that for undirected networks if core percolation occurs then it is continuous while for directed networks it is discontinuous (and hybrid) if the in- and out-degree distributions differ. We also find that core percolations on undirected and directed networks have completely different critical exponents associated with their critical singularities. PMID:23215509
Language Networks as Complex Systems
ERIC Educational Resources Information Center
Lee, Max Kueiming; Ou, Sheue-Jen
2008-01-01
Starting in the late eighties, with a growing discontent with analytical methods in science and the growing power of computers, researchers began to study complex systems such as living organisms, evolution of genes, biological systems, brain neural networks, epidemics, ecology, economy, social networks, etc. In the early nineties, the research…
The physics of communicability in complex networks
NASA Astrophysics Data System (ADS)
Estrada, Ernesto; Hatano, Naomichi; Benzi, Michele
2012-05-01
A fundamental problem in the study of complex networks is to provide quantitative measures of correlation and information flow between different parts of a system. To this end, several notions of communicability have been introduced and applied to a wide variety of real-world networks in recent years. Several such communicability functions are reviewed in this paper. It is emphasized that communication and correlation in networks can take place through many more routes than the shortest paths, a fact that may not have been sufficiently appreciated in previously proposed correlation measures. In contrast to these, the communicability measures reviewed in this paper are defined by taking into account all possible routes between two nodes, assigning smaller weights to longer ones. This point of view naturally leads to the definition of communicability in terms of matrix functions, such as the exponential, resolvent, and hyperbolic functions, in which the matrix argument is either the adjacency matrix or the graph Laplacian associated with the network. Considerable insight on communicability can be gained by modeling a network as a system of oscillators and deriving physical interpretations, both classical and quantum-mechanical, of various communicability functions. Applications of communicability measures to the analysis of complex systems are illustrated on a variety of biological, physical and social networks. The last part of the paper is devoted to a review of the notion of locality in complex networks and to computational aspects that by exploiting sparsity can greatly reduce the computational efforts for the calculation of communicability functions for large networks.
Wealth distribution on complex networks
NASA Astrophysics Data System (ADS)
Ichinomiya, Takashi
2012-12-01
We study the wealth distribution of the Bouchaud-Mézard model on complex networks. It is known from numerical simulations that this distribution depends on the topology of the network; however, no one has succeeded in explaining it. Using “adiabatic” and “independent” assumptions along with the central-limit theorem, we derive equations that determine the probability distribution function. The results are compared to those of simulations for various networks. We find good agreement between our theory and the simulations, except for the case of Watts-Strogatz networks with a low rewiring rate due to the breakdown of independent assumption.
Griffiths Phases on Complex Networks
NASA Astrophysics Data System (ADS)
Muñoz, Miguel A.; Juhász, Róbert; Castellano, Claudio; Ódor, Géza
2010-09-01
Quenched disorder is known to play a relevant role in dynamical processes and phase transitions. Its effects on the dynamics of complex networks have hardly been studied. Aimed at filling this gap, we analyze the contact process, i.e., the simplest propagation model, with quenched disorder on complex networks. We find Griffiths phases and other rare-region effects, leading rather generically to anomalously slow (algebraic, logarithmic, …) relaxation, on Erdős-Rényi networks. Similar effects are predicted to exist for other topologies with a finite percolation threshold. More surprisingly, we find that Griffiths phases can also emerge in the absence of quenched disorder, as a consequence of topological heterogeneity in networks with finite topological dimension. These results have a broad spectrum of implications for propagation phenomena and other dynamical processes on networks.
Heat diffusion: thermodynamic depth complexity of networks.
Escolano, Francisco; Hancock, Edwin R; Lozano, Miguel A
2012-03-01
In this paper we use the Birkhoff-von Neumann decomposition of the diffusion kernel to compute a polytopal measure of graph complexity. We decompose the diffusion kernel into a series of weighted Birkhoff combinations and compute the entropy associated with the weighting proportions (polytopal complexity). The maximum entropy Birkhoff combination can be expressed in terms of matrix permanents. This allows us to introduce a phase-transition principle that links our definition of polytopal complexity to the heat flowing through the network at a given diffusion time. The result is an efficiently computed complexity measure, which we refer to as flow complexity. Moreover, the flow complexity measure allows us to analyze graphs and networks in terms of the thermodynamic depth. We compare our method with three alternative methods described in the literature (Estrada's heterogeneity index, the Laplacian energy, and the von Neumann entropy). Our study is based on 217 protein-protein interaction (PPI) networks including histidine kinases from several species of bacteria. We find a correlation between structural complexity and phylogeny (more evolved species have statistically more complex PPIs). Although our methods outperform the alternatives, we find similarities with Estrada's heterogeneity index in terms of network size independence and predictive power. PMID:22587160
Heat diffusion: Thermodynamic depth complexity of networks
NASA Astrophysics Data System (ADS)
Escolano, Francisco; Hancock, Edwin R.; Lozano, Miguel A.
2012-03-01
In this paper we use the Birkhoff-von Neumann decomposition of the diffusion kernel to compute a polytopal measure of graph complexity. We decompose the diffusion kernel into a series of weighted Birkhoff combinations and compute the entropy associated with the weighting proportions (polytopal complexity). The maximum entropy Birkhoff combination can be expressed in terms of matrix permanents. This allows us to introduce a phase-transition principle that links our definition of polytopal complexity to the heat flowing through the network at a given diffusion time. The result is an efficiently computed complexity measure, which we refer to as flow complexity. Moreover, the flow complexity measure allows us to analyze graphs and networks in terms of the thermodynamic depth. We compare our method with three alternative methods described in the literature (Estrada's heterogeneity index, the Laplacian energy, and the von Neumann entropy). Our study is based on 217 protein-protein interaction (PPI) networks including histidine kinases from several species of bacteria. We find a correlation between structural complexity and phylogeny (more evolved species have statistically more complex PPIs). Although our methods outperform the alternatives, we find similarities with Estrada's heterogeneity index in terms of network size independence and predictive power.
Control efficacy of complex networks
Gao, Xin-Dong; Wang, Wen-Xu; Lai, Ying-Cheng
2016-01-01
Controlling complex networks has become a forefront research area in network science and engineering. Recent efforts have led to theoretical frameworks of controllability to fully control a network through steering a minimum set of driver nodes. However, in realistic situations not every node is accessible or can be externally driven, raising the fundamental issue of control efficacy: if driving signals are applied to an arbitrary subset of nodes, how many other nodes can be controlled? We develop a framework to determine the control efficacy for undirected networks of arbitrary topology. Mathematically, based on non-singular transformation, we prove a theorem to determine rigorously the control efficacy of the network and to identify the nodes that can be controlled for any given driver nodes. Physically, we develop the picture of diffusion that views the control process as a signal diffused from input signals to the set of controllable nodes. The combination of mathematical theory and physical reasoning allows us not only to determine the control efficacy for model complex networks and a large number of empirical networks, but also to uncover phenomena in network control, e.g., hub nodes in general possess lower control centrality than an average node in undirected networks. PMID:27324438
Control efficacy of complex networks
NASA Astrophysics Data System (ADS)
Gao, Xin-Dong; Wang, Wen-Xu; Lai, Ying-Cheng
2016-06-01
Controlling complex networks has become a forefront research area in network science and engineering. Recent efforts have led to theoretical frameworks of controllability to fully control a network through steering a minimum set of driver nodes. However, in realistic situations not every node is accessible or can be externally driven, raising the fundamental issue of control efficacy: if driving signals are applied to an arbitrary subset of nodes, how many other nodes can be controlled? We develop a framework to determine the control efficacy for undirected networks of arbitrary topology. Mathematically, based on non-singular transformation, we prove a theorem to determine rigorously the control efficacy of the network and to identify the nodes that can be controlled for any given driver nodes. Physically, we develop the picture of diffusion that views the control process as a signal diffused from input signals to the set of controllable nodes. The combination of mathematical theory and physical reasoning allows us not only to determine the control efficacy for model complex networks and a large number of empirical networks, but also to uncover phenomena in network control, e.g., hub nodes in general possess lower control centrality than an average node in undirected networks.
Control efficacy of complex networks.
Gao, Xin-Dong; Wang, Wen-Xu; Lai, Ying-Cheng
2016-01-01
Controlling complex networks has become a forefront research area in network science and engineering. Recent efforts have led to theoretical frameworks of controllability to fully control a network through steering a minimum set of driver nodes. However, in realistic situations not every node is accessible or can be externally driven, raising the fundamental issue of control efficacy: if driving signals are applied to an arbitrary subset of nodes, how many other nodes can be controlled? We develop a framework to determine the control efficacy for undirected networks of arbitrary topology. Mathematically, based on non-singular transformation, we prove a theorem to determine rigorously the control efficacy of the network and to identify the nodes that can be controlled for any given driver nodes. Physically, we develop the picture of diffusion that views the control process as a signal diffused from input signals to the set of controllable nodes. The combination of mathematical theory and physical reasoning allows us not only to determine the control efficacy for model complex networks and a large number of empirical networks, but also to uncover phenomena in network control, e.g., hub nodes in general possess lower control centrality than an average node in undirected networks. PMID:27324438
Information communication on complex networks
NASA Astrophysics Data System (ADS)
Igarashi, Akito; Kawamoto, Hiroki; Maruyama, Takahiro; Morioka, Atsushi; Naganuma, Yuki
2013-02-01
Since communication networks such as the Internet, which is regarded as a complex network, have recently become a huge scale and a lot of data pass through them, the improvement of packet routing strategies for transport is one of the most significant themes in the study of computer networks. It is especially important to find routing strategies which can bear as many traffic as possible without congestion in complex networks. First, using neural networks, we introduce a strategy for packet routing on complex networks, where path lengths and queue lengths in nodes are taken into account within a framework of statistical physics. Secondly, instead of using shortest paths, we propose efficient paths which avoid hubs, nodes with a great many degrees, on scale-free networks with a weight of each node. We improve the heuristic algorithm proposed by Danila et. al. which optimizes step by step routing properties on congestion by using the information of betweenness, the probability of paths passing through a node in all optimal paths which are defined according to a rule, and mitigates the congestion. We confirm the new heuristic algorithm which balances traffic on networks by achieving minimization of the maximum betweenness in much smaller number of iteration steps. Finally, We model virus spreading and data transfer on peer-to-peer (P2P) networks. Using mean-field approximation, we obtain an analytical formulation and emulate virus spreading on the network and compare the results with those of simulation. Moreover, we investigate the mitigation of information traffic congestion in the P2P networks.
Spreading dynamics in complex networks
NASA Astrophysics Data System (ADS)
Pei, Sen; Makse, Hernán A.
2013-12-01
Searching for influential spreaders in complex networks is an issue of great significance for applications across various domains, ranging from epidemic control, innovation diffusion, viral marketing, and social movement to idea propagation. In this paper, we first display some of the most important theoretical models that describe spreading processes, and then discuss the problem of locating both the individual and multiple influential spreaders respectively. Recent approaches in these two topics are presented. For the identification of privileged single spreaders, we summarize several widely used centralities, such as degree, betweenness centrality, PageRank, k-shell, etc. We investigate the empirical diffusion data in a large scale online social community—LiveJournal. With this extensive dataset, we find that various measures can convey very distinct information of nodes. Of all the users in the LiveJournal social network, only a small fraction of them are involved in spreading. For the spreading processes in LiveJournal, while degree can locate nodes participating in information diffusion with higher probability, k-shell is more effective in finding nodes with a large influence. Our results should provide useful information for designing efficient spreading strategies in reality.
Dynamic and interacting complex networks
NASA Astrophysics Data System (ADS)
Dickison, Mark E.
This thesis employs methods of statistical mechanics and numerical simulations to study some aspects of dynamic and interacting complex networks. The mapping of various social and physical phenomena to complex networks has been a rich field in the past few decades. Subjects as broad as petroleum engineering, scientific collaborations, and the structure of the internet have all been analyzed in a network physics context, with useful and universal results. In the first chapter we introduce basic concepts in networks, including the two types of network configurations that are studied and the statistical physics and epidemiological models that form the framework of the network research, as well as covering various previously-derived results in network theory that are used in the work in the following chapters. In the second chapter we introduce a model for dynamic networks, where the links or the strengths of the links change over time. We solve the model by mapping dynamic networks to the problem of directed percolation, where the direction corresponds to the time evolution of the network. We show that the dynamic network undergoes a percolation phase transition at a critical concentration pc, that decreases with the rate r at which the network links are changed. The behavior near criticality is universal and independent of r. We find that for dynamic random networks fundamental laws are changed: i) The size of the giant component at criticality scales with the network size N for all values of r, rather than as N2/3 in static network, ii) In the presence of a broad distribution of disorder, the optimal path length between two nodes in a dynamic network scales as N1/2, compared to N1/3 in a static network. The third chapter consists of a study of the effect of quarantine on the propagation of epidemics on an adaptive network of social contacts. For this purpose, we analyze the susceptible-infected-recovered model in the presence of quarantine, where susceptible
Porous Soil as Complex Network
NASA Astrophysics Data System (ADS)
Benito, R. M.; Santiago, A.; Cárdenas, J. P.; Tarquis, A. M.; Borondo, F.; Losada, J. C.
2009-04-01
We present a complex network model based on a heterogeneous preferential attachment scheme [1,2] to quantify the structure of porous soils [3]. Under this perspective pores are represented by nodes and the space for the flow of fluids between them are represented by links. Pore properties such as position and size are described by fixed states in a metric space, while an affinity function is introduced to bias the attachment probabilities of links according to these properties. We perform an analytical and numerical study of the degree distributions in the soil model and show that under reasonable conditions all the model variants yield a multiscaling behavior in the connectivity degrees, leaving a empirically testable signature of heterogeneity in the topology of pore networks. References [1] A. Santiago and R. M. Benito, "Emergence of multiscaling in heterogeneous complex networks". Int. J. Mod. Phys. C 18, 1591 (2007). [2] A. Santiago and R. M. Benito, "An extended formalism for preferential attachment in heterogeneous complex networks". Europhys. Lett. 82, 58004 (2008). [3] A. Santiago, R. M. Benito, J. P. Cárdenas, J. C. Losada, A. M. Tarquis and F. Borondo, "Multiscaling of porous soils as heterogeneous complex networks". Nonl. Proc. Geophys. 15, 1-10 (2008).
Complex Networks in Psychological Models
NASA Astrophysics Data System (ADS)
Wedemann, R. S.; Carvalho, L. S. A. V. D.; Donangelo, R.
We develop schematic, self-organizing, neural-network models to describe mechanisms associated with mental processes, by a neurocomputational substrate. These models are examples of real world complex networks with interesting general topological structures. Considering dopaminergic signal-to-noise neuronal modulation in the central nervous system, we propose neural network models to explain development of cortical map structure and dynamics of memory access, and unify different mental processes into a single neurocomputational substrate. Based on our neural network models, neurotic behavior may be understood as an associative memory process in the brain, and the linguistic, symbolic associative process involved in psychoanalytic working-through can be mapped onto a corresponding process of reconfiguration of the neural network. The models are illustrated through computer simulations, where we varied dopaminergic modulation and observed the self-organizing emergent patterns at the resulting semantic map, interpreting them as different manifestations of mental functioning, from psychotic through to normal and neurotic behavior, and creativity.
Robustness Elasticity in Complex Networks
Matisziw, Timothy C.; Grubesic, Tony H.; Guo, Junyu
2012-01-01
Network robustness refers to a network’s resilience to stress or damage. Given that most networks are inherently dynamic, with changing topology, loads, and operational states, their robustness is also likely subject to change. However, in most analyses of network structure, it is assumed that interaction among nodes has no effect on robustness. To investigate the hypothesis that network robustness is not sensitive or elastic to the level of interaction (or flow) among network nodes, this paper explores the impacts of network disruption, namely arc deletion, over a temporal sequence of observed nodal interactions for a large Internet backbone system. In particular, a mathematical programming approach is used to identify exact bounds on robustness to arc deletion for each epoch of nodal interaction. Elasticity of the identified bounds relative to the magnitude of arc deletion is assessed. Results indicate that system robustness can be highly elastic to spatial and temporal variations in nodal interactions within complex systems. Further, the presence of this elasticity provides evidence that a failure to account for nodal interaction can confound characterizations of complex networked systems. PMID:22808060
Statistical mechanics of complex networks
NASA Astrophysics Data System (ADS)
Waclaw, B.
2007-04-01
The science of complex networks is a new interdisciplinary branch of science which has arisen recently on the interface of physics, biology, social and computer sciences, and others. Its main goal is to discover general laws governing the creation and growth as well as processes taking place on networks, like e.g. the Internet, transportation or neural networks. It turned out that most real-world networks cannot be simply reduced to a compound of some individual components. Fortunately, the statistical mechanics, being one of pillars of modern physics, provides us with a very powerful set of tools and methods for describing and understanding these systems. In this thesis, we would like to present a consistent approach to complex networks based on statistical mechanics, with the central role played by the concept of statistical ensemble of networks. We show how to construct such a theory and present some practical problems where it can be applied. Among them, we pay attention to the problem of finite-size corrections and the dynamics of a simple model of mass transport on networks.
Dynamic information routing in complex networks
Kirst, Christoph; Timme, Marc; Battaglia, Demian
2016-01-01
Flexible information routing fundamentally underlies the function of many biological and artificial networks. Yet, how such systems may specifically communicate and dynamically route information is not well understood. Here we identify a generic mechanism to route information on top of collective dynamical reference states in complex networks. Switching between collective dynamics induces flexible reorganization of information sharing and routing patterns, as quantified by delayed mutual information and transfer entropy measures between activities of a network's units. We demonstrate the power of this mechanism specifically for oscillatory dynamics and analyse how individual unit properties, the network topology and external inputs co-act to systematically organize information routing. For multi-scale, modular architectures, we resolve routing patterns at all levels. Interestingly, local interventions within one sub-network may remotely determine nonlocal network-wide communication. These results help understanding and designing information routing patterns across systems where collective dynamics co-occurs with a communication function. PMID:27067257
Dynamic information routing in complex networks.
Kirst, Christoph; Timme, Marc; Battaglia, Demian
2016-01-01
Flexible information routing fundamentally underlies the function of many biological and artificial networks. Yet, how such systems may specifically communicate and dynamically route information is not well understood. Here we identify a generic mechanism to route information on top of collective dynamical reference states in complex networks. Switching between collective dynamics induces flexible reorganization of information sharing and routing patterns, as quantified by delayed mutual information and transfer entropy measures between activities of a network's units. We demonstrate the power of this mechanism specifically for oscillatory dynamics and analyse how individual unit properties, the network topology and external inputs co-act to systematically organize information routing. For multi-scale, modular architectures, we resolve routing patterns at all levels. Interestingly, local interventions within one sub-network may remotely determine nonlocal network-wide communication. These results help understanding and designing information routing patterns across systems where collective dynamics co-occurs with a communication function. PMID:27067257
Dynamic information routing in complex networks
NASA Astrophysics Data System (ADS)
Kirst, Christoph; Timme, Marc; Battaglia, Demian
2016-04-01
Flexible information routing fundamentally underlies the function of many biological and artificial networks. Yet, how such systems may specifically communicate and dynamically route information is not well understood. Here we identify a generic mechanism to route information on top of collective dynamical reference states in complex networks. Switching between collective dynamics induces flexible reorganization of information sharing and routing patterns, as quantified by delayed mutual information and transfer entropy measures between activities of a network's units. We demonstrate the power of this mechanism specifically for oscillatory dynamics and analyse how individual unit properties, the network topology and external inputs co-act to systematically organize information routing. For multi-scale, modular architectures, we resolve routing patterns at all levels. Interestingly, local interventions within one sub-network may remotely determine nonlocal network-wide communication. These results help understanding and designing information routing patterns across systems where collective dynamics co-occurs with a communication function.
Information filtering in complex weighted networks
NASA Astrophysics Data System (ADS)
Radicchi, Filippo; Ramasco, José J.; Fortunato, Santo
2011-04-01
Many systems in nature, society, and technology can be described as networks, where the vertices are the system’s elements, and edges between vertices indicate the interactions between the corresponding elements. Edges may be weighted if the interaction strength is measurable. However, the full network information is often redundant because tools and techniques from network analysis do not work or become very inefficient if the network is too dense, and some weights may just reflect measurement errors and need to be be discarded. Moreover, since weight distributions in many complex weighted networks are broad, most of the weight is concentrated among a small fraction of all edges. It is then crucial to properly detect relevant edges. Simple thresholding would leave only the largest weights, disrupting the multiscale structure of the system, which is at the basis of the structure of complex networks and ought to be kept. In this paper we propose a weight-filtering technique based on a global null model [Global Statistical Significance (GloSS) filter], keeping both the weight distribution and the full topological structure of the network. The method correctly quantifies the statistical significance of weights assigned independently to the edges from a given distribution. Applications to real networks reveal that the GloSS filter is indeed able to identify relevant connections between vertices.
Quantum physics and complex networks
NASA Astrophysics Data System (ADS)
Biamonte, Jacob
2014-03-01
There is a widely used and successful theory of ``chemical reaction networks,'' which provides a framework describing systems governed by mass action kinetics. Computer science and population biology use the same ideas under a different name: ``stochastic Petri nets.'' But if we look at these theories from the perspective of quantum theory, they turn out to involve creation and annihilation operators, coherent states and other well-known ideas--yet in a context where probabilities replace amplitudes. I will explain this connection as part of a detailed analogy between quantum mechanics and stochastic mechanics which we've produced several results on recently, including the recent analytical results uniting quantum physics and complex networks. Our general idea is about merging concepts from quantum physics and complex network theory to provide a bidirectional bridge between both disciplines. Support is acknowledged from the Foundational Questions Institute (FQXi) and the Compagnia di San Paolo Foundation.
Complexity matching in neural networks
NASA Astrophysics Data System (ADS)
Usefie Mafahim, Javad; Lambert, David; Zare, Marzieh; Grigolini, Paolo
2015-01-01
In the wide literature on the brain and neural network dynamics the notion of criticality is being adopted by an increasing number of researchers, with no general agreement on its theoretical definition, but with consensus that criticality makes the brain very sensitive to external stimuli. We adopt the complexity matching principle that the maximal efficiency of communication between two complex networks is realized when both of them are at criticality. We use this principle to establish the value of the neuronal interaction strength at which criticality occurs, yielding a perfect agreement with the adoption of temporal complexity as criticality indicator. The emergence of a scale-free distribution of avalanche size is proved to occur in a supercritical regime. We use an integrate-and-fire model where the randomness of each neuron is only due to the random choice of a new initial condition after firing. The new model shares with that proposed by Izikevich the property of generating excessive periodicity, and with it the annihilation of temporal complexity at supercritical values of the interaction strength. We find that the concentration of inhibitory links can be used as a control parameter and that for a sufficiently large concentration of inhibitory links criticality is recovered again. Finally, we show that the response of a neural network at criticality to a harmonic stimulus is very weak, in accordance with the complexity matching principle.
Multilevel Complex Networks and Systems
NASA Astrophysics Data System (ADS)
Caldarelli, Guido
2014-03-01
Network theory has been a powerful tool to model isolated complex systems. However, the classical approach does not take into account the interactions often present among different systems. Hence, the scientific community is nowadays concentrating the efforts on the foundations of new mathematical tools for understanding what happens when multiple networks interact. The case of economic and financial networks represents a paramount example of multilevel networks. In the case of trade, trade among countries the different levels can be described by the different granularity of the trading relations. Indeed, we have now data from the scale of consumers to that of the country level. In the case of financial institutions, we have a variety of levels at the same scale. For example one bank can appear in the interbank networks, ownership network and cds networks in which the same institution can take place. In both cases the systemically important vertices need to be determined by different procedures of centrality definition and community detection. In this talk I will present some specific cases of study related to these topics and present the regularities found. Acknowledged support from EU FET Project ``Multiplex'' 317532.
Synchronization in complex dynamical networks coupled with complex chaotic system
NASA Astrophysics Data System (ADS)
Wei, Qiang; Xie, Cheng-Jun; Wang, Bo
2015-11-01
This paper investigates synchronization in complex dynamical networks with time delay and perturbation. The node of complex dynamical networks is composed of complex chaotic system. A complex feedback controller is designed to realize different component of complex state variable synchronize up to different scaling complex function when complex dynamical networks realize synchronization. The synchronization scaling function is changed from real field to complex field. Synchronization in complex dynamical networks with constant delay and time-varying coupling delay are investigated, respectively. Numerical simulations show the effectiveness of the proposed method.
Epidemic processes in complex networks
NASA Astrophysics Data System (ADS)
Pastor-Satorras, Romualdo; Castellano, Claudio; Van Mieghem, Piet; Vespignani, Alessandro
2015-07-01
In recent years the research community has accumulated overwhelming evidence for the emergence of complex and heterogeneous connectivity patterns in a wide range of biological and sociotechnical systems. The complex properties of real-world networks have a profound impact on the behavior of equilibrium and nonequilibrium phenomena occurring in various systems, and the study of epidemic spreading is central to our understanding of the unfolding of dynamical processes in complex networks. The theoretical analysis of epidemic spreading in heterogeneous networks requires the development of novel analytical frameworks, and it has produced results of conceptual and practical relevance. A coherent and comprehensive review of the vast research activity concerning epidemic processes is presented, detailing the successful theoretical approaches as well as making their limits and assumptions clear. Physicists, mathematicians, epidemiologists, computer, and social scientists share a common interest in studying epidemic spreading and rely on similar models for the description of the diffusion of pathogens, knowledge, and innovation. For this reason, while focusing on the main results and the paradigmatic models in infectious disease modeling, the major results concerning generalized social contagion processes are also presented. Finally, the research activity at the forefront in the study of epidemic spreading in coevolving, coupled, and time-varying networks is reported.
Competitive dynamics on complex networks.
Zhao, Jiuhua; Liu, Qipeng; Wang, Xiaofan
2014-01-01
We consider a dynamical network model in which two competitors have fixed and different states, and each normal agent adjusts its state according to a distributed consensus protocol. The state of each normal agent converges to a steady value which is a convex combination of the competitors' states, and is independent of the initial states of agents. This implies that the competition result is fully determined by the network structure and positions of competitors in the network. We compute an Influence Matrix (IM) in which each element characterizing the influence of an agent on another agent in the network. We use the IM to predict the bias of each normal agent and thus predict which competitor will win. Furthermore, we compare the IM criterion with seven node centrality measures to predict the winner. We find that the competitor with higher Katz Centrality in an undirected network or higher PageRank in a directed network is most likely to be the winner. These findings may shed new light on the role of network structure in competition and to what extent could competitors adjust network structure so as to win the competition. PMID:25068622
Competitive Dynamics on Complex Networks
NASA Astrophysics Data System (ADS)
Zhao, Jiuhua; Liu, Qipeng; Wang, Xiaofan
2014-07-01
We consider a dynamical network model in which two competitors have fixed and different states, and each normal agent adjusts its state according to a distributed consensus protocol. The state of each normal agent converges to a steady value which is a convex combination of the competitors' states, and is independent of the initial states of agents. This implies that the competition result is fully determined by the network structure and positions of competitors in the network. We compute an Influence Matrix (IM) in which each element characterizing the influence of an agent on another agent in the network. We use the IM to predict the bias of each normal agent and thus predict which competitor will win. Furthermore, we compare the IM criterion with seven node centrality measures to predict the winner. We find that the competitor with higher Katz Centrality in an undirected network or higher PageRank in a directed network is most likely to be the winner. These findings may shed new light on the role of network structure in competition and to what extent could competitors adjust network structure so as to win the competition.
Andrianov, V.R.; Petrov, A.P.
1985-04-01
This paper describes the Profil'-1 hydroacoustic measuring complex. The complex provides documentary information on the bottom profile of reservoirs, the configuration and geometric dimensions of underwater trenches, the spatial position of pipes in uncovered or washedout trenches, the thickness of a layer covering underwater pipes, etc. The complex can also be used to solve other industrial problems such as hydraulic exploration and searching for sunken objects. The Profil'-1 complex is designed for use on board small craft under field conditions with periodic transportation from storage bases to the operating location and back. The complex uses an echo-pulse method for determining the distance and coordinates of objects with the aid of an ultrasonic transceiver in an aqueous medium. Structurally, the complex consists of four main units: a BA-1 vertical sounding antenna unit; a BAS-1 antenna scanning unit; a BFOS-1 signal shaping and processing unit, and a BR-1 recording unit. Use of the complex in pipeline construction and the oil and gas industry will provide a considerable economic gain by reducing the number of diver inspections of underwater pipelines.
Traffic gridlock on complex networks
NASA Astrophysics Data System (ADS)
Mendes, G. A.; da Silva, L. R.; Herrmann, H. J.
2012-01-01
Here we study how a traffic jam spreads on complex networks when driven by an increasing flux between certain initial and final points. For that purpose, we developed two new traffic models based on vehicular traffic and applied them on the Apollonian network and the Swiss road network. The first model is an electrical analog, using ohmic and non-ohmic resistors which is a classical approach in Physics while the second one which we call the herding model, is based on human driving behavior. For both models, we study the sequence of clogged roads up to the traffic gridlock and display the fragilities of the network. In the electrical model, by increasing the external potential, resistors burn out, as the voltage drop between the ends increases above a certain threshold. Analyzing both models, we observed some power-law functions that occur only near a traffic gridlock as well as the dependence on topological features of the network and influence on flux and the robustness in Apollonian networks of different generations.
Complex network classification using partially self-avoiding deterministic walks.
Gonçalves, Wesley Nunes; Martinez, Alexandre Souto; Bruno, Odemir Martinez
2012-09-01
Complex networks have attracted increasing interest from various fields of science. It has been demonstrated that each complex network model presents specific topological structures which characterize its connectivity and dynamics. Complex network classification relies on the use of representative measurements that describe topological structures. Although there are a large number of measurements, most of them are correlated. To overcome this limitation, this paper presents a new measurement for complex network classification based on partially self-avoiding walks. We validate the measurement on a data set composed by 40000 complex networks of four well-known models. Our results indicate that the proposed measurement improves correct classification of networks compared to the traditional ones. PMID:23020478
Blockmodeling techniques for complex networks
NASA Astrophysics Data System (ADS)
Ball, Brian Joseph
The class of network models known as stochastic blockmodels has recently been gaining popularity. In this dissertation, we present new work that uses blockmodels to answer questions about networks. We create a blockmodel based on the idea of link communities, which naturally gives rise to overlapping vertex communities. We derive a fast and accurate algorithm to fit the model to networks. This model can be related to another blockmodel, which allows the method to efficiently find nonoverlapping communities as well. We then create a heuristic based on the link community model whose use is to find the correct number of communities in a network. The heuristic is based on intuitive corrections to likelihood ratio tests. It does a good job finding the correct number of communities in both real networks and synthetic networks generated from the link communities model. Two commonly studied types of networks are citation networks, where research papers cite other papers, and coauthorship networks, where authors are connected if they've written a paper together. We study a multi-modal network from a large dataset of Physics publications that is the combination of the two, allowing for directed links between papers as citations, and an undirected edge between a scientist and a paper if they helped to write it. This allows for new insights on the relation between social interaction and scientific production. We also have the publication dates of papers, which lets us track our measures over time. Finally, we create a stochastic model for ranking vertices in a semi-directed network. The probability of connection between two vertices depends on the difference of their ranks. When this model is fit to high school friendship networks, the ranks appear to correspond with a measure of social status. Students have reciprocated and some unreciprocated edges with other students of closely similar rank that correspond to true friendship, and claim an aspirational friendship with a much
Controlling centrality in complex networks
Nicosia, V.; Criado, R.; Romance, M.; Russo, G.; Latora, V.
2012-01-01
Spectral centrality measures allow to identify influential individuals in social groups, to rank Web pages by popularity, and even to determine the impact of scientific researches. The centrality score of a node within a network crucially depends on the entire pattern of connections, so that the usual approach is to compute node centralities once the network structure is assigned. We face here with the inverse problem, that is, we study how to modify the centrality scores of the nodes by acting on the structure of a given network. We show that there exist particular subsets of nodes, called controlling sets, which can assign any prescribed set of centrality values to all the nodes of a graph, by cooperatively tuning the weights of their out-going links. We found that many large networks from the real world have surprisingly small controlling sets, containing even less than 5 – 10% of the nodes. PMID:22355732
Viral quasispecies complexity measures.
Gregori, Josep; Perales, Celia; Rodriguez-Frias, Francisco; Esteban, Juan I; Quer, Josep; Domingo, Esteban
2016-06-01
Mutant spectrum dynamics (changes in the related mutants that compose viral populations) has a decisive impact on virus behavior. The several platforms of next generation sequencing (NGS) to study viral quasispecies offer a magnifying glass to study viral quasispecies complexity. Several parameters are available to quantify the complexity of mutant spectra, but they have limitations. Here we critically evaluate the information provided by several population diversity indices, and we propose the introduction of some new ones used in ecology. In particular we make a distinction between incidence, abundance and function measures of viral quasispecies composition. We suggest a multidimensional approach (complementary information contributed by adequately chosen indices), propose some guidelines, and illustrate the use of indices with a simple example. We apply the indices to three clinical samples of hepatitis C virus that display different population heterogeneity. Areas of virus biology in which population complexity plays a role are discussed. PMID:27060566
Network representations of immune system complexity
Subramanian, Naeha; Torabi-Parizi, Parizad; Gottschalk, Rachel A.; Germain, Ronald N.; Dutta, Bhaskar
2015-01-01
The mammalian immune system is a dynamic multi-scale system composed of a hierarchically organized set of molecular, cellular and organismal networks that act in concert to promote effective host defense. These networks range from those involving gene regulatory and protein-protein interactions underlying intracellular signaling pathways and single cell responses to increasingly complex networks of in vivo cellular interaction, positioning and migration that determine the overall immune response of an organism. Immunity is thus not the product of simple signaling events but rather non-linear behaviors arising from dynamic, feedback-regulated interactions among many components. One of the major goals of systems immunology is to quantitatively measure these complex multi-scale spatial and temporal interactions, permitting development of computational models that can be used to predict responses to perturbation. Recent technological advances permit collection of comprehensive datasets at multiple molecular and cellular levels while advances in network biology support representation of the relationships of components at each level as physical or functional interaction networks. The latter facilitate effective visualization of patterns and recognition of emergent properties arising from the many interactions of genes, molecules, and cells of the immune system. We illustrate the power of integrating ‘omics’ and network modeling approaches for unbiased reconstruction of signaling and transcriptional networks with a focus on applications involving the innate immune system. We further discuss future possibilities for reconstruction of increasingly complex cellular and organism-level networks and development of sophisticated computational tools for prediction of emergent immune behavior arising from the concerted action of these networks. PMID:25625853
Network representations of immune system complexity.
Subramanian, Naeha; Torabi-Parizi, Parizad; Gottschalk, Rachel A; Germain, Ronald N; Dutta, Bhaskar
2015-01-01
The mammalian immune system is a dynamic multiscale system composed of a hierarchically organized set of molecular, cellular, and organismal networks that act in concert to promote effective host defense. These networks range from those involving gene regulatory and protein-protein interactions underlying intracellular signaling pathways and single-cell responses to increasingly complex networks of in vivo cellular interaction, positioning, and migration that determine the overall immune response of an organism. Immunity is thus not the product of simple signaling events but rather nonlinear behaviors arising from dynamic, feedback-regulated interactions among many components. One of the major goals of systems immunology is to quantitatively measure these complex multiscale spatial and temporal interactions, permitting development of computational models that can be used to predict responses to perturbation. Recent technological advances permit collection of comprehensive datasets at multiple molecular and cellular levels, while advances in network biology support representation of the relationships of components at each level as physical or functional interaction networks. The latter facilitate effective visualization of patterns and recognition of emergent properties arising from the many interactions of genes, molecules, and cells of the immune system. We illustrate the power of integrating 'omics' and network modeling approaches for unbiased reconstruction of signaling and transcriptional networks with a focus on applications involving the innate immune system. We further discuss future possibilities for reconstruction of increasingly complex cellular- and organism-level networks and development of sophisticated computational tools for prediction of emergent immune behavior arising from the concerted action of these networks. PMID:25625853
Factors Determining Nestedness in Complex Networks
Jonhson, Samuel; Domínguez-García, Virginia; Muñoz, Miguel A.
2013-01-01
Understanding the causes and effects of network structural features is a key task in deciphering complex systems. In this context, the property of network nestedness has aroused a fair amount of interest as regards ecological networks. Indeed, Bastolla et al. introduced a simple measure of network nestedness which opened the door to analytical understanding, allowing them to conclude that biodiversity is strongly enhanced in highly nested mutualistic networks. Here, we suggest a slightly refined version of such a measure of nestedness and study how it is influenced by the most basic structural properties of networks, such as degree distribution and degree-degree correlations (i.e. assortativity). We find that most of the empirically found nestedness stems from heterogeneity in the degree distribution. Once such an influence has been discounted – as a second factor – we find that nestedness is strongly correlated with disassortativity and hence – as random networks have been recently found to be naturally disassortative – they also tend to be naturally nested just as the result of chance. PMID:24069264
Complex Networks and Critical Infrastructures
NASA Astrophysics Data System (ADS)
Setola, Roberto; de Porcellinis, Stefano
The term “Critical Infrastructures” indicates all those technological infrastructures such as: electric grids, telecommunication networks, railways, healthcare systems, financial circuits, etc. that are more and more relevant for the welfare of our countries. Each one of these infrastructures is a complex, highly non-linear, geographically dispersed cluster of systems, that interact with their human owners, operators, users and with the other infrastructures. Their augmented relevance and the actual political and technological scenarios, which have increased their exposition to accidental failure and deliberate attacks, demand for different and innovative protection strategies (generally indicate as CIP - Critical Infrastructure Protection). To this end it is mandatory to understand the mechanisms that regulate the dynamic of these infrastructures. In this framework, an interesting approach is those provided by the complex networks. In this paper we illustrate some results achieved considering structural and functional properties of the corresponding topological networks both when each infrastructure is assumed as an autonomous system and when we take into account also the dependencies existing among the different infrastructures.
Fuzzy Entropy Method for Quantifying Supply Chain Networks Complexity
NASA Astrophysics Data System (ADS)
Zhang, Jihui; Xu, Junqin
Supply chain is a special kind of complex network. Its complexity and uncertainty makes it very difficult to control and manage. Supply chains are faced with a rising complexity of products, structures, and processes. Because of the strong link between a supply chain’s complexity and its efficiency the supply chain complexity management becomes a major challenge of today’s business management. The aim of this paper is to quantify the complexity and organization level of an industrial network working towards the development of a ‘Supply Chain Network Analysis’ (SCNA). By measuring flows of goods and interaction costs between different sectors of activity within the supply chain borders, a network of flows is built and successively investigated by network analysis. The result of this study shows that our approach can provide an interesting conceptual perspective in which the modern supply network can be framed, and that network analysis can handle these issues in practice.
Sampling from complex networks using distributed learning automata
NASA Astrophysics Data System (ADS)
Rezvanian, Alireza; Rahmati, Mohammad; Meybodi, Mohammad Reza
2014-02-01
A complex network provides a framework for modeling many real-world phenomena in the form of a network. In general, a complex network is considered as a graph of real world phenomena such as biological networks, ecological networks, technological networks, information networks and particularly social networks. Recently, major studies are reported for the characterization of social networks due to a growing trend in analysis of online social networks as dynamic complex large-scale graphs. Due to the large scale and limited access of real networks, the network model is characterized using an appropriate part of a network by sampling approaches. In this paper, a new sampling algorithm based on distributed learning automata has been proposed for sampling from complex networks. In the proposed algorithm, a set of distributed learning automata cooperate with each other in order to take appropriate samples from the given network. To investigate the performance of the proposed algorithm, several simulation experiments are conducted on well-known complex networks. Experimental results are compared with several sampling methods in terms of different measures. The experimental results demonstrate the superiority of the proposed algorithm over the others.
Kinetic analysis of complex metabolic networks
Stephanopoulos, G.
1996-12-31
A new methodology is presented for the analysis of complex metabolic networks with the goal of metabolite overproduction. The objective is to locate a small number of reaction steps in a network that have maximum impact on network flux amplification and whose rate can also be increased without functional network derangement. This method extends the concepts of Metabolic Control Analysis to groups of reactions and offers the means for calculating group control coefficients as measures of the control exercised by groups of reactions on the overall network fluxes and intracellular metabolite pools. It is further demonstrated that the optimal strategy for the effective increase of network fluxes, while maintaining an uninterrupted supply of intermediate metabolites, is through the coordinated amplification of multiple (as opposed to a single) reaction steps. Satisfying this requirement invokes the concept of the concentration control to coefficient, which emerges as a critical parameter in the identification of feasible enzymatic modifications with maximal impact on the network flux. A case study of aromatic aminoacid production is provided to illustrate these concepts.
The Correlation Fractal Dimension of Complex Networks
NASA Astrophysics Data System (ADS)
Wang, Xingyuan; Liu, Zhenzhen; Wang, Mogei
2013-05-01
The fractality of complex networks is studied by estimating the correlation dimensions of the networks. Comparing with the previous algorithms of estimating the box dimension, our algorithm achieves a significant reduction in time complexity. For four benchmark cases tested, that is, the Escherichia coli (E. Coli) metabolic network, the Homo sapiens protein interaction network (H. Sapiens PIN), the Saccharomyces cerevisiae protein interaction network (S. Cerevisiae PIN) and the World Wide Web (WWW), experiments are provided to demonstrate the validity of our algorithm.
Minimum complexity echo state network.
Rodan, Ali; Tino, Peter
2011-01-01
Reservoir computing (RC) refers to a new class of state-space models with a fixed state transition structure (the reservoir) and an adaptable readout form the state space. The reservoir is supposed to be sufficiently complex so as to capture a large number of features of the input stream that can be exploited by the reservoir-to-output readout mapping. The field of RC has been growing rapidly with many successful applications. However, RC has been criticized for not being principled enough. Reservoir construction is largely driven by a series of randomized model-building stages, with both researchers and practitioners having to rely on a series of trials and errors. To initialize a systematic study of the field, we concentrate on one of the most popular classes of RC methods, namely echo state network, and ask: What is the minimal complexity of reservoir construction for obtaining competitive models and what is the memory capacity (MC) of such simplified reservoirs? On a number of widely used time series benchmarks of different origin and characteristics, as well as by conducting a theoretical analysis we show that a simple deterministically constructed cycle reservoir is comparable to the standard echo state network methodology. The (short-term) MC of linear cyclic reservoirs can be made arbitrarily close to the proved optimal value. PMID:21075721
Controlling synchronous patterns in complex networks
NASA Astrophysics Data System (ADS)
Lin, Weijie; Fan, Huawei; Wang, Ying; Ying, Heping; Wang, Xingang
2016-04-01
Although the set of permutation symmetries of a complex network could be very large, few of them give rise to stable synchronous patterns. Here we present a general framework and develop techniques for controlling synchronization patterns in complex network of coupled chaotic oscillators. Specifically, according to the network permutation symmetry, we design a small-size and weighted network, namely the control network, and use it to control the large-size complex network by means of pinning coupling. We argue mathematically that for any of the network symmetries, there always exists a critical pinning strength beyond which the unstable synchronous pattern associated to this symmetry can be stabilized. The feasibility of the control method is verified by numerical simulations of both artificial and real-world networks and demonstrated experimentally in systems of coupled chaotic circuits. Our studies show the controllability of synchronous patterns in complex networks of coupled chaotic oscillators.
Robustness and structure of complex networks
NASA Astrophysics Data System (ADS)
Shao, Shuai
This dissertation covers the two major parts of my PhD research on statistical physics and complex networks: i) modeling a new type of attack -- localized attack, and investigating robustness of complex networks under this type of attack; ii) discovering the clustering structure in complex networks and its influence on the robustness of coupled networks. Complex networks appear in every aspect of our daily life and are widely studied in Physics, Mathematics, Biology, and Computer Science. One important property of complex networks is their robustness under attacks, which depends crucially on the nature of attacks and the structure of the networks themselves. Previous studies have focused on two types of attack: random attack and targeted attack, which, however, are insufficient to describe many real-world damages. Here we propose a new type of attack -- localized attack, and study the robustness of complex networks under this type of attack, both analytically and via simulation. On the other hand, we also study the clustering structure in the network, and its influence on the robustness of a complex network system. In the first part, we propose a theoretical framework to study the robustness of complex networks under localized attack based on percolation theory and generating function method. We investigate the percolation properties, including the critical threshold of the phase transition pc and the size of the giant component Pinfinity. We compare localized attack with random attack and find that while random regular (RR) networks are more robust against localized attack, Erdoḧs-Renyi (ER) networks are equally robust under both types of attacks. As for scale-free (SF) networks, their robustness depends crucially on the degree exponent lambda. The simulation results show perfect agreement with theoretical predictions. We also test our model on two real-world networks: a peer-to-peer computer network and an airline network, and find that the real-world networks
NASA Astrophysics Data System (ADS)
Guittienne, Ph; Jacquier, R.; Howling, A. A.; Furno, I.
2015-12-01
Measurements and analysis of a radio-frequency planar antenna are presented for applications in inductively-coupled plasma processing. The network of inductive and capacitive elements exhibits high currents under resonance which are efficient for plasma generation. Mode frequencies and impedances are accurately calculated by accounting for the mutual partial inductances using the impedance matrix. The effect of plasma inductive coupling on mode frequency shift and mode impedance is estimated using the complex image method, giving good agreement with experiment. It is proposed that the complex image method combined with the partial inductance concept (see the accompanying paper, Part I (Howling et al 2015 Plasma Sources Sci. Technol. 24 065014)) offers a general way to calculate the impedance characteristics of inductively-coupled plasma sources in planar geometry.
Community Detection in Quantum Complex Networks
NASA Astrophysics Data System (ADS)
Faccin, Mauro; Migdał, Piotr; Johnson, Tomi H.; Bergholm, Ville; Biamonte, Jacob D.
2014-10-01
Determining community structure is a central topic in the study of complex networks, be it technological, social, biological or chemical, static or in interacting systems. In this paper, we extend the concept of community detection from classical to quantum systems—a crucial missing component of a theory of complex networks based on quantum mechanics. We demonstrate that certain quantum mechanical effects cannot be captured using current classical complex network tools and provide new methods that overcome these problems. Our approaches are based on defining closeness measures between nodes, and then maximizing modularity with hierarchical clustering. Our closeness functions are based on quantum transport probability and state fidelity, two important quantities in quantum information theory. To illustrate the effectiveness of our approach in detecting community structure in quantum systems, we provide several examples, including a naturally occurring light-harvesting complex, LHCII. The prediction of our simplest algorithm, semiclassical in nature, mostly agrees with a proposed partitioning for the LHCII found in quantum chemistry literature, whereas our fully quantum treatment of the problem uncovers a new, consistent, and appropriately quantum community structure.
Complexity Characteristics of Currency Networks
NASA Astrophysics Data System (ADS)
Gorski, A. Z.; Drozdz, S.; Kwapien, J.; Oswiecimka, P.
2006-11-01
A large set of daily FOREX time series is analyzed. The corresponding correlation matrices (CM) are constructed for USD, EUR and PLN used as the base currencies. The triangle rule is interpreted as constraints reducing the number of independent returns. The CM spectrum is computed and compared with the cases of shuffled currencies and a fictitious random currency taken as a base currency. The Minimal Spanning Tree (MST) graphs are calculated and the clustering effects for strong currencies are found. It is shown that for MSTs the node rank has power like, scale free behavior. Finally, the scaling exponents are evaluated and found in the range analogous to those identified recently for various complex networks.
NASA Astrophysics Data System (ADS)
Aliakbary, Sadegh; Motallebi, Sadegh; Rashidian, Sina; Habibi, Jafar; Movaghar, Ali
2015-02-01
Real networks show nontrivial topological properties such as community structure and long-tail degree distribution. Moreover, many network analysis applications are based on topological comparison of complex networks. Classification and clustering of networks, model selection, and anomaly detection are just some applications of network comparison. In these applications, an effective similarity metric is needed which, given two complex networks of possibly different sizes, evaluates the amount of similarity between the structural features of the two networks. Traditional graph comparison approaches, such as isomorphism-based methods, are not only too time consuming but also inappropriate to compare networks with different sizes. In this paper, we propose an intelligent method based on the genetic algorithms for integrating, selecting, and weighting the network features in order to develop an effective similarity measure for complex networks. The proposed similarity metric outperforms state of the art methods with respect to different evaluation criteria.
Higher-order organization of complex networks.
Benson, Austin R; Gleich, David F; Leskovec, Jure
2016-07-01
Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks--at the level of small network subgraphs--remains largely unknown. Here, we develop a generalized framework for clustering networks on the basis of higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks, including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns. PMID:27387949
Centrality measures for networks with community structure
NASA Astrophysics Data System (ADS)
Gupta, Naveen; Singh, Anurag; Cherifi, Hocine
2016-06-01
Understanding the network structure, and finding out the influential nodes is a challenging issue in large networks. Identifying the most influential nodes in a network can be useful in many applications like immunization of nodes in case of epidemic spreading, during intentional attacks on complex networks. A lot of research is being done to devise centrality measures which could efficiently identify the most influential nodes in a network. There are two major approaches to this problem: On one hand, deterministic strategies that exploit knowledge about the overall network topology, while on the other end, random strategies are completely agnostic about the network structure. Centrality measures that can deal with a limited knowledge of the network structure are of prime importance. Indeed, in practice, information about the global structure of the overall network is rarely available or hard to acquire. Even if available, the structure of the network might be too large that it is too much computationally expensive to calculate global centrality measures. To that end, a centrality measure is proposed here that requires information only at the community level. Indeed, most of the real-world networks exhibit a community structure that can be exploited efficiently to discover the influential nodes. We performed a comparative evaluation of prominent global deterministic strategies together with stochastic strategies, an available and the proposed deterministic community-based strategy. Effectiveness of the proposed method is evaluated by performing experiments on synthetic and real-world networks with community structure in the case of immunization of nodes for epidemic control.
The noisy voter model on complex networks
NASA Astrophysics Data System (ADS)
Carro, Adrián; Toral, Raúl; San Miguel, Maxi
2016-04-01
We propose a new analytical method to study stochastic, binary-state models on complex networks. Moving beyond the usual mean-field theories, this alternative approach is based on the introduction of an annealed approximation for uncorrelated networks, allowing to deal with the network structure as parametric heterogeneity. As an illustration, we study the noisy voter model, a modification of the original voter model including random changes of state. The proposed method is able to unfold the dependence of the model not only on the mean degree (the mean-field prediction) but also on more complex averages over the degree distribution. In particular, we find that the degree heterogeneity—variance of the underlying degree distribution—has a strong influence on the location of the critical point of a noise-induced, finite-size transition occurring in the model, on the local ordering of the system, and on the functional form of its temporal correlations. Finally, we show how this latter point opens the possibility of inferring the degree heterogeneity of the underlying network by observing only the aggregate behavior of the system as a whole, an issue of interest for systems where only macroscopic, population level variables can be measured.
The noisy voter model on complex networks
Carro, Adrián; Toral, Raúl; San Miguel, Maxi
2016-01-01
We propose a new analytical method to study stochastic, binary-state models on complex networks. Moving beyond the usual mean-field theories, this alternative approach is based on the introduction of an annealed approximation for uncorrelated networks, allowing to deal with the network structure as parametric heterogeneity. As an illustration, we study the noisy voter model, a modification of the original voter model including random changes of state. The proposed method is able to unfold the dependence of the model not only on the mean degree (the mean-field prediction) but also on more complex averages over the degree distribution. In particular, we find that the degree heterogeneity—variance of the underlying degree distribution—has a strong influence on the location of the critical point of a noise-induced, finite-size transition occurring in the model, on the local ordering of the system, and on the functional form of its temporal correlations. Finally, we show how this latter point opens the possibility of inferring the degree heterogeneity of the underlying network by observing only the aggregate behavior of the system as a whole, an issue of interest for systems where only macroscopic, population level variables can be measured. PMID:27094773
The noisy voter model on complex networks.
Carro, Adrián; Toral, Raúl; San Miguel, Maxi
2016-01-01
We propose a new analytical method to study stochastic, binary-state models on complex networks. Moving beyond the usual mean-field theories, this alternative approach is based on the introduction of an annealed approximation for uncorrelated networks, allowing to deal with the network structure as parametric heterogeneity. As an illustration, we study the noisy voter model, a modification of the original voter model including random changes of state. The proposed method is able to unfold the dependence of the model not only on the mean degree (the mean-field prediction) but also on more complex averages over the degree distribution. In particular, we find that the degree heterogeneity-variance of the underlying degree distribution-has a strong influence on the location of the critical point of a noise-induced, finite-size transition occurring in the model, on the local ordering of the system, and on the functional form of its temporal correlations. Finally, we show how this latter point opens the possibility of inferring the degree heterogeneity of the underlying network by observing only the aggregate behavior of the system as a whole, an issue of interest for systems where only macroscopic, population level variables can be measured. PMID:27094773
Analyzing Complex Metabolomic Networks: Experiments and Simulation
NASA Astrophysics Data System (ADS)
Steuer, R.; Kurths, J.; Fiehn, O.; Weckwerth, W.
2002-03-01
In the recent years, remarkable advances in molecular biology have enabled us to measure the behavior of complex regularity networks underlying biological systems. In particular, high throughput techniques, such as gene expression arrays, allow a fast acquisition of a large number of simultaneously measured variables. Similar to gene expression, the analysis of metabolomic datasets results in a huge number of metabolite co-regulations: Metabolites are the end products of cellular regulatory processes, their level can be regarded as the ultimate response to genetic or environmental changes. In this presentation we focus on the topological description of such networks, using both, experimental data and simulations. In particular, we discuss the possibility to deduce novel links between metabolites, using concepts from (nonlinear) time series analysis and information theory.
Defining nodes in complex brain networks
Stanley, Matthew L.; Moussa, Malaak N.; Paolini, Brielle M.; Lyday, Robert G.; Burdette, Jonathan H.; Laurienti, Paul J.
2013-01-01
Network science holds great promise for expanding our understanding of the human brain in health, disease, development, and aging. Network analyses are quickly becoming the method of choice for analyzing functional MRI data. However, many technical issues have yet to be confronted in order to optimize results. One particular issue that remains controversial in functional brain network analyses is the definition of a network node. In functional brain networks a node represents some predefined collection of brain tissue, and an edge measures the functional connectivity between pairs of nodes. The characteristics of a node, chosen by the researcher, vary considerably in the literature. This manuscript reviews the current state of the art based on published manuscripts and highlights the strengths and weaknesses of three main methods for defining nodes. Voxel-wise networks are constructed by assigning a node to each, equally sized brain area (voxel). The fMRI time-series recorded from each voxel is then used to create the functional network. Anatomical methods utilize atlases to define the nodes based on brain structure. The fMRI time-series from all voxels within the anatomical area are averaged and subsequently used to generate the network. Functional activation methods rely on data from traditional fMRI activation studies, often from databases, to identify network nodes. Such methods identify the peaks or centers of mass from activation maps to determine the location of the nodes. Small (~10–20 millimeter diameter) spheres located at the coordinates of the activation foci are then applied to the data being used in the network analysis. The fMRI time-series from all voxels in the sphere are then averaged, and the resultant time series is used to generate the network. We attempt to clarify the discussion and move the study of complex brain networks forward. While the “correct” method to be used remains an open, possibly unsolvable question that deserves
Structural measures for multiplex networks
NASA Astrophysics Data System (ADS)
Battiston, Federico; Nicosia, Vincenzo; Latora, Vito
2014-03-01
Many real-world complex systems consist of a set of elementary units connected by relationships of different kinds. All such systems are better described in terms of multiplex networks, where the links at each layer represent a different type of interaction between the same set of nodes rather than in terms of (single-layer) networks. In this paper we present a general framework to describe and study multiplex networks, whose links are either unweighted or weighted. In particular, we propose a series of measures to characterize the multiplexicity of the systems in terms of (i) basic node and link properties such as the node degree, and the edge overlap and reinforcement, (ii) local properties such as the clustering coefficient and the transitivity, and (iii) global properties related to the navigability of the multiplex across the different layers. The measures we introduce are validated on a genuinely multiplex data set of Indonesian terrorists, where information among 78 individuals are recorded with respect to mutual trust, common operations, exchanged communications, and business relationships.
Structural measures for multiplex networks.
Battiston, Federico; Nicosia, Vincenzo; Latora, Vito
2014-03-01
Many real-world complex systems consist of a set of elementary units connected by relationships of different kinds. All such systems are better described in terms of multiplex networks, where the links at each layer represent a different type of interaction between the same set of nodes rather than in terms of (single-layer) networks. In this paper we present a general framework to describe and study multiplex networks, whose links are either unweighted or weighted. In particular, we propose a series of measures to characterize the multiplexicity of the systems in terms of (i) basic node and link properties such as the node degree, and the edge overlap and reinforcement, (ii) local properties such as the clustering coefficient and the transitivity, and (iii) global properties related to the navigability of the multiplex across the different layers. The measures we introduce are validated on a genuinely multiplex data set of Indonesian terrorists, where information among 78 individuals are recorded with respect to mutual trust, common operations, exchanged communications, and business relationships. PMID:24730896
Exploring the Morphospace of Communication Efficiency in Complex Networks
Goñi, Joaquín; Avena-Koenigsberger, Andrea; Velez de Mendizabal, Nieves; van den Heuvel, Martijn P.; Betzel, Richard F.; Sporns, Olaf
2013-01-01
Graph theoretical analysis has played a key role in characterizing global features of the topology of complex networks, describing diverse systems such as protein interactions, food webs, social relations and brain connectivity. How system elements communicate with each other depends not only on the structure of the network, but also on the nature of the system's dynamics which are constrained by the amount of knowledge and resources available for communication processes. Complementing widely used measures that capture efficiency under the assumption that communication preferentially follows shortest paths across the network (“routing”), we define analytic measures directed at characterizing network communication when signals flow in a random walk process (“diffusion”). The two dimensions of routing and diffusion efficiency define a morphospace for complex networks, with different network topologies characterized by different combinations of efficiency measures and thus occupying different regions of this space. We explore the relation of network topologies and efficiency measures by examining canonical network models, by evolving networks using a multi-objective optimization strategy, and by investigating real-world network data sets. Within the efficiency morphospace, specific aspects of network topology that differentially favor efficient communication for routing and diffusion processes are identified. Charting regions of the morphospace that are occupied by canonical, evolved or real networks allows inferences about the limits of communication efficiency imposed by connectivity and dynamics, as well as the underlying selection pressures that have shaped network topology. PMID:23505455
Network Motifs: Simple Building Blocks of Complex Networks
NASA Astrophysics Data System (ADS)
Milo, R.; Shen-Orr, S.; Itzkovitz, S.; Kashtan, N.; Chklovskii, D.; Alon, U.
2002-10-01
Complex networks are studied across many fields of science. To uncover their structural design principles, we defined ``network motifs,'' patterns of interconnections occurring in complex networks at numbers that are significantly higher than those in randomized networks. We found such motifs in networks from biochemistry, neurobiology, ecology, and engineering. The motifs shared by ecological food webs were distinct from the motifs shared by the genetic networks of Escherichia coli and Saccharomyces cerevisiae or from those found in the World Wide Web. Similar motifs were found in networks that perform information processing, even though they describe elements as different as biomolecules within a cell and synaptic connections between neurons in Caenorhabditis elegans. Motifs may thus define universal classes of networks. This approach may uncover the basic building blocks of most networks.
Complex networks: A winning strategy
NASA Astrophysics Data System (ADS)
D'Souza, Raissa M.
2013-04-01
Introducing connections between two distinct networks can tip the balance of power -- at times enhancing the weaker system. The properties of the nodes that are linked together often determine which network claims the competitive advantage.
Realizing actual feedback control of complex network
NASA Astrophysics Data System (ADS)
Tu, Chengyi; Cheng, Yuhua
2014-06-01
In this paper, we present the concept of feedbackability and how to identify the Minimum Feedbackability Set of an arbitrary complex directed network. Furthermore, we design an estimator and a feedback controller accessing one MFS to realize actual feedback control, i.e. control the system to our desired state according to the estimated system internal state from the output of estimator. Last but not least, we perform numerical simulations of a small linear time-invariant dynamics network and a real simple food network to verify the theoretical results. The framework presented here could make an arbitrary complex directed network realize actual feedback control and deepen our understanding of complex systems.
Minimum-cost control of complex networks
NASA Astrophysics Data System (ADS)
Li, Guoqi; Hu, Wuhua; Xiao, Gaoxi; Deng, Lei; Tang, Pei; Pei, Jing; Shi, Luping
2016-01-01
Finding the solution for driving a complex network at the minimum energy cost with a given number of controllers, known as the minimum-cost control problem, is critically important but remains largely open. We propose a projected gradient method to tackle this problem, which works efficiently in both synthetic and real-life networks. The study is then extended to the case where each controller can only be connected to a single network node to have the lowest connection complexity. We obtain the interesting insight that such connections basically avoid high-degree nodes of the network, which is in resonance with recent observations on controllability of complex networks. Our results provide the first technical path to enabling minimum-cost control of complex networks, and contribute new insights to locating the key nodes from a minimum-cost control perspective.
Pinning impulsive control algorithms for complex network
Sun, Wen; Lü, Jinhu; Chen, Shihua; Yu, Xinghuo
2014-03-15
In this paper, we further investigate the synchronization of complex dynamical network via pinning control in which a selection of nodes are controlled at discrete times. Different from most existing work, the pinning control algorithms utilize only the impulsive signals at discrete time instants, which may greatly improve the communication channel efficiency and reduce control cost. Two classes of algorithms are designed, one for strongly connected complex network and another for non-strongly connected complex network. It is suggested that in the strongly connected network with suitable coupling strength, a single controller at any one of the network's nodes can always pin the network to its homogeneous solution. In the non-strongly connected case, the location and minimum number of nodes needed to pin the network are determined by the Frobenius normal form of the coupling matrix. In addition, the coupling matrix is not necessarily symmetric or irreducible. Illustrative examples are then given to validate the proposed pinning impulsive control algorithms.
Effective Augmentation of Complex Networks
NASA Astrophysics Data System (ADS)
Wang, Jinjian; Yu, Xinghuo; Stone, Lewi
2016-05-01
Networks science plays an enormous role in many aspects of modern society from distributing electrical power across nations to spreading information and social networking amongst global populations. While modern networks constantly change in size, few studies have sought methods for the difficult task of optimising this growth. Here we study theoretical requirements for augmenting networks by adding source or sink nodes, without requiring additional driver-nodes to accommodate the change i.e., conserving structural controllability. Our “effective augmentation” algorithm takes advantage of clusters intrinsic to the network topology, and permits rapidly and efficient augmentation of a large number of nodes in one time-step. “Effective augmentation” is shown to work successfully on a wide range of model and real networks. The method has numerous applications (e.g. study of biological, social, power and technological networks) and potentially of significant practical and economic value.
Effective Augmentation of Complex Networks.
Wang, Jinjian; Yu, Xinghuo; Stone, Lewi
2016-01-01
Networks science plays an enormous role in many aspects of modern society from distributing electrical power across nations to spreading information and social networking amongst global populations. While modern networks constantly change in size, few studies have sought methods for the difficult task of optimising this growth. Here we study theoretical requirements for augmenting networks by adding source or sink nodes, without requiring additional driver-nodes to accommodate the change i.e., conserving structural controllability. Our "effective augmentation" algorithm takes advantage of clusters intrinsic to the network topology, and permits rapidly and efficient augmentation of a large number of nodes in one time-step. "Effective augmentation" is shown to work successfully on a wide range of model and real networks. The method has numerous applications (e.g. study of biological, social, power and technological networks) and potentially of significant practical and economic value. PMID:27165120
Effective Augmentation of Complex Networks
Wang, Jinjian; Yu, Xinghuo; Stone, Lewi
2016-01-01
Networks science plays an enormous role in many aspects of modern society from distributing electrical power across nations to spreading information and social networking amongst global populations. While modern networks constantly change in size, few studies have sought methods for the difficult task of optimising this growth. Here we study theoretical requirements for augmenting networks by adding source or sink nodes, without requiring additional driver-nodes to accommodate the change i.e., conserving structural controllability. Our “effective augmentation” algorithm takes advantage of clusters intrinsic to the network topology, and permits rapidly and efficient augmentation of a large number of nodes in one time-step. “Effective augmentation” is shown to work successfully on a wide range of model and real networks. The method has numerous applications (e.g. study of biological, social, power and technological networks) and potentially of significant practical and economic value. PMID:27165120
Investigation of a protein complex network
NASA Astrophysics Data System (ADS)
Mashaghi, A. R.; Ramezanpour, A.; Karimipour, V.
2004-09-01
The budding yeast Saccharomyces cerevisiae is the first eukaryote whose genome has been completely sequenced. It is also the first eukaryotic cell whose proteome (the set of all proteins) and interactome (the network of all mutual interactions between proteins) has been analyzed. In this paper we study the structure of the yeast protein complex network in which weighted edges between complexes represent the number of shared proteins. It is found that the network of protein complexes is a small world network with scale free behavior for many of its distributions. However we find that there are no strong correlations between the weights and degrees of neighboring complexes. To reveal non-random features of the network we also compare it with a null model in which the complexes randomly select their proteins. Finally we propose a simple evolutionary model based on duplication and divergence of proteins.
Contagion on complex networks with persuasion
NASA Astrophysics Data System (ADS)
Huang, Wei-Min; Zhang, Li-Jie; Xu, Xin-Jian; Fu, Xinchu
2016-03-01
The threshold model has been widely adopted as a classic model for studying contagion processes on social networks. We consider asymmetric individual interactions in social networks and introduce a persuasion mechanism into the threshold model. Specifically, we study a combination of adoption and persuasion in cascading processes on complex networks. It is found that with the introduction of the persuasion mechanism, the system may become more vulnerable to global cascades, and the effects of persuasion tend to be more significant in heterogeneous networks than those in homogeneous networks: a comparison between heterogeneous and homogeneous networks shows that under weak persuasion, heterogeneous networks tend to be more robust against random shocks than homogeneous networks; whereas under strong persuasion, homogeneous networks are more stable. Finally, we study the effects of adoption and persuasion threshold heterogeneity on systemic stability. Though both heterogeneities give rise to global cascades, the adoption heterogeneity has an overwhelmingly stronger impact than the persuasion heterogeneity when the network connectivity is sufficiently dense.
Analysis of complex systems using neural networks
Uhrig, R.E. . Dept. of Nuclear Engineering Oak Ridge National Lab., TN )
1992-01-01
The application of neural networks, alone or in conjunction with other advanced technologies (expert systems, fuzzy logic, and/or genetic algorithms), to some of the problems of complex engineering systems has the potential to enhance the safety, reliability, and operability of these systems. Typically, the measured variables from the systems are analog variables that must be sampled and normalized to expected peak values before they are introduced into neural networks. Often data must be processed to put it into a form more acceptable to the neural network (e.g., a fast Fourier transformation of the time-series data to produce a spectral plot of the data). Specific applications described include: (1) Diagnostics: State of the Plant (2) Hybrid System for Transient Identification, (3) Sensor Validation, (4) Plant-Wide Monitoring, (5) Monitoring of Performance and Efficiency, and (6) Analysis of Vibrations. Although specific examples described deal with nuclear power plants or their subsystems, the techniques described can be applied to a wide variety of complex engineering systems.
Analysis of complex systems using neural networks
Uhrig, R.E. |
1992-12-31
The application of neural networks, alone or in conjunction with other advanced technologies (expert systems, fuzzy logic, and/or genetic algorithms), to some of the problems of complex engineering systems has the potential to enhance the safety, reliability, and operability of these systems. Typically, the measured variables from the systems are analog variables that must be sampled and normalized to expected peak values before they are introduced into neural networks. Often data must be processed to put it into a form more acceptable to the neural network (e.g., a fast Fourier transformation of the time-series data to produce a spectral plot of the data). Specific applications described include: (1) Diagnostics: State of the Plant (2) Hybrid System for Transient Identification, (3) Sensor Validation, (4) Plant-Wide Monitoring, (5) Monitoring of Performance and Efficiency, and (6) Analysis of Vibrations. Although specific examples described deal with nuclear power plants or their subsystems, the techniques described can be applied to a wide variety of complex engineering systems.
Measurement of Computer Communication Networks.
ERIC Educational Resources Information Center
Abrams, Marshall D.; And Others
Measures, tools, and techniques applicable to the performance measurement of computer communication networks are described for technicians who procure computer services from a remote access network. Cost considerations are discussed as a major component of evaluation, and measurement and evaluation methodologies are surveyed. External measurement…
Bridge and brick motifs in complex networks
NASA Astrophysics Data System (ADS)
Huang, Chung-Yuan; Sun, Chuen-Tsai; Cheng, Chia-Ying; Hsieh, Ji-Lung
2007-04-01
Acknowledging the expanding role of complex networks in numerous scientific contexts, we examine significant functional and topological differences between bridge and brick motifs for predicting network behaviors and functions. After observing similarities between social networks and their genetic, ecological, and engineering counterparts, we identify a larger number of brick motifs in social networks and bridge motifs in the other three types. We conclude that bridge and brick motif content analysis can assist researchers in understanding the small-world and clustering properties of network structures when investigating network functions and behaviors.
CORRELATION PROFILES AND MOTIFS IN COMPLEX NETWORKS.
MASLOV,S.SNEPPEN,K.ALON,U.
2004-01-16
Networks have recently emerged as a unifying theme in complex systems research [1]. It is in fact no coincidence that networks and complexity are so heavily intertwined. Any future definition of a complex system should reflect the fact that such systems consist of many mutually interacting components. These components are far from being identical as say electrons in systems studied by condensed matter physics. In a truly complex system each of them has a unique identity allowing one to separate it from the others. The very first question one may ask about such a system is which other components a given component interacts with? This information system wide can be visualized as a graph, whose nodes correspond to individual components of the complex system in question and edges to their mutual interactions. Such a network can be thought of as a backbone of the complex system. Of course, system's dynamics depends not only on the topology of an underlying network but also on the exact form of interaction of components with each other, which can be very different in various complex systems. However, the underlying network may contain clues about the basic design principles and/or evolutionary history of the complex system in question. The goal of this article is to provide readers with a set of useful tools that would help to decide which features of a complex network are there by pure chance alone, and which of them were possibly designed or evolved to their present state.
Revealing the hidden language of complex networks.
Yaveroğlu, Ömer Nebil; Malod-Dognin, Noël; Davis, Darren; Levnajic, Zoran; Janjic, Vuk; Karapandza, Rasa; Stojmirovic, Aleksandar; Pržulj, Nataša
2014-01-01
Sophisticated methods for analysing complex networks promise to be of great benefit to almost all scientific disciplines, yet they elude us. In this work, we make fundamental methodological advances to rectify this. We discover that the interaction between a small number of roles, played by nodes in a network, can characterize a network's structure and also provide a clear real-world interpretation. Given this insight, we develop a framework for analysing and comparing networks, which outperforms all existing ones. We demonstrate its strength by uncovering novel relationships between seemingly unrelated networks, such as Facebook, metabolic, and protein structure networks. We also use it to track the dynamics of the world trade network, showing that a country's role of a broker between non-trading countries indicates economic prosperity, whereas peripheral roles are associated with poverty. This result, though intuitive, has escaped all existing frameworks. Finally, our approach translates network topology into everyday language, bringing network analysis closer to domain scientists. PMID:24686408
Revealing the Hidden Language of Complex Networks
NASA Astrophysics Data System (ADS)
Yaveroğlu, Ömer Nebil; Malod-Dognin, Noël; Davis, Darren; Levnajic, Zoran; Janjic, Vuk; Karapandza, Rasa; Stojmirovic, Aleksandar; Pržulj, Nataša
2014-04-01
Sophisticated methods for analysing complex networks promise to be of great benefit to almost all scientific disciplines, yet they elude us. In this work, we make fundamental methodological advances to rectify this. We discover that the interaction between a small number of roles, played by nodes in a network, can characterize a network's structure and also provide a clear real-world interpretation. Given this insight, we develop a framework for analysing and comparing networks, which outperforms all existing ones. We demonstrate its strength by uncovering novel relationships between seemingly unrelated networks, such as Facebook, metabolic, and protein structure networks. We also use it to track the dynamics of the world trade network, showing that a country's role of a broker between non-trading countries indicates economic prosperity, whereas peripheral roles are associated with poverty. This result, though intuitive, has escaped all existing frameworks. Finally, our approach translates network topology into everyday language, bringing network analysis closer to domain scientists.
Revealing the Hidden Language of Complex Networks
Yaveroğlu, Ömer Nebil; Malod-Dognin, Noël; Davis, Darren; Levnajic, Zoran; Janjic, Vuk; Karapandza, Rasa; Stojmirovic, Aleksandar; Pržulj, Nataša
2014-01-01
Sophisticated methods for analysing complex networks promise to be of great benefit to almost all scientific disciplines, yet they elude us. In this work, we make fundamental methodological advances to rectify this. We discover that the interaction between a small number of roles, played by nodes in a network, can characterize a network's structure and also provide a clear real-world interpretation. Given this insight, we develop a framework for analysing and comparing networks, which outperforms all existing ones. We demonstrate its strength by uncovering novel relationships between seemingly unrelated networks, such as Facebook, metabolic, and protein structure networks. We also use it to track the dynamics of the world trade network, showing that a country's role of a broker between non-trading countries indicates economic prosperity, whereas peripheral roles are associated with poverty. This result, though intuitive, has escaped all existing frameworks. Finally, our approach translates network topology into everyday language, bringing network analysis closer to domain scientists. PMID:24686408
Percolation of localized attack on complex networks
NASA Astrophysics Data System (ADS)
Shao, Shuai; Huang, Xuqing; Stanley, H. Eugene; Havlin, Shlomo
2015-02-01
The robustness of complex networks against node failure and malicious attack has been of interest for decades, while most of the research has focused on random attack or hub-targeted attack. In many real-world scenarios, however, attacks are neither random nor hub-targeted, but localized, where a group of neighboring nodes in a network are attacked and fail. In this paper we develop a percolation framework to analytically and numerically study the robustness of complex networks against such localized attack. In particular, we investigate this robustness in Erdős-Rényi networks, random-regular networks, and scale-free networks. Our results provide insight into how to better protect networks, enhance cybersecurity, and facilitate the design of more robust infrastructures.
Dynamical robustness analysis of weighted complex networks
NASA Astrophysics Data System (ADS)
He, Zhiwei; Liu, Shuai; Zhan, Meng
2013-09-01
Robustness of weighted complex networks is analyzed from nonlinear dynamical point of view and with focus on different roles of high-degree and low-degree nodes. We find that the phenomenon for the low-degree nodes being the key nodes in the heterogeneous networks only appears in weakly weighted networks and for weak coupling. For all other parameters, the heterogeneous networks are always highly vulnerable to the failure of high-degree nodes; this point is the same as in the structural robustness analysis. We also find that with random inactivation, heterogeneous networks are always more robust than the corresponding homogeneous networks with the same average degree except for one special parameter. Thus our findings give an integrated picture for the dynamical robustness analysis on complex networks.
A random interacting network model for complex networks
NASA Astrophysics Data System (ADS)
Goswami, Bedartha; Shekatkar, Snehal M.; Rheinwalt, Aljoscha; Ambika, G.; Kurths, Jürgen
2015-12-01
We propose a RAndom Interacting Network (RAIN) model to study the interactions between a pair of complex networks. The model involves two major steps: (i) the selection of a pair of nodes, one from each network, based on intra-network node-based characteristics, and (ii) the placement of a link between selected nodes based on the similarity of their relative importance in their respective networks. Node selection is based on a selection fitness function and node linkage is based on a linkage probability defined on the linkage scores of nodes. The model allows us to relate within-network characteristics to between-network structure. We apply the model to the interaction between the USA and Schengen airline transportation networks (ATNs). Our results indicate that two mechanisms: degree-based preferential node selection and degree-assortative link placement are necessary to replicate the observed inter-network degree distributions as well as the observed inter-network assortativity. The RAIN model offers the possibility to test multiple hypotheses regarding the mechanisms underlying network interactions. It can also incorporate complex interaction topologies. Furthermore, the framework of the RAIN model is general and can be potentially adapted to various real-world complex systems.
A random interacting network model for complex networks
Goswami, Bedartha; Shekatkar, Snehal M.; Rheinwalt, Aljoscha; Ambika, G.; Kurths, Jürgen
2015-01-01
We propose a RAndom Interacting Network (RAIN) model to study the interactions between a pair of complex networks. The model involves two major steps: (i) the selection of a pair of nodes, one from each network, based on intra-network node-based characteristics, and (ii) the placement of a link between selected nodes based on the similarity of their relative importance in their respective networks. Node selection is based on a selection fitness function and node linkage is based on a linkage probability defined on the linkage scores of nodes. The model allows us to relate within-network characteristics to between-network structure. We apply the model to the interaction between the USA and Schengen airline transportation networks (ATNs). Our results indicate that two mechanisms: degree-based preferential node selection and degree-assortative link placement are necessary to replicate the observed inter-network degree distributions as well as the observed inter-network assortativity. The RAIN model offers the possibility to test multiple hypotheses regarding the mechanisms underlying network interactions. It can also incorporate complex interaction topologies. Furthermore, the framework of the RAIN model is general and can be potentially adapted to various real-world complex systems. PMID:26657032
A random interacting network model for complex networks.
Goswami, Bedartha; Shekatkar, Snehal M; Rheinwalt, Aljoscha; Ambika, G; Kurths, Jürgen
2015-01-01
We propose a RAndom Interacting Network (RAIN) model to study the interactions between a pair of complex networks. The model involves two major steps: (i) the selection of a pair of nodes, one from each network, based on intra-network node-based characteristics, and (ii) the placement of a link between selected nodes based on the similarity of their relative importance in their respective networks. Node selection is based on a selection fitness function and node linkage is based on a linkage probability defined on the linkage scores of nodes. The model allows us to relate within-network characteristics to between-network structure. We apply the model to the interaction between the USA and Schengen airline transportation networks (ATNs). Our results indicate that two mechanisms: degree-based preferential node selection and degree-assortative link placement are necessary to replicate the observed inter-network degree distributions as well as the observed inter-network assortativity. The RAIN model offers the possibility to test multiple hypotheses regarding the mechanisms underlying network interactions. It can also incorporate complex interaction topologies. Furthermore, the framework of the RAIN model is general and can be potentially adapted to various real-world complex systems. PMID:26657032
Controlling complex networks with conformity behavior
NASA Astrophysics Data System (ADS)
Wang, Xu-Wen; Nie, Sen; Wang, Wen-Xu; Wang, Bing-Hong
2015-09-01
Controlling complex networks accompanied by common conformity behavior is a fundamental problem in social and physical science. Conformity behavior that individuals tend to follow the majority in their neighborhood is common in human society and animal communities. Despite recent progress in understanding controllability of complex networks, the existent controllability theories cannot be directly applied to networks associated with conformity. Here we propose a simple model to incorporate conformity-based decision making into the evolution of a network system, which allows us to employ the exact controllability theory to explore the controllability of such systems. We offer rigorous theoretical results of controllability for representative regular networks. We also explore real networks in different fields and some typical model networks, finding some interesting results that are different from the predictions of structural and exact controllability theory in the absence of conformity. We finally present an example of steering a real social network to some target states to further validate our controllability theory and tools. Our work offers a more realistic understanding of network controllability with conformity behavior and can have potential applications in networked evolutionary games, opinion dynamics and many other complex networked systems.
Detecting link failures in complex network processes using remote monitoring
NASA Astrophysics Data System (ADS)
Dhal, R.; Abad Torres, J.; Roy, S.
2015-11-01
We study whether local structural changes in a complex network can be distinguished from passive remote time-course measurements of the network's dynamics. Specifically the detection of link failures in a network synchronization process from noisy measurements at a single network component is considered. By phrasing the detection task as a Maximum A Posteriori Probability hypothesis testing problem, we are able to obtain conditions under which the detection is (1) improved over the a priori and (2) asymptotically perfect, in terms of the network spectrum and graph. We find that, in the case where the detector has knowledge of the network's state, perfect detection is possible under general connectivity conditions regardless of the measurement location. When the detector does not have state knowledge, a remote signature permits improved but not perfect detection, under the same connectivity conditions. At its essence, detectability is achieved because of the close connection between a network's topology, its eigenvalues and local response characteristics.
Sustainable growth in complex networks
NASA Astrophysics Data System (ADS)
Tessone, C. J.; Geipel, M. M.; Schweitzer, F.
2011-12-01
Based on the analysis of the dependency network in 18 Java projects, we develop a novel model of network growth which considers both preferential attachment and the addition of new nodes with a heterogeneous distribution of their initial degree, k0. Empirically we find that the cumulative distributions of initial and final degrees in the network follow power law behaviours: 1-P(k0)~k01-α, and 1-P(k)~k1-γ, respectively. For the total number of links as a function of the network size, we find empirically K(N)~Nβ, where βin[1.25, 2] (for small N), while converging to β~1 for large N. This indicates a transition from a growth regime with increasing network density towards a sustainable regime, which prevents a collapse due to ever increasing dependencies. Our theoretical framework allows us to predict relations between the exponents α, β, γ, which also link issues of software engineering and developer activity. These relations are verified by means of computer simulations and empirical investigations. They indicate that the growth of real Open Source Software networks occurs on the edge between two regimes, which are dominated either by the initial degree distribution of added nodes, or by the preferential attachment mechanism. Hence, the heterogeneous degree distribution of newly added nodes, found empirically, is essential to describe the laws of sustainable growth in networks.
Monotone measures of statistical complexity
NASA Astrophysics Data System (ADS)
Rudnicki, Łukasz; Toranzo, Irene V.; Sánchez-Moreno, Pablo; Dehesa, Jesús S.
2016-01-01
We introduce and discuss the notion of monotonicity for the complexity measures of general probability distributions, patterned after the resource theory of quantum entanglement. Then, we explore whether this property is satisfied by the three main intrinsic measures of complexity (Crámer-Rao, Fisher-Shannon, LMC) and some of their generalizations.
Statistically Validated Networks in Bipartite Complex Systems
Tumminello, Michele; Miccichè, Salvatore; Lillo, Fabrizio; Piilo, Jyrki; Mantegna, Rosario N.
2011-01-01
Many complex systems present an intrinsic bipartite structure where elements of one set link to elements of the second set. In these complex systems, such as the system of actors and movies, elements of one set are qualitatively different than elements of the other set. The properties of these complex systems are typically investigated by constructing and analyzing a projected network on one of the two sets (for example the actor network or the movie network). Complex systems are often very heterogeneous in the number of relationships that the elements of one set establish with the elements of the other set, and this heterogeneity makes it very difficult to discriminate links of the projected network that are just reflecting system's heterogeneity from links relevant to unveil the properties of the system. Here we introduce an unsupervised method to statistically validate each link of a projected network against a null hypothesis that takes into account system heterogeneity. We apply the method to a biological, an economic and a social complex system. The method we propose is able to detect network structures which are very informative about the organization and specialization of the investigated systems, and identifies those relationships between elements of the projected network that cannot be explained simply by system heterogeneity. We also show that our method applies to bipartite systems in which different relationships might have different qualitative nature, generating statistically validated networks in which such difference is preserved. PMID:21483858
Speed of complex network synchronization
NASA Astrophysics Data System (ADS)
Grabow, C.; Grosskinsky, S.; Timme, M.
2011-12-01
Synchrony is one of the most common dynamical states emerging on networks. The speed of convergence towards synchrony provides a fundamental collective time scale for synchronizing systems. Here we study the asymptotic synchronization times for directed networks with topologies ranging from completely ordered, grid-like, to completely disordered, random, including intermediate, partially disordered topologies. We extend the approach of master stability functions to quantify synchronization times. We find that the synchronization times strongly and systematically depend on the network topology. In particular, at fixed in-degree, stronger topological randomness induces faster synchronization, whereas at fixed path length, synchronization is slowest for intermediate randomness in the small-world regime. Randomly rewiring real-world neural, social and transport networks confirms this picture.
Structure of Mutualistic Complex Networks
NASA Astrophysics Data System (ADS)
Hwang, Jun Kyung; Maeng, Seong Eun; Cha, Moon Yong; Lee, Jae Woo
We consider the structures of six plant-pollinator mutualistic networks. The plants and pollinators are linked by the plant-pollinating relation. We assigned the visiting frequency of pollinators to a plant as a weight of each link. We calculated the cumulative distribution functions of the degree and strength for the networks. We observed a power-law, linear, and stretched exponential dependence of the cumulative distribution function. We also calculated the disparity and the strength of the nodes s(k) with degree k. We observed that the plant-pollinator networks exhibit an disassortative behaviors and nonlinear dependence of the strength on the nodes. In mutualistic networks links with large weight are connected to the neighbors with small degrees.
Link prediction in complex networks: A survey
NASA Astrophysics Data System (ADS)
Lü, Linyuan; Zhou, Tao
2011-03-01
Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labeled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.
Optimal dynamic bandwidth allocation for complex networks
NASA Astrophysics Data System (ADS)
Jiang, Zhong-Yuan; Liang, Man-Gui; Li, Qian; Guo, Dong-Chao
2013-03-01
Traffic capacity of one network strongly depends on the link’s bandwidth allocation strategy. In previous bandwidth allocation mechanisms, once one link’s bandwidth is allocated, it will be fixed throughout the overall traffic transmission process. However, the traffic load of every link changes from time to time. In this paper, with finite total bandwidth resource of the network, we propose to dynamically allocate the total bandwidth resource in which each link’s bandwidth is proportional to the queue length of the output buffer of the link per time step. With plenty of data packets in the network, the traffic handling ability of all links of the network achieves full utilization. The theoretical analysis and the extensive simulation results on complex networks are consistent. This work is valuable for network service providers to improve network performance or to do reasonable network design efficiently.
Localized recovery of complex networks against failure.
Shang, Yilun
2016-01-01
Resilience of complex networks to failure has been an important issue in network research for decades, and recent studies have begun to focus on the inverse recovery of network functionality through strategically healing missing nodes or edges. However, the effect of network recovery is far from fully understood, and a general theory is still missing. Here we propose and study a general model of localized recovery, where a group of neighboring nodes are restored in an invasive way from a seed node. We develop a theoretical framework to compare the effect of random recovery (RR) and localized recovery (LR) in complex networks including Erdős-Rényi networks, random regular networks, and scale-free networks. We find detailed phase diagrams for the subnetwork of occupied nodes and the "complement network" of failed nodes under RR and LR. By identifying the two competitive forces behind LR, we present an analytical and numerical approach to guide us in choosing the appropriate recovery strategy and provide estimation on its effect by using the degree distribution of the original network as the only input. Our work therefore provides insight for quantitatively understanding recovery process and its implications in infrastructure protection in various complex systems. PMID:27456202
Traffic congestion in interconnected complex networks
NASA Astrophysics Data System (ADS)
Tan, Fei; Wu, Jiajing; Xia, Yongxiang; Tse, Chi K.
2014-06-01
Traffic congestion in isolated complex networks has been investigated extensively over the last decade. Coupled network models have recently been developed to facilitate further understanding of real complex systems. Analysis of traffic congestion in coupled complex networks, however, is still relatively unexplored. In this paper, we try to explore the effect of interconnections on traffic congestion in interconnected Barabási-Albert scale-free networks. We find that assortative coupling can alleviate traffic congestion more readily than disassortative and random coupling when the node processing capacity is allocated based on node usage probability. Furthermore, the optimal coupling probability can be found for assortative coupling. However, three types of coupling preferences achieve similar traffic performance if all nodes share the same processing capacity. We analyze interconnected Internet autonomous-system-level graphs of South Korea and Japan and obtain similar results. Some practical suggestions are presented to optimize such real-world interconnected networks accordingly.
Distinguishing fiction from non-fiction with complex networks
NASA Astrophysics Data System (ADS)
Larue, David M.; Carr, Lincoln D.; Jones, Linnea K.; Stevanak, Joe T.
2014-03-01
Complex Network Measures are applied to networks constructed from texts in English to demonstrate an initial viability in textual analysis. Texts from novels and short stories obtained from Project Gutenberg and news stories obtained from NPR are selected. Unique word stems in a text are used as nodes in an associated unweighted undirected network, with edges connecting words occurring within a certain number of words somewhere in the text. Various combinations of complex network measures are computed for each text's network. Fisher's Linear Discriminant analysis is used to build a parameter optimizing the ability to separate the texts according to their genre. Success rates in the 70% range for correctly distinguishing fiction from non-fiction were obtained using edges defined as within four words, using 400 word samples from 400 texts from each of the two genres with some combinations of measures such as the power-law exponents of degree distributions and clustering coefficients.
Tsallis information dimension of complex networks
NASA Astrophysics Data System (ADS)
Zhang, Qi; Luo, Chuanhai; Li, Meizhu; Deng, Yong; Mahadevan, Sankaran
2015-02-01
The fractal and self-similarity properties are revealed in many complex networks. The information dimension is a useful method to describe the fractal and self-similarity properties of the complex networks. In order to show the influence of different parts in the complex networks to the information dimension, we have proposed a new information dimension based on the Tsallis entropy namely the Tsallis information dimension. The proposed information dimension is changed according to the scale which is described by the nonextensivity parameter q, and it is inverse with the nonextensivity parameter q. The existing information dimension is a special case of the Tsallis information dimension when q = 1. The Tsallis information dimension is a generalized information dimension of the complex networks.
Topological Strata of Weighted Complex Networks
Petri, Giovanni; Scolamiero, Martina; Donato, Irene; Vaccarino, Francesco
2013-01-01
The statistical mechanical approach to complex networks is the dominant paradigm in describing natural and societal complex systems. The study of network properties, and their implications on dynamical processes, mostly focus on locally defined quantities of nodes and edges, such as node degrees, edge weights and –more recently– correlations between neighboring nodes. However, statistical methods quickly become cumbersome when dealing with many-body properties and do not capture the precise mesoscopic structure of complex networks. Here we introduce a novel method, based on persistent homology, to detect particular non-local structures, akin to weighted holes within the link-weight network fabric, which are invisible to existing methods. Their properties divide weighted networks in two broad classes: one is characterized by small hierarchically nested holes, while the second displays larger and longer living inhomogeneities. These classes cannot be reduced to known local or quasilocal network properties, because of the intrinsic non-locality of homological properties, and thus yield a new classification built on high order coordination patterns. Our results show that topology can provide novel insights relevant for many-body interactions in social and spatial networks. Moreover, this new method creates the first bridge between network theory and algebraic topology, which will allow to import the toolset of algebraic methods to complex systems. PMID:23805226
Topological Strata of Weighted Complex Networks.
Petri, Giovanni; Scolamiero, Martina; Donato, Irene; Vaccarino, Francesco
2013-01-01
The statistical mechanical approach to complex networks is the dominant paradigm in describing natural and societal complex systems. The study of network properties, and their implications on dynamical processes, mostly focus on locally defined quantities of nodes and edges, such as node degrees, edge weights and -more recently- correlations between neighboring nodes. However, statistical methods quickly become cumbersome when dealing with many-body properties and do not capture the precise mesoscopic structure of complex networks. Here we introduce a novel method, based on persistent homology, to detect particular non-local structures, akin to weighted holes within the link-weight network fabric, which are invisible to existing methods. Their properties divide weighted networks in two broad classes: one is characterized by small hierarchically nested holes, while the second displays larger and longer living inhomogeneities. These classes cannot be reduced to known local or quasilocal network properties, because of the intrinsic non-locality of homological properties, and thus yield a new classification built on high order coordination patterns. Our results show that topology can provide novel insights relevant for many-body interactions in social and spatial networks. Moreover, this new method creates the first bridge between network theory and algebraic topology, which will allow to import the toolset of algebraic methods to complex systems. PMID:23805226
An Adaptive Complex Network Model for Brain Functional Networks
Gomez Portillo, Ignacio J.; Gleiser, Pablo M.
2009-01-01
Brain functional networks are graph representations of activity in the brain, where the vertices represent anatomical regions and the edges their functional connectivity. These networks present a robust small world topological structure, characterized by highly integrated modules connected sparsely by long range links. Recent studies showed that other topological properties such as the degree distribution and the presence (or absence) of a hierarchical structure are not robust, and show different intriguing behaviors. In order to understand the basic ingredients necessary for the emergence of these complex network structures we present an adaptive complex network model for human brain functional networks. The microscopic units of the model are dynamical nodes that represent active regions of the brain, whose interaction gives rise to complex network structures. The links between the nodes are chosen following an adaptive algorithm that establishes connections between dynamical elements with similar internal states. We show that the model is able to describe topological characteristics of human brain networks obtained from functional magnetic resonance imaging studies. In particular, when the dynamical rules of the model allow for integrated processing over the entire network scale-free non-hierarchical networks with well defined communities emerge. On the other hand, when the dynamical rules restrict the information to a local neighborhood, communities cluster together into larger ones, giving rise to a hierarchical structure, with a truncated power law degree distribution. PMID:19738902
Localized recovery of complex networks against failure
Shang, Yilun
2016-01-01
Resilience of complex networks to failure has been an important issue in network research for decades, and recent studies have begun to focus on the inverse recovery of network functionality through strategically healing missing nodes or edges. However, the effect of network recovery is far from fully understood, and a general theory is still missing. Here we propose and study a general model of localized recovery, where a group of neighboring nodes are restored in an invasive way from a seed node. We develop a theoretical framework to compare the effect of random recovery (RR) and localized recovery (LR) in complex networks including Erdős-Rényi networks, random regular networks, and scale-free networks. We find detailed phase diagrams for the subnetwork of occupied nodes and the “complement network” of failed nodes under RR and LR. By identifying the two competitive forces behind LR, we present an analytical and numerical approach to guide us in choosing the appropriate recovery strategy and provide estimation on its effect by using the degree distribution of the original network as the only input. Our work therefore provides insight for quantitatively understanding recovery process and its implications in infrastructure protection in various complex systems. PMID:27456202
Localized recovery of complex networks against failure
NASA Astrophysics Data System (ADS)
Shang, Yilun
2016-07-01
Resilience of complex networks to failure has been an important issue in network research for decades, and recent studies have begun to focus on the inverse recovery of network functionality through strategically healing missing nodes or edges. However, the effect of network recovery is far from fully understood, and a general theory is still missing. Here we propose and study a general model of localized recovery, where a group of neighboring nodes are restored in an invasive way from a seed node. We develop a theoretical framework to compare the effect of random recovery (RR) and localized recovery (LR) in complex networks including Erdős-Rényi networks, random regular networks, and scale-free networks. We find detailed phase diagrams for the subnetwork of occupied nodes and the “complement network” of failed nodes under RR and LR. By identifying the two competitive forces behind LR, we present an analytical and numerical approach to guide us in choosing the appropriate recovery strategy and provide estimation on its effect by using the degree distribution of the original network as the only input. Our work therefore provides insight for quantitatively understanding recovery process and its implications in infrastructure protection in various complex systems.
Topology and energy transport in networks of interacting photosynthetic complexes
NASA Astrophysics Data System (ADS)
Allegra, Michele; Giorda, Paolo
2012-05-01
We address the role of topology in the energy transport process that occurs in networks of photosynthetic complexes. We take inspiration from light-harvesting networks present in purple bacteria and simulate an incoherent dissipative energy transport process on more general and abstract networks, considering both regular structures (Cayley trees and hyperbranched fractals) and randomly generated ones. We focus on the the two primary light-harvesting complexes of purple bacteria, i.e., the LH1 and LH2, and we use network-theoretical centrality measures in order to select different LH1 arrangements. We show that different choices cause significant differences in the transport efficiencies, and that for regular networks, centrality measures allow us to identify arrangements that ensure transport efficiencies which are better than those obtained with a random disposition of the complexes. The optimal arrangements strongly depend on the dissipative nature of the dynamics and on the topological properties of the networks considered, and depending on the latter, they are achieved by using global versus local centrality measures. For randomly generated networks, a random arrangement of the complexes already provides efficient transport, and this suggests the process is strong with respect to limited amount of control in the structure design and to the disorder inherent in the construction of randomly assembled structures. Finally, we compare the networks considered with the real biological networks and find that the latter have in general better performances, due to their higher connectivity, but the former with optimal arrangements can mimic the real networks' behavior for a specific range of transport parameters. These results show that the use of network-theoretical concepts can be crucial for the characterization and design of efficient artificial energy transport networks.
Maximizing information exchange between complex networks
NASA Astrophysics Data System (ADS)
West, Bruce J.; Geneston, Elvis L.; Grigolini, Paolo
2008-10-01
Science is not merely the smooth progressive interaction of hypothesis, experiment and theory, although it sometimes has that form. More realistically the scientific study of any given complex phenomenon generates a number of explanations, from a variety of perspectives, that eventually requires synthesis to achieve a deep level of insight and understanding. One such synthesis has created the field of out-of-equilibrium statistical physics as applied to the understanding of complex dynamic networks. Over the past forty years the concept of complexity has undergone a metamorphosis. Complexity was originally seen as a consequence of memory in individual particle trajectories, in full agreement with a Hamiltonian picture of microscopic dynamics and, in principle, macroscopic dynamics could be derived from the microscopic Hamiltonian picture. The main difficulty in deriving macroscopic dynamics from microscopic dynamics is the need to take into account the actions of a very large number of components. The existence of events such as abrupt jumps, considered by the conventional continuous time random walk approach to describing complexity was never perceived as conflicting with the Hamiltonian view. Herein we review many of the reasons why this traditional Hamiltonian view of complexity is unsatisfactory. We show that as a result of technological advances, which make the observation of single elementary events possible, the definition of complexity has shifted from the conventional memory concept towards the action of non-Poisson renewal events. We show that the observation of crucial processes, such as the intermittent fluorescence of blinking quantum dots as well as the brain’s response to music, as monitored by a set of electrodes attached to the scalp, has forced investigators to go beyond the traditional concept of complexity and to establish closer contact with the nascent field of complex networks. Complex networks form one of the most challenging areas of
Applications of Complex Networks on Analysis of World Trade Network
NASA Astrophysics Data System (ADS)
Lee, Jae Woo; Maeng, Seong Eun; Ha, Gyeong-Gyun; Hyeok Lee, Moon; Cho, Eun Seong
2013-02-01
We consider the wealth and the money flow of the world trade data. We analyze the world trade data from year 1948 to 2000 which include the total amounts of the import and export for every country per year. We apply the analyzing methods of the complex networks to the world trade network. We define the wealth as the gross domestic products (GDP) of each country. We defined the backbone network of the world trade network. We generate the backbone network keeping the link with the largest wealth flowing out each country by the import and deleting all remaining links. We observed that the wealth was transferred from the poorer countries to the wealthier countries. We found the asymmetry of the world trade flow by the disparity of the networks. From the backbone network of the world trade we can identify the regional economic connections and wealth flow among the countries.
Minimum structural controllability problems of complex networks
NASA Astrophysics Data System (ADS)
Yin, Hongli; Zhang, Siying
2016-02-01
Controllability of complex networks has been one of the attractive research areas for both network and control community, and has yielded many promising and significant results in minimum inputs and minimum driver vertices. However, few studies have been devoted to studying the minimum controlled vertex set through which control over the network with arbitrary structure can be achieved. In this paper, we prove that the minimum driver vertices driven by different inputs are not sufficient to ensure the full control of the network when the associated graph contains the inaccessible strongly connected component which has perfect matching and propose an algorithm to identify a minimum controlled vertex set for network with arbitrary structure using convenient graph and mathematical tools. And the simulation results show that the controllability of network is correlated to the number of inaccessible strongly connected components which have perfect matching and these results promote us to better understand the relationship between the network's structural characteristics and its control.
Core organization of directed complex networks
NASA Astrophysics Data System (ADS)
Azimi-Tafreshi, N.; Dorogovtsev, S. N.; Mendes, J. F. F.
2013-03-01
The recursive removal of leaves (dead end vertices) and their neighbors from an undirected network results, when this pruning algorithm stops, in a so-called core of the network. This specific subgraph should be distinguished from k-cores, which are principally different subgraphs in networks. If the vertex mean degree of a network is sufficiently large, the core is a giant cluster containing a finite fraction of vertices. We find that generalization of this pruning algorithm to directed networks provides a significantly more complex picture of cores. By implementing a rate equation approach to this pruning procedure for directed uncorrelated networks, we identify a set of cores progressively embedded into each other in a network and describe their birth points and structure.
Controlling extreme events on complex networks
NASA Astrophysics Data System (ADS)
Chen, Yu-Zhong; Huang, Zi-Gang; Lai, Ying-Cheng
2014-08-01
Extreme events, a type of collective behavior in complex networked dynamical systems, often can have catastrophic consequences. To develop effective strategies to control extreme events is of fundamental importance and practical interest. Utilizing transportation dynamics on complex networks as a prototypical setting, we find that making the network ``mobile'' can effectively suppress extreme events. A striking, resonance-like phenomenon is uncovered, where an optimal degree of mobility exists for which the probability of extreme events is minimized. We derive an analytic theory to understand the mechanism of control at a detailed and quantitative level, and validate the theory numerically. Implications of our finding to current areas such as cybersecurity are discussed.
Dynamics on Complex Networks and Applications
NASA Astrophysics Data System (ADS)
Motter, Adilson E.; Matías, Manuel A.; Kurths, Jürgen; Ott, Edward
2006-12-01
At the eight-year anniversary of Watts and Strogatz’s work on the collective dynamics of small-world networks and seven years after Barabási and Albert’s discovery of scale-free networks, the area of dynamical processes on complex networks is at the forefront of the current research on nonlinear dynamics and complex systems. This volume brings together a selection of original contributions in complementary topics of statistical physics, nonlinear dynamics and biological sciences, and is expected to provide the reader with a comprehensive up-to-date representation of this rapidly developing area.
Mapping dynamical systems onto complex networks
NASA Astrophysics Data System (ADS)
Borges, E. P.; Cajueiro, D. O.; Andrade, R. F. S.
2007-08-01
The objective of this study is to design a procedure to characterize chaotic dynamical systems, in which they are mapped onto a complex network. The nodes represent the regions of space visited by the system, while the edges represent the transitions between these regions. Parameters developed to quantify the properties of complex networks, including those related to higher order neighbourhoods, are used in the analysis. The methodology is tested on the logistic map, focusing on the onset of chaos and chaotic regimes. The corresponding networks were found to have distinct features that are associated with the particular type of dynamics that generated them.
Measurement of Online Social Networks
ERIC Educational Resources Information Center
Gjoka, Mina
2010-01-01
In recent years, the popularity of online social networks (OSN) has risen to unprecedented levels, with the most popular ones having hundreds of millions of users. This success has generated interest within the networking community and has given rise to a number of measurement and characterization studies, which provide a first step towards their…
Measuring and modeling correlations in multiplex networks.
Nicosia, Vincenzo; Latora, Vito
2015-09-01
The interactions among the elementary components of many complex systems can be qualitatively different. Such systems are therefore naturally described in terms of multiplex or multilayer networks, i.e., networks where each layer stands for a different type of interaction between the same set of nodes. There is today a growing interest in understanding when and why a description in terms of a multiplex network is necessary and more informative than a single-layer projection. Here we contribute to this debate by presenting a comprehensive study of correlations in multiplex networks. Correlations in node properties, especially degree-degree correlations, have been thoroughly studied in single-layer networks. Here we extend this idea to investigate and characterize correlations between the different layers of a multiplex network. Such correlations are intrinsically multiplex, and we first study them empirically by constructing and analyzing several multiplex networks from the real world. In particular, we introduce various measures to characterize correlations in the activity of the nodes and in their degree at the different layers and between activities and degrees. We show that real-world networks exhibit indeed nontrivial multiplex correlations. For instance, we find cases where two layers of the same multiplex network are positively correlated in terms of node degrees, while other two layers are negatively correlated. We then focus on constructing synthetic multiplex networks, proposing a series of models to reproduce the correlations observed empirically and/or to assess their relevance. PMID:26465526
Measuring and modeling correlations in multiplex networks
NASA Astrophysics Data System (ADS)
Nicosia, Vincenzo; Latora, Vito
2015-09-01
The interactions among the elementary components of many complex systems can be qualitatively different. Such systems are therefore naturally described in terms of multiplex or multilayer networks, i.e., networks where each layer stands for a different type of interaction between the same set of nodes. There is today a growing interest in understanding when and why a description in terms of a multiplex network is necessary and more informative than a single-layer projection. Here we contribute to this debate by presenting a comprehensive study of correlations in multiplex networks. Correlations in node properties, especially degree-degree correlations, have been thoroughly studied in single-layer networks. Here we extend this idea to investigate and characterize correlations between the different layers of a multiplex network. Such correlations are intrinsically multiplex, and we first study them empirically by constructing and analyzing several multiplex networks from the real world. In particular, we introduce various measures to characterize correlations in the activity of the nodes and in their degree at the different layers and between activities and degrees. We show that real-world networks exhibit indeed nontrivial multiplex correlations. For instance, we find cases where two layers of the same multiplex network are positively correlated in terms of node degrees, while other two layers are negatively correlated. We then focus on constructing synthetic multiplex networks, proposing a series of models to reproduce the correlations observed empirically and/or to assess their relevance.
Constant Communities in Complex Networks
NASA Astrophysics Data System (ADS)
Chakraborty, Tanmoy; Srinivasan, Sriram; Ganguly, Niloy; Bhowmick, Sanjukta; Mukherjee, Animesh
2013-05-01
Identifying community structure is a fundamental problem in network analysis. Most community detection algorithms are based on optimizing a combinatorial parameter, for example modularity. This optimization is generally NP-hard, thus merely changing the vertex order can alter their assignments to the community. However, there has been less study on how vertex ordering influences the results of the community detection algorithms. Here we identify and study the properties of invariant groups of vertices (constant communities) whose assignment to communities are, quite remarkably, not affected by vertex ordering. The percentage of constant communities can vary across different applications and based on empirical results we propose metrics to evaluate these communities. Using constant communities as a pre-processing step, one can significantly reduce the variation of the results. Finally, we present a case study on phoneme network and illustrate that constant communities, quite strikingly, form the core functional units of the larger communities.
Analysis of complex networks using aggressive abstraction.
Colbaugh, Richard; Glass, Kristin.; Willard, Gerald
2008-10-01
This paper presents a new methodology for analyzing complex networks in which the network of interest is first abstracted to a much simpler (but equivalent) representation, the required analysis is performed using the abstraction, and analytic conclusions are then mapped back to the original network and interpreted there. We begin by identifying a broad and important class of complex networks which admit abstractions that are simultaneously dramatically simplifying and property preserving - we call these aggressive abstractions -- and which can therefore be analyzed using the proposed approach. We then introduce and develop two forms of aggressive abstraction: 1.) finite state abstraction, in which dynamical networks with uncountable state spaces are modeled using finite state systems, and 2.) onedimensional abstraction, whereby high dimensional network dynamics are captured in a meaningful way using a single scalar variable. In each case, the property preserving nature of the abstraction process is rigorously established and efficient algorithms are presented for computing the abstraction. The considerable potential of the proposed approach to complex networks analysis is illustrated through case studies involving vulnerability analysis of technological networks and predictive analysis for social processes.
Experimental flux measurements on a network scale
Schwender, J.
2011-10-11
Metabolic flux is a fundamental property of living organisms. In recent years, methods for measuring metabolic flux in plants on a network scale have evolved further. One major challenge in studying flux in plants is the complexity of the plant's metabolism. In particular, in the presence of parallel pathways in multiple cellular compartments, the core of plant central metabolism constitutes a complex network. Hence, a common problem with the reliability of the contemporary results of {sup 13}C-Metabolic Flux Analysis in plants is the substantial reduction in complexity that must be included in the simulated networks; this omission partly is due to limitations in computational simulations. Here, I discuss recent emerging strategies that will better address these shortcomings.
The price of complexity in financial networks.
Battiston, Stefano; Caldarelli, Guido; May, Robert M; Roukny, Tarik; Stiglitz, Joseph E
2016-09-01
Financial institutions form multilayer networks by engaging in contracts with each other and by holding exposures to common assets. As a result, the default probability of one institution depends on the default probability of all of the other institutions in the network. Here, we show how small errors on the knowledge of the network of contracts can lead to large errors in the probability of systemic defaults. From the point of view of financial regulators, our findings show that the complexity of financial networks may decrease the ability to mitigate systemic risk, and thus it may increase the social cost of financial crises. PMID:27555583
Travel and tourism: Into a complex network
NASA Astrophysics Data System (ADS)
Miguéns, J. I. L.; Mendes, J. F. F.
2008-05-01
It is discussed how the worldwide tourist arrivals, about 10% of the world’s domestic product, form a largely heterogeneous and directed complex network. Remarkably the random network of connectivity is converted into a scale-free network of intensities. The importance of weights on network connections is brought into discussion. It is also shown how strategic positioning particularly benefits from market diversity and that interactions among countries prevail on a technological and economic pattern, questioning the backbone of driving forces in traveling.
Quantum navigation and ranking in complex networks.
Sánchez-Burillo, Eduardo; Duch, Jordi; Gómez-Gardeñes, Jesús; Zueco, David
2012-01-01
Complex networks are formal frameworks capturing the interdependencies between the elements of large systems and databases. This formalism allows to use network navigation methods to rank the importance that each constituent has on the global organization of the system. A key example is Pagerank navigation which is at the core of the most used search engine of the World Wide Web. Inspired in this classical algorithm, we define a quantum navigation method providing a unique ranking of the elements of a network. We analyze the convergence of quantum navigation to the stationary rank of networks and show that quantumness decreases the number of navigation steps before convergence. In addition, we show that quantum navigation allows to solve degeneracies found in classical ranks. By implementing the quantum algorithm in real networks, we confirm these improvements and show that quantum coherence unveils new hierarchical features about the global organization of complex systems. PMID:22930671
Quantum Navigation and Ranking in Complex Networks
Sánchez-Burillo, Eduardo; Duch, Jordi; Gómez-Gardeñes, Jesús; Zueco, David
2012-01-01
Complex networks are formal frameworks capturing the interdependencies between the elements of large systems and databases. This formalism allows to use network navigation methods to rank the importance that each constituent has on the global organization of the system. A key example is Pagerank navigation which is at the core of the most used search engine of the World Wide Web. Inspired in this classical algorithm, we define a quantum navigation method providing a unique ranking of the elements of a network. We analyze the convergence of quantum navigation to the stationary rank of networks and show that quantumness decreases the number of navigation steps before convergence. In addition, we show that quantum navigation allows to solve degeneracies found in classical ranks. By implementing the quantum algorithm in real networks, we confirm these improvements and show that quantum coherence unveils new hierarchical features about the global organization of complex systems. PMID:22930671
Shock waves on complex networks
Mones, Enys; Araújo, Nuno A. M.; Vicsek, Tamás; Herrmann, Hans J.
2014-01-01
Power grids, road maps, and river streams are examples of infrastructural networks which are highly vulnerable to external perturbations. An abrupt local change of load (voltage, traffic density, or water level) might propagate in a cascading way and affect a significant fraction of the network. Almost discontinuous perturbations can be modeled by shock waves which can eventually interfere constructively and endanger the normal functionality of the infrastructure. We study their dynamics by solving the Burgers equation under random perturbations on several real and artificial directed graphs. Even for graphs with a narrow distribution of node properties (e.g., degree or betweenness), a steady state is reached exhibiting a heterogeneous load distribution, having a difference of one order of magnitude between the highest and average loads. Unexpectedly we find for the European power grid and for finite Watts-Strogatz networks a broad pronounced bimodal distribution for the loads. To identify the most vulnerable nodes, we introduce the concept of node-basin size, a purely topological property which we show to be strongly correlated to the average load of a node. PMID:24821422
Shock waves on complex networks.
Mones, Enys; Araújo, Nuno A M; Vicsek, Tamás; Herrmann, Hans J
2014-01-01
Power grids, road maps, and river streams are examples of infrastructural networks which are highly vulnerable to external perturbations. An abrupt local change of load (voltage, traffic density, or water level) might propagate in a cascading way and affect a significant fraction of the network. Almost discontinuous perturbations can be modeled by shock waves which can eventually interfere constructively and endanger the normal functionality of the infrastructure. We study their dynamics by solving the Burgers equation under random perturbations on several real and artificial directed graphs. Even for graphs with a narrow distribution of node properties (e.g., degree or betweenness), a steady state is reached exhibiting a heterogeneous load distribution, having a difference of one order of magnitude between the highest and average loads. Unexpectedly we find for the European power grid and for finite Watts-Strogatz networks a broad pronounced bimodal distribution for the loads. To identify the most vulnerable nodes, we introduce the concept of node-basin size, a purely topological property which we show to be strongly correlated to the average load of a node. PMID:24821422
Cascade defense via routing in complex networks
NASA Astrophysics Data System (ADS)
Xu, Xiao-Lan; Du, Wen-Bo; Hong, Chen
2015-05-01
As the cascading failures in networked traffic systems are becoming more and more serious, research on cascade defense in complex networks has become a hotspot in recent years. In this paper, we propose a traffic-based cascading failure model, in which each packet in the network has its own source and destination. When cascade is triggered, packets will be redistributed according to a given routing strategy. Here, a global hybrid (GH) routing strategy, which uses the dynamic information of the queue length and the static information of nodes' degree, is proposed to defense the network cascade. Comparing GH strategy with the shortest path (SP) routing, efficient routing (ER) and global dynamic (GD) routing strategies, we found that GH strategy is more effective than other routing strategies in improving the network robustness against cascading failures. Our work provides insight into the robustness of networked traffic systems.
Network model of bilateral power markets based on complex networks
NASA Astrophysics Data System (ADS)
Wu, Yang; Liu, Junyong; Li, Furong; Yan, Zhanxin; Zhang, Li
2014-06-01
The bilateral power transaction (BPT) mode becomes a typical market organization with the restructuring of electric power industry, the proper model which could capture its characteristics is in urgent need. However, the model is lacking because of this market organization's complexity. As a promising approach to modeling complex systems, complex networks could provide a sound theoretical framework for developing proper simulation model. In this paper, a complex network model of the BPT market is proposed. In this model, price advantage mechanism is a precondition. Unlike other general commodity transactions, both of the financial layer and the physical layer are considered in the model. Through simulation analysis, the feasibility and validity of the model are verified. At same time, some typical statistical features of BPT network are identified. Namely, the degree distribution follows the power law, the clustering coefficient is low and the average path length is a bit long. Moreover, the topological stability of the BPT network is tested. The results show that the network displays a topological robustness to random market member's failures while it is fragile against deliberate attacks, and the network could resist cascading failure to some extent. These features are helpful for making decisions and risk management in BPT markets.
Opinion control in complex networks
NASA Astrophysics Data System (ADS)
Masuda, Naoki
2015-03-01
In many political elections, the electorate appears to be a composite of partisan and independent voters. Given that partisans are not likely to convert to a different party, an important goal for a political party could be to mobilize independent voters toward the party with the help of strong leadership, mass media, partisans, and the effects of peer-to-peer influence. Based on the exact solution of classical voter model dynamics in the presence of perfectly partisan voters (i.e., zealots), we propose a computational method that uses pinning control strategy to maximize the share of a party in a social network of independent voters. The party, corresponding to the controller or zealots, optimizes the nodes to be controlled given the information about the connectivity of independent voters and the set of nodes that the opposing party controls. We show that controlling hubs is generally a good strategy, but the optimized strategy is even better. The superiority of the optimized strategy is particularly eminent when the independent voters are connected as directed (rather than undirected) networks.
The architecture of complex weighted networks
Barrat, A.; Barthélemy, M.; Pastor-Satorras, R.; Vespignani, A.
2004-01-01
Networked structures arise in a wide array of different contexts such as technological and transportation infrastructures, social phenomena, and biological systems. These highly interconnected systems have recently been the focus of a great deal of attention that has uncovered and characterized their topological complexity. Along with a complex topological structure, real networks display a large heterogeneity in the capacity and intensity of the connections. These features, however, have mainly not been considered in past studies where links are usually represented as binary states, i.e., either present or absent. Here, we study the scientific collaboration network and the world-wide air-transportation network, which are representative examples of social and large infrastructure systems, respectively. In both cases it is possible to assign to each edge of the graph a weight proportional to the intensity or capacity of the connections among the various elements of the network. We define appropriate metrics combining weighted and topological observables that enable us to characterize the complex statistical properties and heterogeneity of the actual strength of edges and vertices. This information allows us to investigate the correlations among weighted quantities and the underlying topological structure of the network. These results provide a better description of the hierarchies and organizational principles at the basis of the architecture of weighted networks. PMID:15007165
Contagion on complex networks with persuasion.
Huang, Wei-Min; Zhang, Li-Jie; Xu, Xin-Jian; Fu, Xinchu
2016-01-01
The threshold model has been widely adopted as a classic model for studying contagion processes on social networks. We consider asymmetric individual interactions in social networks and introduce a persuasion mechanism into the threshold model. Specifically, we study a combination of adoption and persuasion in cascading processes on complex networks. It is found that with the introduction of the persuasion mechanism, the system may become more vulnerable to global cascades, and the effects of persuasion tend to be more significant in heterogeneous networks than those in homogeneous networks: a comparison between heterogeneous and homogeneous networks shows that under weak persuasion, heterogeneous networks tend to be more robust against random shocks than homogeneous networks; whereas under strong persuasion, homogeneous networks are more stable. Finally, we study the effects of adoption and persuasion threshold heterogeneity on systemic stability. Though both heterogeneities give rise to global cascades, the adoption heterogeneity has an overwhelmingly stronger impact than the persuasion heterogeneity when the network connectivity is sufficiently dense. PMID:27029498
Assembly of complex plant–fungus networks
Toju, Hirokazu; Guimarães, Paulo R.; Olesen, Jens M.; Thompson, John N.
2014-01-01
Species in ecological communities build complex webs of interaction. Although revealing the architecture of these networks is fundamental to understanding ecological and evolutionary dynamics in nature, it has been difficult to characterize the structure of most species-rich ecological systems. By overcoming this limitation through next-generation sequencing technology, we herein uncover the network architecture of below-ground plant–fungus symbioses, which are ubiquitous to terrestrial ecosystems. The examined symbiotic network of a temperate forest in Japan includes 33 plant species and 387 functionally and phylogenetically diverse fungal taxa, and the overall network architecture differs fundamentally from that of other ecological networks. In contrast to results for other ecological networks and theoretical predictions for symbiotic networks, the plant–fungus network shows moderate or relatively low levels of interaction specialization and modularity and an unusual pattern of ‘nested’ network architecture. These results suggest that species-rich ecological networks are more architecturally diverse than previously recognized. PMID:25327887
Contagion on complex networks with persuasion
Huang, Wei-Min; Zhang, Li-Jie; Xu, Xin-Jian; Fu, Xinchu
2016-01-01
The threshold model has been widely adopted as a classic model for studying contagion processes on social networks. We consider asymmetric individual interactions in social networks and introduce a persuasion mechanism into the threshold model. Specifically, we study a combination of adoption and persuasion in cascading processes on complex networks. It is found that with the introduction of the persuasion mechanism, the system may become more vulnerable to global cascades, and the effects of persuasion tend to be more significant in heterogeneous networks than those in homogeneous networks: a comparison between heterogeneous and homogeneous networks shows that under weak persuasion, heterogeneous networks tend to be more robust against random shocks than homogeneous networks; whereas under strong persuasion, homogeneous networks are more stable. Finally, we study the effects of adoption and persuasion threshold heterogeneity on systemic stability. Though both heterogeneities give rise to global cascades, the adoption heterogeneity has an overwhelmingly stronger impact than the persuasion heterogeneity when the network connectivity is sufficiently dense. PMID:27029498
Robust Reconstruction of Complex Networks from Sparse Data
NASA Astrophysics Data System (ADS)
Han, Xiao; Shen, Zhesi; Wang, Wen-Xu; Di, Zengru
2015-01-01
Reconstructing complex networks from measurable data is a fundamental problem for understanding and controlling collective dynamics of complex networked systems. However, a significant challenge arises when we attempt to decode structural information hidden in limited amounts of data accompanied by noise and in the presence of inaccessible nodes. Here, we develop a general framework for robust reconstruction of complex networks from sparse and noisy data. Specifically, we decompose the task of reconstructing the whole network into recovering local structures centered at each node. Thus, the natural sparsity of complex networks ensures a conversion from the local structure reconstruction into a sparse signal reconstruction problem that can be addressed by using the lasso, a convex optimization method. We apply our method to evolutionary games, transportation, and communication processes taking place in a variety of model and real complex networks, finding that universal high reconstruction accuracy can be achieved from sparse data in spite of noise in time series and missing data of partial nodes. Our approach opens new routes to the network reconstruction problem and has potential applications in a wide range of fields.
Analytical and experimental study on complex compressed air pipe network
NASA Astrophysics Data System (ADS)
Gai, Yushou; Cai, Maolin; Shi, Yan
2015-09-01
To analyze the working characteristics of complex compressed air networks, numerical methods are widely used which are based on finite element technology or intelligent algorithms. However, the effectiveness of the numerical methods is limited. In this paper, to provide a new method to optimize the design and the air supply strategy of the complex compressed air pipe network, firstly, a novel method to analyze the topology structure of the compressed air flow in the pipe network is initially proposed. A matrix is used to describe the topology structure of the compressed air flow. Moreover, based on the analysis of the pressure loss of the pipe network, the relationship between the pressure and the flow of the compressed air is derived, and a prediction method of pressure fluctuation and air flow in a segment in a complex pipe network is proposed. Finally, to inspect the effectiveness of the method, an experiment with a complex network is designed. The pressure and the flow of airflow in the network are measured and studied. The results of the study show that, the predicted results with the proposed method have a good consistency with the experimental results, and that verifies the air flow prediction method of the complex pipe network. This research proposes a new method to analyze the compressed air network and a prediction method of pressure fluctuation and air flow in a segment, which can predicate the fluctuation of the pressure according to the flow of compressed air, and predicate the fluctuation of the flow according to the pressure in a segment of a complex pipe network.
Self-determined mechanisms in complex networks
NASA Astrophysics Data System (ADS)
Liu, Yang; Yuan, Jian; Shan, Xiuming; Ren, Yong; Ma, Zhengxin
2008-03-01
Self-organized networks are pervasive in communication systems such as the Internet, overlay networks, peer-to-peer networks, and cluster-based services. These networks evolve into complex topologies, under specific driving forces, i.e. user demands, technological innovations, design objectives and so on. Our study focuses on the driving forces behind individual evolutions of network components, and their stimulation and domination to the self-organized networks which are defined as self-determined mechanisms in this paper. Understanding forces underlying the evolution of networks should enable informed design decisions and help to avoid unwanted surprises, such as congestion collapse. A case study on the macroscopic evolution of the Internet topology of autonomous systems under a specific driving force is then presented. Using computer simulations, it is found that the power-law degree distribution can originate from a connection preference to larger numbers of users, and that the small-world property can be caused by rapid growth in the number of users. Our results provide a new feasible perspective to understand intrinsic fundamentals in the topological evolution of complex networks.
Self-organized topology of recurrence-based complex networks
Yang, Hui Liu, Gang
2013-12-15
With the rapid technological advancement, network is almost everywhere in our daily life. Network theory leads to a new way to investigate the dynamics of complex systems. As a result, many methods are proposed to construct a network from nonlinear time series, including the partition of state space, visibility graph, nearest neighbors, and recurrence approaches. However, most previous works focus on deriving the adjacency matrix to represent the complex network and extract new network-theoretic measures. Although the adjacency matrix provides connectivity information of nodes and edges, the network geometry can take variable forms. The research objective of this article is to develop a self-organizing approach to derive the steady geometric structure of a network from the adjacency matrix. We simulate the recurrence network as a physical system by treating the edges as springs and the nodes as electrically charged particles. Then, force-directed algorithms are developed to automatically organize the network geometry by minimizing the system energy. Further, a set of experiments were designed to investigate important factors (i.e., dynamical systems, network construction methods, force-model parameter, nonhomogeneous distribution) affecting this self-organizing process. Interestingly, experimental results show that the self-organized geometry recovers the attractor of a dynamical system that produced the adjacency matrix. This research addresses a question, i.e., “what is the self-organizing geometry of a recurrence network?” and provides a new way to reproduce the attractor or time series from the recurrence plot. As a result, novel network-theoretic measures (e.g., average path length and proximity ratio) can be achieved based on actual node-to-node distances in the self-organized network topology. The paper brings the physical models into the recurrence analysis and discloses the spatial geometry of recurrence networks.
Self-organized topology of recurrence-based complex networks
NASA Astrophysics Data System (ADS)
Yang, Hui; Liu, Gang
2013-12-01
With the rapid technological advancement, network is almost everywhere in our daily life. Network theory leads to a new way to investigate the dynamics of complex systems. As a result, many methods are proposed to construct a network from nonlinear time series, including the partition of state space, visibility graph, nearest neighbors, and recurrence approaches. However, most previous works focus on deriving the adjacency matrix to represent the complex network and extract new network-theoretic measures. Although the adjacency matrix provides connectivity information of nodes and edges, the network geometry can take variable forms. The research objective of this article is to develop a self-organizing approach to derive the steady geometric structure of a network from the adjacency matrix. We simulate the recurrence network as a physical system by treating the edges as springs and the nodes as electrically charged particles. Then, force-directed algorithms are developed to automatically organize the network geometry by minimizing the system energy. Further, a set of experiments were designed to investigate important factors (i.e., dynamical systems, network construction methods, force-model parameter, nonhomogeneous distribution) affecting this self-organizing process. Interestingly, experimental results show that the self-organized geometry recovers the attractor of a dynamical system that produced the adjacency matrix. This research addresses a question, i.e., "what is the self-organizing geometry of a recurrence network?" and provides a new way to reproduce the attractor or time series from the recurrence plot. As a result, novel network-theoretic measures (e.g., average path length and proximity ratio) can be achieved based on actual node-to-node distances in the self-organized network topology. The paper brings the physical models into the recurrence analysis and discloses the spatial geometry of recurrence networks.
Aging in complex interdependency networks.
Vural, Dervis C; Morrison, Greg; Mahadevan, L
2014-02-01
Although species longevity is subject to a diverse range of evolutionary forces, the mortality curves of a wide variety of organisms are rather similar. Here we argue that qualitative and quantitative features of aging can be reproduced by a simple model based on the interdependence of fault-prone agents on one other. In addition to fitting our theory to the empiric mortality curves of six very different organisms, we establish the dependence of lifetime and aging rate on initial conditions, damage and repair rate, and system size. We compare the size distributions of disease and death and see that they have qualitatively different properties. We show that aging patterns are independent of the details of interdependence network structure, which suggests that aging is a many-body effect, and that the qualitative and quantitative features of aging are not sensitively dependent on the details of dependency structure or its formation. PMID:25353538
Social networks as embedded complex adaptive systems.
Benham-Hutchins, Marge; Clancy, Thomas R
2010-09-01
As systems evolve over time, their natural tendency is to become increasingly more complex. Studies in the field of complex systems have generated new perspectives on management in social organizations such as hospitals. Much of this research appears as a natural extension of the cross-disciplinary field of systems theory. This is the 15th in a series of articles applying complex systems science to the traditional management concepts of planning, organizing, directing, coordinating, and controlling. In this article, the authors discuss healthcare social networks as a hierarchy of embedded complex adaptive systems. The authors further examine the use of social network analysis tools as a means to understand complex communication patterns and reduce medical errors. PMID:20798616
Complex Dynamics in Information Sharing Networks
NASA Astrophysics Data System (ADS)
Cronin, Bruce
This study examines the roll-out of an electronic knowledge base in a medium-sized professional services firm over a six year period. The efficiency of such implementation is a key business problem in IT systems of this type. Data from usage logs provides the basis for analysis of the dynamic evolution of social networks around the depository during this time. The adoption pattern follows an "s-curve" and usage exhibits something of a power law distribution, both attributable to network effects, and network position is associated with organisational performance on a number of indicators. But periodicity in usage is evident and the usage distribution displays an exponential cut-off. Further analysis provides some evidence of mathematical complexity in the periodicity. Some implications of complex patterns in social network data for research and management are discussed. The study provides a case study demonstrating the utility of the broad methodological approach.
Predictive Control of Large Complex Networks
NASA Astrophysics Data System (ADS)
Haber, Aleksandar; Motter, Adilson E.
Networks of coupled dynamical subsystems are increasingly used to represent complex natural and engineered systems. While recent technological developments give us improved means to actively control the dynamics of individual subsystems in various domains, network control remains a challenging problem due to difficulties imposed by intrinsic nonlinearities, control constraints, and the large-scale nature of the systems. In this talk, we will present a model predictive control approach that is effective while accounting for these realistic properties of complex networks. Our method can systematically identify control interventions that steer the trajectory to a desired state, even in the presence of strong nonlinearities and constraints. Numerical tests show that the method is applicable to a variety of networks, ranging from power grids to chemical reaction systems.
Micro-macro analysis of complex networks.
Marchiori, Massimo; Possamai, Lino
2015-01-01
Complex systems have attracted considerable interest because of their wide range of applications, and are often studied via a "classic" approach: study a specific system, find a complex network behind it, and analyze the corresponding properties. This simple methodology has produced a great deal of interesting results, but relies on an often implicit underlying assumption: the level of detail on which the system is observed. However, in many situations, physical or abstract, the level of detail can be one out of many, and might also depend on intrinsic limitations in viewing the data with a different level of abstraction or precision. So, a fundamental question arises: do properties of a network depend on its level of observability, or are they invariant? If there is a dependence, then an apparently correct network modeling could in fact just be a bad approximation of the true behavior of a complex system. In order to answer this question, we propose a novel micro-macro analysis of complex systems that quantitatively describes how the structure of complex networks varies as a function of the detail level. To this extent, we have developed a new telescopic algorithm that abstracts from the local properties of a system and reconstructs the original structure according to a fuzziness level. This way we can study what happens when passing from a fine level of detail ("micro") to a different scale level ("macro"), and analyze the corresponding behavior in this transition, obtaining a deeper spectrum analysis. The obtained results show that many important properties are not universally invariant with respect to the level of detail, but instead strongly depend on the specific level on which a network is observed. Therefore, caution should be taken in every situation where a complex network is considered, if its context allows for different levels of observability. PMID:25635812
Micro-Macro Analysis of Complex Networks
Marchiori, Massimo; Possamai, Lino
2015-01-01
Complex systems have attracted considerable interest because of their wide range of applications, and are often studied via a “classic” approach: study a specific system, find a complex network behind it, and analyze the corresponding properties. This simple methodology has produced a great deal of interesting results, but relies on an often implicit underlying assumption: the level of detail on which the system is observed. However, in many situations, physical or abstract, the level of detail can be one out of many, and might also depend on intrinsic limitations in viewing the data with a different level of abstraction or precision. So, a fundamental question arises: do properties of a network depend on its level of observability, or are they invariant? If there is a dependence, then an apparently correct network modeling could in fact just be a bad approximation of the true behavior of a complex system. In order to answer this question, we propose a novel micro-macro analysis of complex systems that quantitatively describes how the structure of complex networks varies as a function of the detail level. To this extent, we have developed a new telescopic algorithm that abstracts from the local properties of a system and reconstructs the original structure according to a fuzziness level. This way we can study what happens when passing from a fine level of detail (“micro”) to a different scale level (“macro”), and analyze the corresponding behavior in this transition, obtaining a deeper spectrum analysis. The obtained results show that many important properties are not universally invariant with respect to the level of detail, but instead strongly depend on the specific level on which a network is observed. Therefore, caution should be taken in every situation where a complex network is considered, if its context allows for different levels of observability. PMID:25635812
Structurally robust control of complex networks
NASA Astrophysics Data System (ADS)
Nacher, Jose C.; Akutsu, Tatsuya
2015-01-01
Robust control theory has been successfully applied to numerous real-world problems using a small set of devices called controllers. However, the real systems represented by networks contain unreliable components and modern robust control engineering has not addressed the problem of structural changes on complex networks including scale-free topologies. Here, we introduce the concept of structurally robust control of complex networks and provide a concrete example using an algorithmic framework that is widely applied in engineering. The developed analytical tools, computer simulations, and real network analyses lead herein to the discovery that robust control can be achieved in scale-free networks with exactly the same order of controllers required in a standard nonrobust configuration by adjusting only the minimum degree. The presented methodology also addresses the probabilistic failure of links in real systems, such as neural synaptic unreliability in Caenorhabditis elegans, and suggests a new direction to pursue in studies of complex networks in which control theory has a role.
Structurally robust control of complex networks.
Nacher, Jose C; Akutsu, Tatsuya
2015-01-01
Robust control theory has been successfully applied to numerous real-world problems using a small set of devices called controllers. However, the real systems represented by networks contain unreliable components and modern robust control engineering has not addressed the problem of structural changes on complex networks including scale-free topologies. Here, we introduce the concept of structurally robust control of complex networks and provide a concrete example using an algorithmic framework that is widely applied in engineering. The developed analytical tools, computer simulations, and real network analyses lead herein to the discovery that robust control can be achieved in scale-free networks with exactly the same order of controllers required in a standard nonrobust configuration by adjusting only the minimum degree. The presented methodology also addresses the probabilistic failure of links in real systems, such as neural synaptic unreliability in Caenorhabditis elegans, and suggests a new direction to pursue in studies of complex networks in which control theory has a role. PMID:25679675
Size reduction of complex networks preserving modularity
Arenas, A.; Duch, J.; Fernandez, A.; Gomez, S.
2008-12-24
The ubiquity of modular structure in real-world complex networks is being the focus of attention in many trials to understand the interplay between network topology and functionality. The best approaches to the identification of modular structure are based on the optimization of a quality function known as modularity. However this optimization is a hard task provided that the computational complexity of the problem is in the NP-hard class. Here we propose an exact method for reducing the size of weighted (directed and undirected) complex networks while maintaining invariant its modularity. This size reduction allows the heuristic algorithms that optimize modularity for a better exploration of the modularity landscape. We compare the modularity obtained in several real complex-networks by using the Extremal Optimization algorithm, before and after the size reduction, showing the improvement obtained. We speculate that the proposed analytical size reduction could be extended to an exact coarse graining of the network in the scope of real-space renormalization.
Identifying community structure in complex networks
NASA Astrophysics Data System (ADS)
Shao, Chenxi; Duan, Yubing
2015-07-01
A wide variety of applications could be formulated to resolve the problem of finding all communities from a given network, ranging from social and biological network analysis to web mining and searching. In this study, we propose the concept of virtual attractive strength between each pair of node in networks, and then give the definition of community structure based on the proposed attractive strength. Furthermore, we present a community detection method by moving vertices to the clusters that produce the largest attractive strengths to them until the division of network reaches unchanged. Experimental results on synthetic and real networks indicate that the proposed approach has favorite effectiveness and fast convergence speed, which provides an efficient method for exploring and analyzing complex systems.
Characterizing English Poetic Style Using Complex Networks
NASA Astrophysics Data System (ADS)
Roxas-Villanueva, Ranzivelle Marianne; Nambatac, Maelori Krista; Tapang, Giovanni
Complex networks have been proven useful in characterizing written texts. Here, we use networks to probe if there exist a similarity within, and difference across, era as reflected within the poem's structure. In literary history, boundary lines are set to distinguish the change in writing styles through time. We obtain the network parameters and motif frequencies of 845 poems published from 1522 to 1931 and relate this to the writing of the Elizabethan, 17th Century, Augustan, Romantic and Victorian eras. Analysis of the different network parameters shows a significant difference of the Augustan era (1667-1780) with the rest. The network parameters and the convex hull and centroids of the motif frequencies reflect the adjectival sequence pattern of the poems of the Augustan era.
Cascade control and defense in complex networks.
Motter, Adilson E
2004-08-27
Complex networks with a heterogeneous distribution of loads may undergo a global cascade of overload failures when highly loaded nodes or edges are removed due to attacks or failures. Since a small attack or failure has the potential to trigger a global cascade, a fundamental question regards the possible strategies of defense to prevent the cascade from propagating through the entire network. Here we introduce and investigate a costless strategy of defense based on a selective further removal of nodes and edges, right after the initial attack or failure. This intentional removal of network elements is shown to drastically reduce the size of the cascade. PMID:15447153
Complex root networks of Chinese characters
NASA Astrophysics Data System (ADS)
Lee, Po-Han; Chen, Jia-Ling; Wang, Po-Cheng; Chi, Ting-Ting; Xiao, Zhi-Ren; Jhang, Zih-Jian; Yeh, Yeong-Nan; Chen, Yih-Yuh; Hu, Chin-Kun
There are several sets of Chinese characters still available today, including Oracle Bone Inscriptions (OBI) in Shang Dynasty, Chu characters (CC) used in Chu of Warring State Period, Small Seal Script in dictionary Shuowen Jiezi (SJ) in Eastern Han Dynasty, and Kangxi Dictionary (KD) in Qing Dynasty. Such as Chinese characters were all constructed via combinations of meaningful patterns, called roots. Our studies for the complex networks of all roots indicate that the roots of the characters in OBI, CC, SJ and KD have characteristics of small world networks and scale-free networks.
An improved sampling method of complex network
NASA Astrophysics Data System (ADS)
Gao, Qi; Ding, Xintong; Pan, Feng; Li, Weixing
2014-12-01
Sampling subnet is an important topic of complex network research. Sampling methods influence the structure and characteristics of subnet. Random multiple snowball with Cohen (RMSC) process sampling which combines the advantages of random sampling and snowball sampling is proposed in this paper. It has the ability to explore global information and discover the local structure at the same time. The experiments indicate that this novel sampling method could keep the similarity between sampling subnet and original network on degree distribution, connectivity rate and average shortest path. This method is applicable to the situation where the prior knowledge about degree distribution of original network is not sufficient.
NEXCADE: perturbation analysis for complex networks.
Yadav, Gitanjali; Babu, Suresh
2012-01-01
Recent advances in network theory have led to considerable progress in our understanding of complex real world systems and their behavior in response to external threats or fluctuations. Much of this research has been invigorated by demonstration of the 'robust, yet fragile' nature of cellular and large-scale systems transcending biology, sociology, and ecology, through application of the network theory to diverse interactions observed in nature such as plant-pollinator, seed-dispersal agent and host-parasite relationships. In this work, we report the development of NEXCADE, an automated and interactive program for inducing disturbances into complex systems defined by networks, focusing on the changes in global network topology and connectivity as a function of the perturbation. NEXCADE uses a graph theoretical approach to simulate perturbations in a user-defined manner, singly, in clusters, or sequentially. To demonstrate the promise it holds for broader adoption by the research community, we provide pre-simulated examples from diverse real-world networks including eukaryotic protein-protein interaction networks, fungal biochemical networks, a variety of ecological food webs in nature as well as social networks. NEXCADE not only enables network visualization at every step of the targeted attacks, but also allows risk assessment, i.e. identification of nodes critical for the robustness of the system of interest, in order to devise and implement context-based strategies for restructuring a network, or to achieve resilience against link or node failures. Source code and license for the software, designed to work on a Linux-based operating system (OS) can be downloaded at http://www.nipgr.res.in/nexcade_download.html. In addition, we have developed NEXCADE as an OS-independent online web server freely available to the scientific community without any login requirement at http://www.nipgr.res.in/nexcade.html. PMID:22870252
NEXCADE: Perturbation Analysis for Complex Networks
Yadav, Gitanjali; Babu, Suresh
2012-01-01
Recent advances in network theory have led to considerable progress in our understanding of complex real world systems and their behavior in response to external threats or fluctuations. Much of this research has been invigorated by demonstration of the ‘robust, yet fragile’ nature of cellular and large-scale systems transcending biology, sociology, and ecology, through application of the network theory to diverse interactions observed in nature such as plant-pollinator, seed-dispersal agent and host-parasite relationships. In this work, we report the development of NEXCADE, an automated and interactive program for inducing disturbances into complex systems defined by networks, focusing on the changes in global network topology and connectivity as a function of the perturbation. NEXCADE uses a graph theoretical approach to simulate perturbations in a user-defined manner, singly, in clusters, or sequentially. To demonstrate the promise it holds for broader adoption by the research community, we provide pre-simulated examples from diverse real-world networks including eukaryotic protein-protein interaction networks, fungal biochemical networks, a variety of ecological food webs in nature as well as social networks. NEXCADE not only enables network visualization at every step of the targeted attacks, but also allows risk assessment, i.e. identification of nodes critical for the robustness of the system of interest, in order to devise and implement context-based strategies for restructuring a network, or to achieve resilience against link or node failures. Source code and license for the software, designed to work on a Linux-based operating system (OS) can be downloaded at http://www.nipgr.res.in/nexcade_download.html. In addition, we have developed NEXCADE as an OS-independent online web server freely available to the scientific community without any login requirement at http://www.nipgr.res.in/nexcade.html. PMID:22870252
Collective chaos induced by structures of complex networks
NASA Astrophysics Data System (ADS)
Yang, Huijie; Zhao, Fangcui; Wang, Binghong
2006-05-01
Mapping a complex network of N coupled identical oscillators to a quantum system, the nearest neighbor level spacing (NNLS) distribution is used to identify collective chaos in the corresponding classical dynamics on the complex network. The classical dynamics on an Erdos-Renyi network with the wiring probability pER⩽1/N is in the state of collective order, while that on an Erdos-Renyi network with pER>1/N in the state of collective chaos. The dynamics on a WS Small-world complex network evolves from collective order to collective chaos rapidly in the region of the rewiring probability pr∈[0.0,0.1], and then keeps chaotic up to pr=1.0. The dynamics on a Growing Random Network (GRN) is in a special state deviates from order significantly in a way opposite to that on WS small-world networks. Each network can be measured by a couple values of two parameters (β,η).
Extractive summarization using complex networks and syntactic dependency
NASA Astrophysics Data System (ADS)
Amancio, Diego R.; Nunes, Maria G. V.; Oliveira, Osvaldo N.; Costa, Luciano da F.
2012-02-01
The realization that statistical physics methods can be applied to analyze written texts represented as complex networks has led to several developments in natural language processing, including automatic summarization and evaluation of machine translation. Most importantly, so far only a few metrics of complex networks have been used and therefore there is ample opportunity to enhance the statistics-based methods as new measures of network topology and dynamics are created. In this paper, we employ for the first time the metrics betweenness, vulnerability and diversity to analyze written texts in Brazilian Portuguese. Using strategies based on diversity metrics, a better performance in automatic summarization is achieved in comparison to previous work employing complex networks. With an optimized method the Rouge score (an automatic evaluation method used in summarization) was 0.5089, which is the best value ever achieved for an extractive summarizer with statistical methods based on complex networks for Brazilian Portuguese. Furthermore, the diversity metric can detect keywords with high precision, which is why we believe it is suitable to produce good summaries. It is also shown that incorporating linguistic knowledge through a syntactic parser does enhance the performance of the automatic summarizers, as expected, but the increase in the Rouge score is only minor. These results reinforce the suitability of complex network methods for improving automatic summarizers in particular, and treating text in general.
Optimal synchronization of directed complex networks
NASA Astrophysics Data System (ADS)
Skardal, Per Sebastian; Taylor, Dane; Sun, Jie
2016-09-01
We study optimal synchronization of networks of coupled phase oscillators. We extend previous theory for optimizing the synchronization properties of undirected networks to the important case of directed networks. We derive a generalized synchrony alignment function that encodes the interplay between the network structure and the oscillators' natural frequencies and serves as an objective measure for the network's degree of synchronization. Using the generalized synchrony alignment function, we show that a network's synchronization properties can be systematically optimized. This framework also allows us to study the properties of synchrony-optimized networks, and in particular, investigate the role of directed network properties such as nodal in- and out-degrees. For instance, we find that in optimally rewired networks, the heterogeneity of the in-degree distribution roughly matches the heterogeneity of the natural frequency distribution, but no such relationship emerges for out-degrees. We also observe that a network's synchronization properties are promoted by a strong correlation between the nodal in-degrees and the natural frequencies of oscillators, whereas the relationship between the nodal out-degrees and the natural frequencies has comparatively little effect. This result is supported by our theory, which indicates that synchronization is promoted by a strong alignment of the natural frequencies with the left singular vectors corresponding to the largest singular values of the Laplacian matrix.
An exploration of graph metric reproducibility in complex brain networks
Telesford, Qawi K.; Burdette, Jonathan H.; Laurienti, Paul J.
2013-01-01
The application of graph theory to brain networks has become increasingly popular in the neuroimaging community. These investigations and analyses have led to a greater understanding of the brain's complex organization. More importantly, it has become a useful tool for studying the brain under various states and conditions. With the ever expanding popularity of network science in the neuroimaging community, there is increasing interest to validate the measurements and calculations derived from brain networks. Underpinning these studies is the desire to use brain networks in longitudinal studies or as clinical biomarkers to understand changes in the brain. A highly reproducible tool for brain imaging could potentially prove useful as a clinical tool. In this review, we examine recent studies in network reproducibility and their implications for analysis of brain networks. PMID:23717257
Discriminating complex networks through supervised NDR and Bayesian classifier
NASA Astrophysics Data System (ADS)
Yan, Ke-Sheng; Rong, Li-Li; Yu, Kai
2016-12-01
Discriminating complex networks is a particularly important task for the purpose of the systematic study of networks. In order to discriminate unknown networks exactly, a large set of network measurements are needed to be taken into account for comprehensively considering network properties. However, as we demonstrate in this paper, these measurements are nonlinear correlated with each other in general, resulting in a wide variety of redundant measurements which unintentionally explain the same aspects of network properties. To solve this problem, we adopt supervised nonlinear dimensionality reduction (NDR) to eliminate the nonlinear redundancy and visualize networks in a low-dimensional projection space. Though unsupervised NDR can achieve the same aim, we illustrate that supervised NDR is more appropriate than unsupervised NDR for discrimination task. After that, we perform Bayesian classifier (BC) in the projection space to discriminate the unknown network by considering the projection score vectors as the input of the classifier. We also demonstrate the feasibility and effectivity of this proposed method in six extensive research real networks, ranging from technological to social or biological. Moreover, the effectiveness and advantage of the proposed method is proved by the contrast experiments with the existing method.
Efficiency of informational transfer in regular and complex networks
NASA Astrophysics Data System (ADS)
Vragović, I.; Louis, E.; Díaz-Guilera, A.
2005-03-01
We analyze the process of informational exchange through complex networks by measuring network efficiencies. Aiming to study nonclustered systems, we propose a modification of this measure on the local level. We apply this method to an extension of the class of small worlds that includes declustered networks and show that they are locally quite efficient, although their clustering coefficient is practically zero. Unweighted systems with small-world and scale-free topologies are shown to be both globally and locally efficient. Our method is also applied to characterize weighted networks. In particular we examine the properties of underground transportation systems of Madrid and Barcelona and reinterpret the results obtained for the Boston subway network.
The complex network of musical tastes
NASA Astrophysics Data System (ADS)
Buldú, Javier M.; Cano, P.; Koppenberger, M.; Almendral, Juan A.; Boccaletti, S.
2007-06-01
We present an empirical study of the evolution of a social network constructed under the influence of musical tastes. The network is obtained thanks to the selfless effort of a broad community of users who share playlists of their favourite songs with other users. When two songs co-occur in a playlist a link is created between them, leading to a complex network where songs are the fundamental nodes. In this representation, songs in the same playlist could belong to different musical genres, but they are prone to be linked by a certain musical taste (e.g. if songs A and B co-occur in several playlists, an user who likes A will probably like also B). Indeed, playlist collections such as the one under study are the basic material that feeds some commercial music recommendation engines. Since playlists have an input date, we are able to evaluate the topology of this particular complex network from scratch, observing how its characteristic parameters evolve in time. We compare our results with those obtained from an artificial network defined by means of a null model. This comparison yields some insight on the evolution and structure of such a network, which could be used as ground data for the development of proper models. Finally, we gather information that can be useful for the development of music recommendation engines and give some hints about how top-hits appear.
Realizing Wisdom Theory in Complex Learning Networks
ERIC Educational Resources Information Center
Kok, Ayse
2009-01-01
The word "wisdom" is rarely seen in contemporary technology and learning discourse. This conceptual paper aims to provide some clear principles that answer the question: How can we establish wisdom in complex learning networks? By considering the nature of contemporary calls for wisdom the paper provides a metatheoretial framework to evaluate the…
The Kuramoto model in complex networks
NASA Astrophysics Data System (ADS)
Rodrigues, Francisco A.; Peron, Thomas K. DM.; Ji, Peng; Kurths, Jürgen
2016-01-01
Synchronization of an ensemble of oscillators is an emergent phenomenon present in several complex systems, ranging from social and physical to biological and technological systems. The most successful approach to describe how coherent behavior emerges in these complex systems is given by the paradigmatic Kuramoto model. This model has been traditionally studied in complete graphs. However, besides being intrinsically dynamical, complex systems present very heterogeneous structure, which can be represented as complex networks. This report is dedicated to review main contributions in the field of synchronization in networks of Kuramoto oscillators. In particular, we provide an overview of the impact of network patterns on the local and global dynamics of coupled phase oscillators. We cover many relevant topics, which encompass a description of the most used analytical approaches and the analysis of several numerical results. Furthermore, we discuss recent developments on variations of the Kuramoto model in networks, including the presence of noise and inertia. The rich potential for applications is discussed for special fields in engineering, neuroscience, physics and Earth science. Finally, we conclude by discussing problems that remain open after the last decade of intensive research on the Kuramoto model and point out some promising directions for future research.
Controlling extreme events on complex networks
Chen, Yu-Zhong; Huang, Zi-Gang; Lai, Ying-Cheng
2014-01-01
Extreme events, a type of collective behavior in complex networked dynamical systems, often can have catastrophic consequences. To develop effective strategies to control extreme events is of fundamental importance and practical interest. Utilizing transportation dynamics on complex networks as a prototypical setting, we find that making the network “mobile” can effectively suppress extreme events. A striking, resonance-like phenomenon is uncovered, where an optimal degree of mobility exists for which the probability of extreme events is minimized. We derive an analytic theory to understand the mechanism of control at a detailed and quantitative level, and validate the theory numerically. Implications of our finding to current areas such as cybersecurity are discussed. PMID:25131344
Controlling extreme events on complex networks.
Chen, Yu-Zhong; Huang, Zi-Gang; Lai, Ying-Cheng
2014-01-01
Extreme events, a type of collective behavior in complex networked dynamical systems, often can have catastrophic consequences. To develop effective strategies to control extreme events is of fundamental importance and practical interest. Utilizing transportation dynamics on complex networks as a prototypical setting, we find that making the network "mobile" can effectively suppress extreme events. A striking, resonance-like phenomenon is uncovered, where an optimal degree of mobility exists for which the probability of extreme events is minimized. We derive an analytic theory to understand the mechanism of control at a detailed and quantitative level, and validate the theory numerically. Implications of our finding to current areas such as cybersecurity are discussed. PMID:25131344
Amplitude dynamics favors synchronization in complex networks
Gambuzza, Lucia Valentina; Gómez-Gardeñes, Jesus; Frasca, Mattia
2016-01-01
In this paper we study phase synchronization in random complex networks of coupled periodic oscillators. In particular, we show that, when amplitude dynamics is not negligible, phase synchronization may be enhanced. To illustrate this, we compare the behavior of heterogeneous units with both amplitude and phase dynamics and pure (Kuramoto) phase oscillators. We find that in small network motifs the behavior crucially depends on the topology and on the node frequency distribution. Surprisingly, the microscopic structures for which the amplitude dynamics improves synchronization are those that are statistically more abundant in random complex networks. Thus, amplitude dynamics leads to a general lowering of the synchronization threshold in arbitrary random topologies. Finally, we show that this synchronization enhancement is generic of oscillators close to Hopf bifurcations. To this aim we consider coupled FitzHugh-Nagumo units modeling neuron dynamics. PMID:27108847
Particle competition for complex network community detection
NASA Astrophysics Data System (ADS)
Quiles, Marcos G.; Zhao, Liang; Alonso, Ronaldo L.; Romero, Roseli A. F.
2008-09-01
In many real situations, randomness is considered to be uncertainty or even confusion which impedes human beings from making a correct decision. Here we study the combined role of randomness and determinism in particle dynamics for complex network community detection. In the proposed model, particles walk in the network and compete with each other in such a way that each of them tries to possess as many nodes as possible. Moreover, we introduce a rule to adjust the level of randomness of particle walking in the network, and we have found that a portion of randomness can largely improve the community detection rate. Computer simulations show that the model has good community detection performance and at the same time presents low computational complexity.
Disease Surveillance on Complex Social Networks.
Herrera, Jose L; Srinivasan, Ravi; Brownstein, John S; Galvani, Alison P; Meyers, Lauren Ancel
2016-07-01
As infectious disease surveillance systems expand to include digital, crowd-sourced, and social network data, public health agencies are gaining unprecedented access to high-resolution data and have an opportunity to selectively monitor informative individuals. Contact networks, which are the webs of interaction through which diseases spread, determine whether and when individuals become infected, and thus who might serve as early and accurate surveillance sensors. Here, we evaluate three strategies for selecting sensors-sampling the most connected, random, and friends of random individuals-in three complex social networks-a simple scale-free network, an empirical Venezuelan college student network, and an empirical Montreal wireless hotspot usage network. Across five different surveillance goals-early and accurate detection of epidemic emergence and peak, and general situational awareness-we find that the optimal choice of sensors depends on the public health goal, the underlying network and the reproduction number of the disease (R0). For diseases with a low R0, the most connected individuals provide the earliest and most accurate information about both the onset and peak of an outbreak. However, identifying network hubs is often impractical, and they can be misleading if monitored for general situational awareness, if the underlying network has significant community structure, or if R0 is high or unknown. Taking a theoretical approach, we also derive the optimal surveillance system for early outbreak detection but find that real-world identification of such sensors would be nearly impossible. By contrast, the friends-of-random strategy offers a more practical and robust alternative. It can be readily implemented without prior knowledge of the network, and by identifying sensors with higher than average, but not the highest, epidemiological risk, it provides reasonably early and accurate information. PMID:27415615
Complexity in neuronal noise depends on network interconnectivity.
Serletis, Demitre; Zalay, Osbert C; Valiante, Taufik A; Bardakjian, Berj L; Carlen, Peter L
2011-06-01
"Noise," or noise-like activity (NLA), defines background electrical membrane potential fluctuations at the cellular level of the nervous system, comprising an important aspect of brain dynamics. Using whole-cell voltage recordings from fast-spiking stratum oriens interneurons and stratum pyramidale neurons located in the CA3 region of the intact mouse hippocampus, we applied complexity measures from dynamical systems theory (i.e., 1/f(γ) noise and correlation dimension) and found evidence for complexity in neuronal NLA, ranging from high- to low-complexity dynamics. Importantly, these high- and low-complexity signal features were largely dependent on gap junction and chemical synaptic transmission. Progressive neuronal isolation from the surrounding local network via gap junction blockade (abolishing gap junction-dependent spikelets) and then chemical synaptic blockade (abolishing excitatory and inhibitory post-synaptic potentials), or the reverse order of these treatments, resulted in emergence of high-complexity NLA dynamics. Restoring local network interconnectivity via blockade washout resulted in resolution to low-complexity behavior. These results suggest that the observed increase in background NLA complexity is the result of reduced network interconnectivity, thereby highlighting the potential importance of the NLA signal to the study of network state transitions arising in normal and abnormal brain dynamics (such as in epilepsy, for example). PMID:21347547
Graph theory and stability analysis of protein complex interaction networks.
Huang, Chien-Hung; Chen, Teng-Hung; Ng, Ka-Lok
2016-04-01
Protein complexes play an essential role in many biological processes. Complexes can interact with other complexes to form protein complex interaction network (PCIN) that involves in important cellular processes. There are relatively few studies on examining the interaction topology among protein complexes; and little is known about the stability of PCIN under perturbations. We employed graph theoretical approach to reveal hidden properties and features of four species PCINs. Two main issues are addressed, (i) the global and local network topological properties, and (ii) the stability of the networks under 12 types of perturbations. According to the topological parameter classification, we identified some critical protein complexes and validated that the topological analysis approach could provide meaningful biological interpretations of the protein complex systems. Through the Kolmogorov-Smimov test, we showed that local topological parameters are good indicators to characterise the structure of PCINs. We further demonstrated the effectiveness of the current approach by performing the scalability and data normalization tests. To measure the robustness of PCINs, we proposed to consider eight topological-based perturbations, which are specifically applicable in scenarios of targeted, sustained attacks. We found that the degree-based, betweenness-based and brokering-coefficient-based perturbations have the largest effect on network stability. PMID:26997661
Emergence of Complexity in Financial Networks
NASA Astrophysics Data System (ADS)
Caldarelli, Guido; Battiston, Stefano; Garlaschelli, Diego; Catanzaro, Michele
We present here a brief summary of the various possible applications of network theory in the field of finance. Since we want to characterize different systems by means of simple and universal features, graph theory could represent a rather powerful methodology. In the following we report our activity in three different subfields, namely the board and director networks, the networks formed by prices correlations and the stock ownership networks. In most of the cases these three kind of networks display scale-free properties making them interesting in their own. Nevertheless, we want to stress here that the main utility of this methodology is to provide new measures of the real data sets in order to validate the different models.
Surprise maximization reveals the community structure of complex networks
NASA Astrophysics Data System (ADS)
Aldecoa, Rodrigo; Marín, Ignacio
2013-01-01
How to determine the community structure of complex networks is an open question. It is critical to establish the best strategies for community detection in networks of unknown structure. Here, using standard synthetic benchmarks, we show that none of the algorithms hitherto developed for community structure characterization perform optimally. Significantly, evaluating the results according to their modularity, the most popular measure of the quality of a partition, systematically provides mistaken solutions. However, a novel quality function, called Surprise, can be used to elucidate which is the optimal division into communities. Consequently, we show that the best strategy to find the community structure of all the networks examined involves choosing among the solutions provided by multiple algorithms the one with the highest Surprise value. We conclude that Surprise maximization precisely reveals the community structure of complex networks.
Surprise maximization reveals the community structure of complex networks.
Aldecoa, Rodrigo; Marín, Ignacio
2013-01-01
How to determine the community structure of complex networks is an open question. It is critical to establish the best strategies for community detection in networks of unknown structure. Here, using standard synthetic benchmarks, we show that none of the algorithms hitherto developed for community structure characterization perform optimally. Significantly, evaluating the results according to their modularity, the most popular measure of the quality of a partition, systematically provides mistaken solutions. However, a novel quality function, called Surprise, can be used to elucidate which is the optimal division into communities. Consequently, we show that the best strategy to find the community structure of all the networks examined involves choosing among the solutions provided by multiple algorithms the one with the highest Surprise value. We conclude that Surprise maximization precisely reveals the community structure of complex networks. PMID:23320141
Universal resilience patterns in complex networks.
Gao, Jianxi; Barzel, Baruch; Barabási, Albert-László
2016-02-18
Resilience, a system's ability to adjust its activity to retain its basic functionality when errors, failures and environmental changes occur, is a defining property of many complex systems. Despite widespread consequences for human health, the economy and the environment, events leading to loss of resilience--from cascading failures in technological systems to mass extinctions in ecological networks--are rarely predictable and are often irreversible. These limitations are rooted in a theoretical gap: the current analytical framework of resilience is designed to treat low-dimensional models with a few interacting components, and is unsuitable for multi-dimensional systems consisting of a large number of components that interact through a complex network. Here we bridge this theoretical gap by developing a set of analytical tools with which to identify the natural control and state parameters of a multi-dimensional complex system, helping us derive effective one-dimensional dynamics that accurately predict the system's resilience. The proposed analytical framework allows us systematically to separate the roles of the system's dynamics and topology, collapsing the behaviour of different networks onto a single universal resilience function. The analytical results unveil the network characteristics that can enhance or diminish resilience, offering ways to prevent the collapse of ecological, biological or economic systems, and guiding the design of technological systems resilient to both internal failures and environmental changes. PMID:26887493
Disease Surveillance on Complex Social Networks
Herrera, Jose L.; Srinivasan, Ravi; Brownstein, John S.; Galvani, Alison P.; Meyers, Lauren Ancel
2016-01-01
As infectious disease surveillance systems expand to include digital, crowd-sourced, and social network data, public health agencies are gaining unprecedented access to high-resolution data and have an opportunity to selectively monitor informative individuals. Contact networks, which are the webs of interaction through which diseases spread, determine whether and when individuals become infected, and thus who might serve as early and accurate surveillance sensors. Here, we evaluate three strategies for selecting sensors—sampling the most connected, random, and friends of random individuals—in three complex social networks—a simple scale-free network, an empirical Venezuelan college student network, and an empirical Montreal wireless hotspot usage network. Across five different surveillance goals—early and accurate detection of epidemic emergence and peak, and general situational awareness—we find that the optimal choice of sensors depends on the public health goal, the underlying network and the reproduction number of the disease (R0). For diseases with a low R0, the most connected individuals provide the earliest and most accurate information about both the onset and peak of an outbreak. However, identifying network hubs is often impractical, and they can be misleading if monitored for general situational awareness, if the underlying network has significant community structure, or if R0 is high or unknown. Taking a theoretical approach, we also derive the optimal surveillance system for early outbreak detection but find that real-world identification of such sensors would be nearly impossible. By contrast, the friends-of-random strategy offers a more practical and robust alternative. It can be readily implemented without prior knowledge of the network, and by identifying sensors with higher than average, but not the highest, epidemiological risk, it provides reasonably early and accurate information. PMID:27415615
Detecting complex network modularity by dynamical clustering
NASA Astrophysics Data System (ADS)
Boccaletti, S.; Ivanchenko, M.; Latora, V.; Pluchino, A.; Rapisarda, A.
2007-04-01
Based on cluster desynchronization properties of phase oscillators, we introduce an efficient method for the detection and identification of modules in complex networks. The performance of the algorithm is tested on computer generated and real-world networks whose modular structure is already known or has been studied by means of other methods. The algorithm attains a high level of precision, especially when the modular units are very mixed and hardly detectable by the other methods, with a computational effort O(KN) on a generic graph with N nodes and K links.
Post Disaster Governance, Complexity and Network Theory
Lassa, Jonatan A.
2015-01-01
This research aims to understand the organizational network typology of large-scale disaster intervention in developing countries and to understand the complexity of post-disaster intervention, through the use of network theory based on empirical data from post-tsunami reconstruction in Aceh, Indonesia, during 2005/2007. The findings suggest that the ‘ degrees of separation’ (or network diameter) between any two organizations in the field is 5, thus reflecting ‘small world’ realities and therefore making no significant difference with the real human networks, as found in previous experiments. There are also significant loops in the network reflecting the fact that some actors tend to not cooperate, which challenges post disaster coordination. The findings show the landscape of humanitarian actors is not randomly distributed. Many actors were connected to each other through certain hubs, while hundreds of actors make ‘scattered’ single ‘principal-client’ links. The paper concludes that by understanding the distribution of degree, centrality, ‘degrees of separation’ and visualization of the network, authorities can improve their understanding of the realities of coordination, from macro to micro scales. PMID:26236562
Modified localized attack on complex network
NASA Astrophysics Data System (ADS)
Dong, Gaogao; Du, Ruijin; Hao, Huifang; Tian, Lixin
2016-01-01
Since a shell structure contains a wealth of information, it is not only very important for understanding the transport properties of the network, but also essential to identify influential spreaders in complex networks. Nodes within each shell can be classified into two categories: protected nodes and unprotected nodes. In this paper, we propose a generalization of the localized attack, modified localized attack, which means that when a randomly chosen node (root node) is under attack, protected nodes will not be removed, but unprotected nodes in the nearest shells will fail. We numerically and analytically study the system robustness under this attack by taking an Erdös-Rényi (ER) network, a regular random (RR) network and a scale-free (SF) network as examples. Moreover, a fraction of nodes belonging to giant component S and a critical threshold q c , where S approaches to zero, are given. The result implies that increasing connection density has been found to be useful to significantly improve network robustness.
Robust Multiobjective Controllability of Complex Neuronal Networks.
Tang, Yang; Gao, Huijun; Du, Wei; Lu, Jianquan; Vasilakos, Athanasios V; Kurths, Jurgen
2016-01-01
This paper addresses robust multiobjective identification of driver nodes in the neuronal network of a cat's brain, in which uncertainties in determination of driver nodes and control gains are considered. A framework for robust multiobjective controllability is proposed by introducing interval uncertainties and optimization algorithms. By appropriate definitions of robust multiobjective controllability, a robust nondominated sorting adaptive differential evolution (NSJaDE) is presented by means of the nondominated sorting mechanism and the adaptive differential evolution (JaDE). The simulation experimental results illustrate the satisfactory performance of NSJaDE for robust multiobjective controllability, in comparison with six statistical methods and two multiobjective evolutionary algorithms (MOEAs): nondominated sorting genetic algorithms II (NSGA-II) and nondominated sorting composite differential evolution. It is revealed that the existence of uncertainties in choosing driver nodes and designing control gains heavily affects the controllability of neuronal networks. We also unveil that driver nodes play a more drastic role than control gains in robust controllability. The developed NSJaDE and obtained results will shed light on the understanding of robustness in controlling realistic complex networks such as transportation networks, power grid networks, biological networks, etc. PMID:26441452
Universality at Breakdown of Quantum Transport on Complex Networks
NASA Astrophysics Data System (ADS)
Kulvelis, Nikolaj; Dolgushev, Maxim; Mülken, Oliver
2015-09-01
We consider single-particle quantum transport on parametrized complex networks. Based on general arguments regarding the spectrum of the corresponding Hamiltonian, we derive bounds for a measure of the global transport efficiency defined by the time-averaged return probability. For treelike networks, we show analytically that a transition from efficient to inefficient transport occurs depending on the (average) functionality of the nodes of the network. In the infinite system size limit, this transition can be characterized by an exponent which is universal for all treelike networks. Our findings are corroborated by analytic results for specific deterministic networks, dendrimers and Vicsek fractals, and by Monte Carlo simulations of iteratively built scale-free trees.
Universality at Breakdown of Quantum Transport on Complex Networks.
Kulvelis, Nikolaj; Dolgushev, Maxim; Mülken, Oliver
2015-09-18
We consider single-particle quantum transport on parametrized complex networks. Based on general arguments regarding the spectrum of the corresponding Hamiltonian, we derive bounds for a measure of the global transport efficiency defined by the time-averaged return probability. For treelike networks, we show analytically that a transition from efficient to inefficient transport occurs depending on the (average) functionality of the nodes of the network. In the infinite system size limit, this transition can be characterized by an exponent which is universal for all treelike networks. Our findings are corroborated by analytic results for specific deterministic networks, dendrimers and Vicsek fractals, and by Monte Carlo simulations of iteratively built scale-free trees. PMID:26430977
Quantum Google in a Complex Network
Paparo, Giuseppe Davide; Müller, Markus; Comellas, Francesc; Martin-Delgado, Miguel Angel
2013-01-01
We investigate the behaviour of the recently proposed Quantum PageRank algorithm, in large complex networks. We find that the algorithm is able to univocally reveal the underlying topology of the network and to identify and order the most relevant nodes. Furthermore, it is capable to clearly highlight the structure of secondary hubs and to resolve the degeneracy in importance of the low lying part of the list of rankings. The quantum algorithm displays an increased stability with respect to a variation of the damping parameter, present in the Google algorithm, and a more clearly pronounced power-law behaviour in the distribution of importance, as compared to the classical algorithm. We test the performance and confirm the listed features by applying it to real world examples from the WWW. Finally, we raise and partially address whether the increased sensitivity of the quantum algorithm persists under coordinated attacks in scale-free and random networks. PMID:24091980
Analysis of remote synchronization in complex networks
NASA Astrophysics Data System (ADS)
Gambuzza, Lucia Valentina; Cardillo, Alessio; Fiasconaro, Alessandro; Fortuna, Luigi; Gómez-Gardeñes, Jesus; Frasca, Mattia
2013-12-01
A novel regime of synchronization, called remote synchronization, where the peripheral nodes form a phase synchronized cluster not including the hub, was recently observed in star motifs [Bergner et al., Phys. Rev. E 85, 026208 (2012)]. We show the existence of a more general dynamical state of remote synchronization in arbitrary networks of coupled oscillators. This state is characterized by the synchronization of pairs of nodes that are not directly connected via a physical link or any sequence of synchronized nodes. This phenomenon is almost negligible in networks of phase oscillators as its underlying mechanism is the modulation of the amplitude of those intermediary nodes between the remotely synchronized units. Our findings thus show the ubiquity and robustness of these states and bridge the gap from their recent observation in simple toy graphs to complex networks.
The complex networks approach for authorship attribution of books
NASA Astrophysics Data System (ADS)
Mehri, Ali; Darooneh, Amir H.; Shariati, Ashrafalsadat
2012-04-01
Authorship analysis by means of textual features is an important task in linguistic studies. We employ complex networks theory to tackle this disputed problem. In this work, we focus on some measurable quantities of word co-occurrence network of each book for authorship characterization. Based on the network features, attribution probability is defined for authorship identification. Furthermore, two scaling exponents, q-parameter and α-exponent, are combined to classify personal writing style with acceptable high resolution power. The q-parameter, generally known as the nonextensivity measure, is calculated for degree distribution and the α-exponent comes from a power law relationship between number of links and number of nodes in the co-occurrence network constructed for different books written by each author. The applicability of the presented method is evaluated in an experiment with thirty six books of five Persian litterateurs. Our results show high accuracy rate in authorship attribution.
Complex network approach to fractional time series
Manshour, Pouya
2015-10-15
In order to extract correlation information inherited in stochastic time series, the visibility graph algorithm has been recently proposed, by which a time series can be mapped onto a complex network. We demonstrate that the visibility algorithm is not an appropriate one to study the correlation aspects of a time series. We then employ the horizontal visibility algorithm, as a much simpler one, to map fractional processes onto complex networks. The degree distributions are shown to have parabolic exponential forms with Hurst dependent fitting parameter. Further, we take into account other topological properties such as maximum eigenvalue of the adjacency matrix and the degree assortativity, and show that such topological quantities can also be used to predict the Hurst exponent, with an exception for anti-persistent fractional Gaussian noises. To solve this problem, we take into account the Spearman correlation coefficient between nodes' degrees and their corresponding data values in the original time series.
Complex network approach to fractional time series
NASA Astrophysics Data System (ADS)
Manshour, Pouya
2015-10-01
In order to extract correlation information inherited in stochastic time series, the visibility graph algorithm has been recently proposed, by which a time series can be mapped onto a complex network. We demonstrate that the visibility algorithm is not an appropriate one to study the correlation aspects of a time series. We then employ the horizontal visibility algorithm, as a much simpler one, to map fractional processes onto complex networks. The degree distributions are shown to have parabolic exponential forms with Hurst dependent fitting parameter. Further, we take into account other topological properties such as maximum eigenvalue of the adjacency matrix and the degree assortativity, and show that such topological quantities can also be used to predict the Hurst exponent, with an exception for anti-persistent fractional Gaussian noises. To solve this problem, we take into account the Spearman correlation coefficient between nodes' degrees and their corresponding data values in the original time series.
Complex networks analysis of obstructive nephropathy data
NASA Astrophysics Data System (ADS)
Zanin, M.; Boccaletti, S.
2011-09-01
Congenital obstructive nephropathy (ON) is one of the most frequent and complex diseases affecting children, characterized by an abnormal flux of the urine, due to a partial or complete obstruction of the urinary tract; as a consequence, urine may accumulate in the kidney and disturb the normal operation of the organ. Despite important advances, pathological mechanisms are not yet fully understood. In this contribution, the topology of complex networks, based on vectors of features of control and ON subjects, is related with the severity of the pathology. Nodes in these networks represent genetic and metabolic profiles, while connections between them indicate an abnormal relation between their expressions. Resulting topologies allow discriminating ON subjects and detecting which genetic or metabolic elements are responsible for the malfunction.
Price of Anarchy on Complex Networks
NASA Astrophysics Data System (ADS)
Youn, Hye-Jin; Jeong, Hawoong
2007-03-01
We present an optimization problem of decentralized transportation networks, where latency depends linearly on congestion of a link. The system shows that a collection of individual optimization of the flow does not always meet the most optimized outcome that is conventionally assumed. We suggest that the Price of Anarchy, the ratio of two optimums, can quantify such discrepancy and accordingly regarded as an index of inefficiency of the system. We also measure the Price of Anarchy of model networks with various underlying structures, and a simplified Boston road network. Our numerical result confirms the existence of the Price of Anarchy in the networks. Finally, we find Braess's paradox is not just a pedagogical example, but inefficiency that can counterintuitively take place in real.
Complex growing networks with intrinsic vertex fitness
Bedogne, C.; Rodgers, G. J.
2006-10-15
One of the major questions in complex network research is to identify the range of mechanisms by which a complex network can self organize into a scale-free state. In this paper we investigate the interplay between a fitness linking mechanism and both random and preferential attachment. In our models, each vertex is assigned a fitness x, drawn from a probability distribution {rho}(x). In Model A, at each time step a vertex is added and joined to an existing vertex, selected at random, with probability p and an edge is introduced between vertices with fitnesses x and y, with a rate f(x,y), with probability 1-p. Model B differs from Model A in that, with probability p, edges are added with preferential attachment rather than randomly. The analysis of Model A shows that, for every fixed fitness x, the network's degree distribution decays exponentially. In Model B we recover instead a power-law degree distribution whose exponent depends only on p, and we show how this result can be generalized. The properties of a number of particular networks are examined.
Structural and dynamical properties of complex networks
NASA Astrophysics Data System (ADS)
Ghoshal, Gourab
Recent years have witnessed a substantial amount of interest within the physics community in the properties of networks. Techniques from statistical physics coupled with the widespread availability of computing resources have facilitated studies ranging from large scale empirical analysis of the worldwide web, social networks, biological systems, to the development of theoretical models and tools to explore the various properties of these systems. Following these developments, in this dissertation, we present and solve for a diverse set of new problems, investigating the structural and dynamical properties of both model and real world networks. We start by defining a new metric to measure the stability of network structure to disruptions, and then using a combination of theory and simulation study its properties in detail on artificially generated networks; we then compare our results to a selection of networks from the real world and find good agreement in most cases. In the following chapter, we propose a mathematical model that mimics the structure of popular file-sharing websites such as Flickr and CiteULike and demonstrate that many of its properties can solved exactly in the limit of large network size. The remaining part of the dissertation primarily focuses on the dynamical properties of networks. We first formulate a model of a network that evolves under the addition and deletion of vertices and edges, and solve for the equilibrium degree distribution for a variety of cases of interest. We then consider networks whose structure can be manipulated by adjusting the rules by which vertices enter and leave the network. We focus in particular on degree distributions and show that, with some mild constraints, it is possible by a suitable choice of rules to arrange for the network to have any degree distribution we desire. In addition we define a simple local algorithm by which appropriate rules can be implemented in practice. Finally, we conclude our
Universal resilience patterns in complex networks
NASA Astrophysics Data System (ADS)
Gao, Jianxi; Barzel, Baruch; Barabási, Albert-László
2016-02-01
Resilience, a system’s ability to adjust its activity to retain its basic functionality when errors, failures and environmental changes occur, is a defining property of many complex systems. Despite widespread consequences for human health, the economy and the environment, events leading to loss of resilience—from cascading failures in technological systems to mass extinctions in ecological networks—are rarely predictable and are often irreversible. These limitations are rooted in a theoretical gap: the current analytical framework of resilience is designed to treat low-dimensional models with a few interacting components, and is unsuitable for multi-dimensional systems consisting of a large number of components that interact through a complex network. Here we bridge this theoretical gap by developing a set of analytical tools with which to identify the natural control and state parameters of a multi-dimensional complex system, helping us derive effective one-dimensional dynamics that accurately predict the system’s resilience. The proposed analytical framework allows us systematically to separate the roles of the system’s dynamics and topology, collapsing the behaviour of different networks onto a single universal resilience function. The analytical results unveil the network characteristics that can enhance or diminish resilience, offering ways to prevent the collapse of ecological, biological or economic systems, and guiding the design of technological systems resilient to both internal failures and environmental changes.
Complexity Measures in Magnetoencephalography: Measuring "Disorder" in Schizophrenia
Brookes, Matthew J.; Hall, Emma L.; Robson, Siân E.; Price, Darren; Palaniyappan, Lena; Liddle, Elizabeth B.; Liddle, Peter F.; Robinson, Stephen E.; Morris, Peter G.
2015-01-01
This paper details a methodology which, when applied to magnetoencephalography (MEG) data, is capable of measuring the spatio-temporal dynamics of ‘disorder’ in the human brain. Our method, which is based upon signal entropy, shows that spatially separate brain regions (or networks) generate temporally independent entropy time-courses. These time-courses are modulated by cognitive tasks, with an increase in local neural processing characterised by localised and transient increases in entropy in the neural signal. We explore the relationship between entropy and the more established time-frequency decomposition methods, which elucidate the temporal evolution of neural oscillations. We observe a direct but complex relationship between entropy and oscillatory amplitude, which suggests that these metrics are complementary. Finally, we provide a demonstration of the clinical utility of our method, using it to shed light on aberrant neurophysiological processing in schizophrenia. We demonstrate significantly increased task induced entropy change in patients (compared to controls) in multiple brain regions, including a cingulo-insula network, bilateral insula cortices and a right fronto-parietal network. These findings demonstrate potential clinical utility for our method and support a recent hypothesis that schizophrenia can be characterised by abnormalities in the salience network (a well characterised distributed network comprising bilateral insula and cingulate cortices). PMID:25886553
Simulating Operation of a Complex Sensor Network
NASA Technical Reports Server (NTRS)
Jennings, Esther; Clare, Loren; Woo, Simon
2008-01-01
Simulation Tool for ASCTA Microsensor Network Architecture (STAMiNA) ["ASCTA" denotes the Advanced Sensors Collaborative Technology Alliance.] is a computer program for evaluating conceptual sensor networks deployed over terrain to provide military situational awareness. This or a similar program is needed because of the complexity of interactions among such diverse phenomena as sensing and communication portions of a network, deployment of sensor nodes, effects of terrain, data-fusion algorithms, and threat characteristics. STAMiNA is built upon a commercial network-simulator engine, with extensions to include both sensing and communication models in a discrete-event simulation environment. Users can define (1) a mission environment, including terrain features; (2) objects to be sensed; (3) placements and modalities of sensors, abilities of sensors to sense objects of various types, and sensor false alarm rates; (4) trajectories of threatening objects; (5) means of dissemination and fusion of data; and (6) various network configurations. By use of STAMiNA, one can simulate detection of targets through sensing, dissemination of information by various wireless communication subsystems under various scenarios, and fusion of information, incorporating such metrics as target-detection probabilities, false-alarm rates, and communication loads, and capturing effects of terrain and threat.
Diffusive capture process on complex networks
NASA Astrophysics Data System (ADS)
Lee, Sungmin; Yook, Soon-Hyung; Kim, Yup
2006-10-01
We study the dynamical properties of a diffusing lamb captured by a diffusing lion on the complex networks with various sizes of N . We find that the lifetime ⟨T⟩ of a lamb scales as ⟨T⟩˜N and the survival probability S(N→∞,t) becomes finite on scale-free networks with degree exponent γ>3 . However, S(N,t) for γ<3 has a long-living tail on tree-structured scale-free networks and decays exponentially on looped scale-free networks. This suggests that the second moment of degree distribution ⟨k2⟩ is the relevant factor for the dynamical properties in the diffusive capture process. We numerically find that the normalized number of capture events at a node with degree k , n(k) , decreases as n(k)˜k-σ . When γ<3 , n(k) still increases anomalously for k≈kmax , where kmax is the maximum value of k of given networks with size N . We analytically show that n(k) satisfies the relation n(k)˜k2P(k) for any degree distribution P(k) and the total number of capture events Ntot is proportional to ⟨k2⟩ , which causes the γ -dependent behavior of S(N,t) and ⟨T⟩ .
Propagation dynamics on networks featuring complex topologies
NASA Astrophysics Data System (ADS)
Hébert-Dufresne, Laurent; Noël, Pierre-André; Marceau, Vincent; Allard, Antoine; Dubé, Louis J.
2010-09-01
Analytical description of propagation phenomena on random networks has flourished in recent years, yet more complex systems have mainly been studied through numerical means. In this paper, a mean-field description is used to coherently couple the dynamics of the network elements (such as nodes, vertices, individuals, etc.) on the one hand and their recurrent topological patterns (such as subgraphs, groups, etc.) on the other hand. In a susceptible-infectious-susceptible (SIS) model of epidemic spread on social networks with community structure, this approach yields a set of ordinary differential equations for the time evolution of the system, as well as analytical solutions for the epidemic threshold and equilibria. The results obtained are in good agreement with numerical simulations and reproduce the behavior of random networks in the appropriate limits which highlights the influence of topology on the processes. Finally, it is demonstrated that our model predicts higher epidemic thresholds for clustered structures than for equivalent random topologies in the case of networks with zero degree correlation.
Sampling of Complex Networks: A Datamining Approach
NASA Astrophysics Data System (ADS)
Loecher, Markus; Dohrmann, Jakob; Bauer, Gernot
2007-03-01
Efficient and accurate sampling of big complex networks is still an unsolved problem. As the degree distribution is one of the most commonly used attributes to characterize a network, there have been many attempts in recent papers to derive the original degree distribution from the data obtained during a traceroute- like sampling process. This talk describes a strategy for predicting the original degree of a node using the data obtained from a network by traceroute-like sampling making use of datamining techniques. Only local quantities (the sampled degree k, the redundancy of node detection r, the time of the first discovery of a node t and the distance to the sampling source d) are used as input for the datamining models. Global properties like the betweenness centrality are ignored. These local quantities are examined theoretically and in simulations to increase their value for the predictions. The accuracy of the models is discussed as a function of the number of sources used in the sampling process and the underlying topology of the network. The purpose of this work is to introduce the techniques of the relatively young field of datamining to the discussion on network sampling.
The Generalization Complexity Measure for Continuous Input Data
Cannas, Sergio A.; Osenda, Omar; Jerez, José M.
2014-01-01
We introduce in this work an extension for the generalization complexity measure to continuous input data. The measure, originally defined in Boolean space, quantifies the complexity of data in relationship to the prediction accuracy that can be expected when using a supervised classifier like a neural network, SVM, and so forth. We first extend the original measure for its use with continuous functions to later on, using an approach based on the use of the set of Walsh functions, consider the case of having a finite number of data points (inputs/outputs pairs), that is, usually the practical case. Using a set of trigonometric functions a model that gives a relationship between the size of the hidden layer of a neural network and the complexity is constructed. Finally, we demonstrate the application of the introduced complexity measure, by using the generated model, to the problem of estimating an adequate neural network architecture for real-world data sets. PMID:24983000
A descriptive study of fracture networks in rocks using complex network metrics
NASA Astrophysics Data System (ADS)
Santiago, Elizabeth; Velasco-Hernández, Jorge X.; Romero-Salcedo, Manuel
2016-03-01
In this paper we describe the static topological fracture structure of five rock samples from three regions in Eastern Mexico by the application of centrality and communicability measures used in the area of complex networks. The information obtained from fracture images is used to characterize the fracture networks. The analysis is divided into two groups of characteristics. The first provides a general summary of the fracture network through the description of the number of nodes, edges, diameter, radius, lengths and clustering coefficients. A second group of features centers on the description of communicability in the network by means of three indexes recently proposed. In addition, we apply centrality measures (betweenness, closeness, eigenvector and eccentricity) for quantifying the importance of nodes in the entire network. Finally, we identify a topology for fracture networks using a classification based on the degree of communicability. The most important results obtained in this work are focused in the topological characteristic patterns found in fracture networks applying the approach of complex networks that in general provide local and global parameters of connectivity and communicability.