The dismantling network problem only asks the minimal vertex set of a graph after removing which the remaining graph will break into connected components of sub-extensive size, but we should also consider the efficiency of intermediate states during the entire dismantling process, which is measured by the general performance R in this paper. In order to improve the general performance of the belief-propagation decimation (BPD) algorithm, we introduce a compound algorithm (CA) mixing the BPD and the node explosive percolation (NEP) algorithm. In this CA, the NEP algorithm will rearrange and optimize the head part of a dismantling sequence given by the BPD. Two ancestor algorithms are connected at the joint point where the general performance can be optimized. It dismantles a graph to small pieces as quickly as the BPD, and it is with the efficiency of the NEP during the entire dismantling process. We find that a wise joint point is where the BPD breaks the original graph to subgraphs no longer larger than the 1% of the original one. We refer the CA with this settled joint point as the fast CA and the fast CA is in the same complexity class with the BPD algorithm. The computation on some real-world instances also exhibits that using the fast CA to optimize the intermediate process of a dismantling algorithm is an effective approach.
A signed network represents how a set of nodes are connected by two logically contradictory types of links: positive and negative links. Examples are signed product networks where two products can be complementary (purchased together) or substitutable (purchased instead of each other). Such contradictory types of links may play dramatically different roles in the spreading process of information, opinion etc. In this work, we propose a Self-Avoiding Pruning (SAP) random walk on a signed network to model e.g. a user's purchase activity on a signed network of products and information/opinion diffusion on a signed social network. Specifically, a SAP walk starts at a random node. At each step, the walker moves to a positive neighbour that is randomly selected and its previously visited node together with its negative neighbours are removed. We explored both analytically and numerically how signed network features such as link density and degree distribution influence the key performance of a SAP walk: the evolution of the pruned network resulting from the node removals of a SAP walk, the length of a SAP walk and the visiting probability of each node. Our findings in signed network models are further partially verified in two real-world signed networks.
We propose a targeted intervention protocol where recovery is restricted to individuals that have the least number of infected neighbours. Our recovery strategy is highly efficient on any kind of network, since epidemic outbreaks are minimal when compared to the baseline scenario of spontaneous recovery. In the case of spatially embedded networks, we find that an epidemic stays strongly spatially confined with a characteristic length scale undergoing a random walk. We demonstrate numerically and analytically that this dynamics leads to an epidemic spot with a flat surface structure and a radius that grows linearly with the spreading rate.
Many progresses in the understanding of epidemic spreading models have been obtained thanks to numerous modeling efforts and analytical and numerical studies, considering host populations with very different structures and properties, including complex and temporal interaction networks. Moreover, a number of recent studies have started to go beyond the assumption of an absence of coupling between the spread of a disease and the structure of the contacts on which it unfolds. Models including awareness of the spread have been proposed, to mimic possible precautionary measures taken by individuals that decrease their risk of infection, but have mostly considered static networks. Here, we adapt such a framework to the more realistic case of temporal networks of interactions between individuals. We study the resulting model by analytical and numerical means on both simple models of temporal networks and empirical time-resolved contact data. Analytical results show that the epidemic threshold is not affected by the awareness but that the prevalence can be significantly decreased. Numerical studies highlight however the presence of very strong finite-size effects, in particular for the more realistic synthetic temporal networks, resulting in a significant shift of the effective epidemic threshold in the presence of risk awareness. For empirical contact networks, the awareness mechanism leads as well to a shift in the effective threshold and to a strong reduction of the epidemic prevalence.
Spreading is a ubiquitous process in the social, biological and technological systems. Therefore, identifying influential spreaders, which is important to prevent epidemic spreading and to establish effective vaccination strategies, is full of theoretical and practical significance. In this paper, a weighted h-index centrality based on virtual nodes extension is proposed to quantify the spreading influence of nodes in complex networks. Simulation results on real-world networks reveal that the proposed method provides more accurate and more consistent ranking than the five classical methods. Moreover, we observe that the monotonicity and the computational complexity of our measure can also yield excellent performance.
Complex networks are the subject of fundamental interest from the scientific community at large. Several metrics have been introduced to characterize the structure of these networks, such as the degree distribution, degree correlation, path length, clustering coefficient, centrality measures etc. Another important feature is the presence of network symmetries. In particular, the effect of these symmetries has been studied in the context of network synchronization, where they have been used to predict the emergence and stability of cluster synchronous states. Here we provide theoretical, numerical, and experimental evidence that network symmetries play a role in a substantially broader class of dynamical models on networks, including epidemics, game theory, communication, and coupled excitable systems. Namely, we see that in all these models, nodes that are related by a symmetry relation show the same time-averaged dynamical properties. This discovery leads us to propose reduction techniques for exact, yet minimal, simulation of complex networks dynamics, which we show are effective in order to optimize the use of computational resources, such as computation time and memory.
Personal Rapid Transit (PRT) is a promising form of urban transport. Its operation consists in the use of small unmanned vehicles which convey the passengers among stations within a dedicated network. Various aspects of the PRT network performance are frequently evaluated using the discrete-event simulation. The paper supports the need of establishing some reference models for the simulation of PRT networks, targeted mainly towards the needs of the research on network management algorithms. Three models of such PRT network models are proposed and discussed. The presented models can play the role of benchmarks which would be very useful for comparative evaluation of heuristic control algorithms, developed by different research groups.
We present an analysis of risk levels on multi-lane roads. The aim is to use the crash metrics to understand which direction of the flow mainly influences the safety in traffic flow. In fact, on multi-lane highways interactions among vehicles occur also with lane changing and we show that they strongly affect the level of potential conflicts. In particular, in this study we consider the Time-To-Collision as risk metric and we use the experimental data collected on the A3 German highway.