Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIdentifying Infection Sources and Regions in Large Networks
175
0
0.0
(
0
)
Added by
Wuqiong Luo
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Identifying the infection sources in a network, including the index cases that introduce a contagious disease into a population network, the servers that inject a computer virus into a computer network, or the individuals who started a rumor in a social network, plays a critical role in limiting the damage caused by the infection through timely quarantine of the sources. We consider the problem of estimating the infection sources and the infection regions (subsets of nodes infected by each source) in a network, based only on knowledge of which nodes are infected and their connections, and when the number of sources is unknown a priori. We derive estimators for the infection sources and their infection regions based on approximations of the infection sequences count. We prove that if there are at most two infection sources in a geometric tree, our estimator identifies the true source or sources with probability going to one as the number of infected nodes increases. When there are more than two infection sources, and when the maximum possible number of infection sources is known, we propose an algorithm with quadratic complexity to estimate the actual number and identities of the infection sources. Simulations on various kinds of networks, including tree networks, small-world networks and real world power grid networks, and tests on two real data sets are provided to verify the performance of our estimators.
rate research
Read More
Understanding structural controllability of a complex network requires to identify a Minimum Input nodes Set (MIS) of the network. It has been suggested that finding an MIS is equivalent to computing a maximum matching of the network, where the unmatched nodes constitute an MIS. However, maximum matching of a network is often not unique, and finding all MISs may provide deep insights to the controllability of the network. Finding all possible input nodes, which form the union of all MISs, is computationally challenging for large networks. Here we present an efficient enumerative algorithm for the problem. The main idea is to modify a maximum matching algorithm to make it efficient for finding all possible input nodes by computing only one MIS. We rigorously proved the correctness of the new algorithm and evaluated its performance on synthetic and large real networks. The experimental results showed that the new algorithm ran several orders of magnitude faster than the existing method on large real networks.
Our ability to uncover complex network structure and dynamics from data is fundamental to understanding and controlling collective dynamics in complex systems. Despite recent progress in this area, reconstructing networks with stochastic dynamical processes from limited time series remains to be an outstanding problem. Here we develop a framework based on compressed sensing to reconstruct complex networks on which stochastic spreading dynamics take place. We apply the methodology to a large number of model and real networks, finding that a full reconstruction of inhomogeneous interactions can be achieved from small amounts of polarized (binary) data, a virtue of compressed sensing. Further, we demonstrate that a hidden source that triggers the spreading process but is externally inaccessible can be ascertained and located with high confidence in the absence of direct routes of propagation from it. Our approach thus establishes a paradigm for tracing and controlling epidemic invasion and information diffusion in complex networked systems.
We investigate the electrical current and flow (number of parallel paths) between two sets of n sources and n sinks in complex networks. We derive analytical formulas for the average current and flow as a function of n. We show that for small n, increasing n improves the total transport in the network, while for large n bottlenecks begin to form. For the case of flow, this leads to an optimal n* above which the transport is less efficient. For current, the typical decrease in the length of the connecting paths for large n compensates for the effect of the bottlenecks. We also derive an expression for the average flow as a function of n under the common limitation that transport takes place between specific pairs of sources and sinks.
Multiple lines of evidence strongly suggest that infection hotspots, where a single individual infects many others, play a key role in the transmission dynamics of COVID-19. However, most of the existing epidemiological models fail to capture this aspect by neither representing the sites visited by individuals explicitly nor characterizing disease transmission as a function of individual mobility patterns. In this work, we introduce a temporal point process modeling framework that specifically represents visits to the sites where individuals get in contact and infect each other. Under our model, the number of infections caused by an infectious individual naturally emerges to be overdispersed. Using an efficient sampling algorithm, we demonstrate how to apply Bayesian optimization with longitudinal case data to estimate the transmission rate of infectious individuals at the sites they visit and in their households. Simulations using fine-grained and publicly available demographic data and site locations from Bern, Switzerland showcase the flexibility of our framework. To facilitate research and analyses of other cities and regions, we release an open-source implementation of our framework.
A majority of real life networks are weighted and sparse. The present article aims at characterization of weighted networks based on sparsity, as a measure of inherent diversity, of different network parameters. It utilizes sparsity index defined on ordered degree sequence of simple networks and derives further properties of this index. The range of possible values of sparsity index of any connected network, with edge-count in specific intervals, is worked out analytically in terms of node-count; a pattern is uncovered in corresponding degree sequences to produce highest sparsities. Given the edge-weight frequency distribution of a network, we have formulated an expression of the sparsity index of edge-weights. Its properties are analyzed under different distributions of edge-weights. For example, the upper and lower bounds of sparsity index of edge-weights of a network, having all distinct edge-weights, is determined in terms of its node-count and edge density. The article highlights that this summary index with low computational cost, computed on different network parameters, is useful to reveal different structural and organizational aspects of networks for performing analysis. An application of this index has been demonstrated through overlapping community detection of networks. The results validated on artificial and real-world networks show its efficacy.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
