ترغب بنشر مسار تعليمي؟ اضغط هنا

Hierarchy measure for complex networks

143   0   0.0 ( 0 )
 نشر من قبل Enys Mones
 تاريخ النشر 2012
  مجال البحث فيزياء
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

Network motifs are small building blocks of complex networks. Statistically significant motifs often perform network-specific functions. However, the precise nature of the connection between motifs and the global structure and function of networks re mains elusive. Here we show that the global structure of some real networks is statistically determined by the probability of connections within motifs of size at most 3, once this probability accounts for node degrees. The connectivity profiles of node triples in these networks capture all their local and global properties. This finding impacts methods relying on motif statistical significance, and enriches our understanding of the elementary forces that shape the structure of complex networks.
151 - James P. Gleeson 2012
A wide class of binary-state dynamics on networks---including, for example, the voter model, the Bass diffusion model, and threshold models---can be described in terms of transition rates (spin-flip probabilities) that depend on the number of nearest neighbors in each of the two possible states. High-accuracy approximations for the emergent dynamics of such models on uncorrelated, infinite networks are given by recently-developed compartmental models or approximate master equations (AME). Pair approximations (PA) and mean-field theories can be systematically derived from the AME. We show that PA and AME solutions can coincide under certain circumstances, and numerical simulations confirm that PA is highly accurate in these cases. For monotone dynamics (where transitions out of one nodal state are impossible, e.g., SI disease-spread or Bass diffusion), PA and AME give identical results for the fraction of nodes in the infected (active) state for all time, provided the rate of infection depends linearly on the number of infected neighbors. In the more general non-monotone case, we derive a condition---that proves equivalent to a detailed balance condition on the dynamics---for PA and AME solutions to coincide in the limit $t to infty$. This permits bifurcation analysis, yielding explicit expressions for the critical (ferromagnetic/paramagnetic transition) point of such dynamics, closely analogous to the critical temperature of the Ising spin model. Finally, the AME for threshold models of propagation is shown to reduce to just two differential equations, and to give excellent agreement with numerical simulations. As part of this work, Octave/Matlab code for implementing and solving the differential equation systems is made available for download.
To understand the controllability of complex networks is a forefront problem relevant to different fields of science and engineering. Despite recent advances in network controllability theories, an outstanding issue is to understand the effect of net work topology and nodal interactions on the controllability at the most fundamental level. Here we develop a universal framework based on local information only to unearth the most {em fundamental building blocks} that determine the controllability. In particular, we introduce a network dissection process to fully unveil the origin of the role of individual nodes and links in control, giving rise to a criterion for the much needed strong structural controllability. We theoretically uncover various phase-transition phenomena associated with the role of nodes and links and strong structural controllability. Applying our theory to a large number of empirical networks demonstrates that technological networks are more strongly structurally controllable (SSC) than many social and biological networks, and real world networks are generally much more SSC than their random counterparts with intrinsic resilience and adaptability as a result of human design and natural evolution.
Determining community structure is a central topic in the study of complex networks, be it technological, social, biological or chemical, in static or 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.
149 - Kyu-Min Lee , K.-I. Goh , 2011
We introduce the sandpile model on multiplex networks with more than one type of edge and investigate its scaling and dynamical behaviors. We find that the introduction of multiplexity does not alter the scaling behavior of avalanche dynamics; the sy stem is critical with an asymptotic power-law avalanche size distribution with an exponent $tau = 3/2$ on duplex random networks. The detailed cascade dynamics, however, is affected by the multiplex coupling. For example, higher-degree nodes such as hubs in scale-free networks fail more often in the multiplex dynamics than in the simplex network counterpart in which different types of edges are simply aggregated. Our results suggest that multiplex modeling would be necessary in order to gain a better understanding of cascading failure phenomena of real-world multiplex complex systems, such as the global economic crisis.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا