اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNetwork dismantling
211
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study the network dismantling problem, which consists in determining a minimal set of vertices whose removal leaves the network broken into connected components of sub-extensive size. For a large class of random graphs, this problem is tightly connected to the decycling problem (the removal of vertices leaving the graph acyclic). Exploiting this connection and recent works on epidemic spreading we present precise predictions for the minimal size of a dismantling set in a large random graph with a prescribed (light-tailed) degree distribution. Building on the statistical mechanics perspective we propose a three-stage Min-Sum algorithm for efficiently dismantling networks, including heavy-tailed ones for which the dismantling and decycling problems are not equivalent. We also provide further insights into the dismantling problem concluding that it is an intrinsically collective problem and that optimal dismantling sets cannot be viewed as a collection of individually well performing nodes.
قيم البحث
اقرأ أيضاً
We propose a maximally disassortative (MD) network model which realizes a maximally negative degree-degree correlation, and study its percolation transition to discuss the effect of a strong degree-degree correlation on the percolation critical behav
iors. Using the generating function method for bipartite networks, we analytically derive the percolation threshold and the order parameter critical exponent, $beta$. For the MD scale-free networks, whose degree distribution is $P(k) sim k^{-gamma}$, we show that the exponent, $beta$, for the MD networks and corresponding uncorrelated networks are same for $gamma>3$ but are different for $2<gamma<3$. A strong degree-degree correlation significantly affects the percolation critical behavior in heavy-tailed scale-free networks. Our analytical results for the critical exponents are numerically confirmed by a finite-size scaling argument.
This paper explores a variety of strategies for understanding the formation, structure, efficiency and vulnerability of water distribution networks. Water supply systems are studied as spatially organized networks for which the practical applications
of abstract evaluation methods are critically evaluated. Empirical data from benchmark networks are used to study the interplay between network structure and operational efficiency, reliability and robustness. Structural measurements are undertaken to quantify properties such as redundancy and optimal-connectivity, herein proposed as constraints in network design optimization problems. The role of the supply-demand structure towards system efficiency is studied and an assessment of the vulnerability to failures based on the disconnection of nodes from the source(s) is undertaken. The absence of conventional degree-based hubs (observed through uncorrelated non-heterogeneous sparse topologies) prompts an alternative approach to studying structural vulnerability based on the identification of network cut-sets and optimal connectivity invariants. A discussion on the scope, limitations and possible future directions of this research is provided.
Percolation theory is an approach to study vulnerability of a system. We develop analytical framework and analyze percolation properties of a network composed of interdependent networks (NetONet). Typically, percolation of a single network shows that
the damage in the network due to a failure is a continuous function of the fraction of failed nodes. In sharp contrast, in NetONet, due to the cascading failures, the percolation transition may be discontinuous and even a single node failure may lead to abrupt collapse of the system. We demonstrate our general framework for a NetONet composed of $n$ classic ErdH{o}s-R{e}nyi (ER) networks, where each network depends on the same number $m$ of other networks, i.e., a random regular network of interdependent ER networks. In contrast to a emph{treelike} NetONet in which the size of the largest connected cluster (mutual component) depends on $n$, the loops in the RR NetONet cause the largest connected cluster to depend only on $m$. We also analyzed the extremely vulnerable feedback condition of coupling. In the case of ER networks, the NetONet only exhibits two phases, a second order phase transition and collapse, and there is no first phase transition regime unlike the no feedback condition. In the case of NetONet composed of RR networks, there exists a first order phase transition when $q$ is large and second order phase transition when $q$ is small. Our results can help in designing robust interdependent systems.
Individual heterogeneity is a key characteristic of many real-world systems, from organisms to humans. However its role in determining the systems collective dynamics is typically not well understood. Here we study how individual heterogeneity impact
s the system network dynamics by comparing linking mechanisms that favor similar or dissimilar individuals. We find that this heterogeneity-based evolution can drive explosive network behavior and dictates how a polarized population moves toward consensus. Our model shows good agreement with data from both biological and social science domains. We conclude that individual heterogeneity likely plays a key role in the collective development of real-world networks and communities, and cannot be ignored.
Network growth processes can be understood as generative models of the structure and history of complex networks. This point of view naturally leads to the problem of network archaeology: reconstructing all the past states of a network from its struc
ture---a difficult permutation inference problem. In this paper, we introduce a Bayesian formulation of network archaeology, with a generalization of preferential attachment as our generative mechanism. We develop a sequential Monte Carlo algorithm to evaluate the posterior averages of this model, as well as an efficient heuristic that uncovers a history well correlated with the true one, in polynomial time. We use these methods to identify and characterize a phase transition in the quality of the reconstructed history, when they are applied to artificial networks generated by the model itself. Despite the existence of a no-recovery phase, we find that nontrivial inference is possible in a large portion of the parameter space as well as on empirical data.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
