The shortest path problem is related to many dynamic processes on networks, ranging from routing in communication networks to signaling in molecular interaction networks. When the network is fully known, the shortest path problem can be solved precisely and in polynomial time. If, however, the network of interest is only partially observable, the shortest path problem is no longer straightforward. Inspired by the shortest path problem in partially observable networks, we investigate the geometric properties of shortest paths in Euclidean soft random geometric graphs (SRGGs). We find that shortest paths are aligned along geodesic curves connecting shortest path end points. The strength of the shortest path alignment, as quantified by the average distance to geodesic from shortest path nodes and the average path stretch, is higher for larger SRGGs with short-range connections. In addition, we find that the strength of the shortest path alignment is nonmonotonic with respect to the average degree of the SRGG. Based on these observations, we establish the conditions under which the alignment of shortest paths may be sufficiently strong to allow the identification of shortest path nodes based on their proximity to geodesic curves. We show that in partially observable networks with uncertain node positions, our geometric approach can outperform network-based shortest path algorithms. In practical settings, our findings may have applications to navigation, wireless routing, and flow characterization in infrastructure networks.

The node-reliability polynomial nRelG(p) measures the probability that a connected network remains connected given that each node functions independently with probability p. Computing node-reliability polynomials nRelG(p) exactly is NP-hard. Here we propose efficient approximations. First, we develop an accurate Monte Carlo simulation, which is accelerated by incorporating a Laplace approximation that captures the polynomial’s main behavior. We also introduce three degree-based stochastic approximations (Laplace, arithmetic, and geometric), which leverage the degree distribution to estimate nRelG(p) with low complexity. Beyond approximations, our framework addresses the reliability-based Global Robustness Improvement Problem (k-GRIP) by selecting exactly k links to add to a given graph so as to maximize its node reliability. A Greedy Lowest-Degree Pairing Link Addition (Greedy-LD) Algorithm, is proposed which offers a computationally efficient and practically effective heuristic, particularly suitable for large-scale networks.

Two approximations for network reliability polynomials, only based upon the knowledge of the degree vector of the graph, are compared: the first-order approximation by Brown et al. and our stochastic approximation. Our method is an extension of the connectivity probability of Erdős–Rènyi random graphs. Both approximations are shown to upper bound the actual reliability polynomial and are increasingly accurate for dense and large graphs. Moreover, the first-order approximation is always sharper or at least as good as the stochastic approximation, whereas the stochastic approximation is computationally easier. Our stochastic approximation (2.2) can determine the critical operational probability under which the graph is disconnected almost surely for any graph and an approximation for the number F_j of sets of j links whose removal retains the graph G connected, which is helpfull because the exact computation of F_j is NP-hard.

In 2009, Shao et al. (Phys Rev Lett 103(1):018701, 2009) introduced the Non-consensus opinion (NCO) model, which allows different opinions to coexist in the steady state. We propose a mean-field-based dynamical model for the NCO model on networks with low degree correlation, which reveals the mechanism of opinion formation in the NCO model. This mean-field model provides a new way of estimating important system properties such as the fraction of a certain opinion F, the critical threshold f_c, and the size of the largest connected cluster for a given opinion s₁. It offers an accurate estimation in less time than the Monte Carlo simulations. The scale invariance of the NCO model is discussed. The variation in the degree of nodes holding different opinions in the dynamics of the NCO model is investigated. The trends in the dynamics of the NCO model are also revealed. This approach can be applied to real-world social networks, providing a method of analyzing opinion dynamics in human society.

pinion dynamics models study how the interaction among people influences the opinion formation process. In most opinion dynamics models, only one opinion can exist in the steady state, which is different from the real-life opinion formation process. In 2009, Shao et at. introduced a Non-Consensus Opinion (NCO) model, which allows different opinions to coexist in the steady state. This paper extends the NCO model by introducing a special type of nodes, namely Byzantine nodes, to play the role of dishonest people. We perform simulations on three different network models: small-scale graphs, Erdős-Rényi random graphs and scale-free networks. We find a new steady state for the NCO model: the cyclic steady state. The cyclic behavior of the NCO and Byzantine NCO model is discussed, including a method to generate networks with extremely long cycle lengths. Other properties of the Byzantine NCO model, such as the probability of cyclic behavior and the final opinion distribution, are also studied. We find that the introduction of Byzantine nodes generally steers towards a more balanced steady state and increases the probability of cyclic behavior. The latter is particularly problematic in communication systems, where the large cycle lengths may cause a very slow consensus process and thus stalling future communications.