We consider the optimisation problem of adding k links to a given network, such that the resulting effective graph resistance is as small as possible. The problem was recently proven to be NP-hard, such that obtaining optimal solutions through brute-force methods is infeasible for any graph of realistic size. It is common in such cases to use a simple greedy algorithm to obtain an approximation of the optimal solution. It is known that if the considered problem is submodular, the quality of the greedy solution can be guaranteed. However, the considered optimisation problem is known to be not submodular. For such cases one can use the notion of generalized submodularity, which is captured by the submodularity ratio γ. A performance bound, which is a function of γ, also exists in case of generalized submodularity. In this paper we give an example of a family of graphs where the submodularity ratio approaches zero, implying that the solution quality of the greedy algorithm cannot be guaranteed through the concept of generalized submodularity, at least, according to the currently available theoretical results. Finally, we conduct some numerical experiments on small graphs. Even though we lack a theory to guarantee the performance of the greedy algorithm, the experiments show that the greedy algorithm leads to near-optimal solutions.

We propose a generalization of the adaptive N-Intertwined Mean-Field Approximation (aNIMFA) model studied in Achterberg and Sensi [Nonlinear Dyn. 111, 12657-12670 (2023)] to a heterogeneous network of communities. In particular, the multigroup aNIMFA model describes the impact of both local and global disease awareness on the spread of a disease in a network. We obtain results on the existence and stability of the equilibria of the system, in terms of the basic reproduction number R 0 . Assuming individuals have no reason to decrease their contacts in the absence of disease, we show that the basic reproduction number R 0 is equivalent to the basic reproduction number of the NIMFA model on static networks. Based on numerical simulations, we demonstrate that with just two communities periodic behavior can occur, which contrasts the case with only a single community, in which periodicity was ruled out analytically. We also find that breaking connections between communities is more fruitful compared to breaking connections within communities to reduce the disease outbreak on dense networks, but both strategies are viable in networks with fewer links. Finally, we emphasize that our method of modeling adaptivity is not limited to Susceptible-Infected-Susceptible models, but has huge potential to be applied in other compartmental models in epidemiology.

The interplay between disease spreading and personal risk perception is of key importance for modelling the spread of infectious diseases. We propose a planar system of ordinary differential equations (ODEs) to describe the co-evolution of a spreading phenomenon and the average link density in the personal contact network. Contrary to standard epidemic models, we assume that the contact network changes based on the current prevalence of the disease in the population, i.e. the network adapts to the current state of the epidemic. We assume that personal risk perception is described using two functional responses: one for link-breaking and one for link-creation. The focus is on applying the model to epidemics, but we also highlight other possible fields of application. We derive an explicit form for the basic reproduction number and guarantee the existence of at least one endemic equilibrium, for all possible functional responses. Moreover, we show that for all functional responses, limit cycles do not exist. This means that our minimal model is not able to reproduce consequent waves of an epidemic, and more complex disease or behavioural dynamics are required to reproduce epidemic waves.

The effective graph resistance, also known as the Kirchhoff index, is metric that is used to quantify the robustness of a network. We show that the optimisation problem of minimizing the effective graph resistance of a graph by adding a fixed number of links, is NP-hard.

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.

We analyze continuous-time Markovian ϵ-SIS epidemics with self-infections on the complete graph. The majority of the graphs are analytically intractable, but many physical features of the ϵ-SIS process observed in the complete graph can occur in any other graph. In this work, we illustrate that the timescales of the ϵ-SIS process are related to the eigenvalues of the tridiagonal matrix of the SIS Markov chain. We provide a detailed analysis of all eigenvalues and illustrate that the eigenvalues show staircases, which are caused by the nearly degenerate (but strictly distinct) pairs of eigenvalues. We also illustrate that the ratio between the second-largest and third-largest eigenvalue is a good indicator of metastability in the ϵ-SIS process. Additionally, we show that the epidemic threshold of the Markovian ϵ-SIS process can be accurately approximated by the effective infection rate for which the third-largest eigenvalue of the transition matrix is the smallest. Finally, we derive the exact mean-field solution for the ϵ-SIS process on the complete graph, and we show that the mean-field approximation does not correctly represent the metastable behavior of Markovian ϵ-SIS epidemics.

During the outbreak of a virus, perhaps the greatest concern is the future evolution of the epidemic: How many people will be infected and which regions will be affected the most? The accurate prediction of an epidemic enables targeted disease countermeasures (e.g., allocating medical staff and quarantining). But when can we trust the prediction of an epidemic to be accurate? In this work we consider susceptible-infected-susceptible (SIS) and susceptible-infected-removed (SIR) epidemics on networks with time-invariant spreading parameters. (For time-varying spreading parameters, our results correspond to an optimistic scenario for the predictability of epidemics.) Our contribution is twofold. First, accurate long-term predictions of epidemics are possible only after the peak rate of new infections. Hence, before the peak, only short-term predictions are reliable. Second, we define an exponential growth metric, which quantifies the predictability of an epidemic. In particular, even without knowing the future evolution of the epidemic, the growth metric allows us to compare the predictability of an epidemic at different points in time. Our results are an important step towards understanding when and why epidemics can be predicted reliably.

Researchers from various scientific disciplines have attempted to forecast the spread of coronavirus disease 2019 (COVID-19). The proposed epidemic prediction methods range from basic curve fitting methods and traffic interaction models to machine-learning approaches. If we combine all these approaches, we obtain the Network Inference-based Prediction Algorithm (NIPA). In this paper, we analyse a diverse set of COVID-19 forecast algorithms, including several modifications of NIPA. Among the algorithms that we evaluated, the original NIPA performed best at forecasting the spread of COVID-19 in Hubei, China and in the Netherlands. In particular, we show that network-based forecasting is superior to any other forecasting algorithm.

We introduce a Markov Modulated Process (MMP) to describe human mobility. We represent the mobility process as a time-varying graph, where a link specifies a connection between two nodes (humans) at any discrete time step. Each state of the Markov chain encodes a certain modification to the original graph. We show that our MMP model successfully captures the main features of a random mobility simulator, in which nodes moves in a square region. We apply our MMP model to human mobility, measured in a library.

The influence of people's individual responses to the spread of contagious phenomena, like the COVID-19 pandemic, is still not well understood. We investigate the Markovian Generalized Adaptive Susceptible-Infected-Susceptible (G-ASIS) epidemic model. The G-ASIS model comprises many contagious phenomena on networks, ranging from epidemics and information diffusion to innovation spread and human brain interactions. The connections between nodes in the G-ASIS model change adaptively over time, because nodes make decisions to create or break links based on the health state of their neighbors. Our contribution is fourfold. First, we rigorously derive the first-order and second-order mean-field approximations from the continuous-time Markov chain. Second, we illustrate that the first-order mean-field approximation fails to approximate the epidemic threshold of the Markovian G-ASIS model accurately. Third, we show that the second-order mean-field approximation is a qualitative good approximation of the Markovian G-ASIS model. Finally, we discuss the Adaptive Information Diffusion (AID) model in detail, which is contained in the G-ASIS model. We show that, similar to most other instances of the G-ASIS model, the AID model possesses a unique steady state, but that in the AID model, the convergence time toward the steady state is very large. Our theoretical results are supported by numerical simulations.

At the moment of writing, the future evolution of the COVID-19 epidemic is unclear. Predictions of the further course of the epidemic are decisive to deploy targeted disease control measures. We consider a network-based model to describe the COVID-19 epidemic in the Hubei province. The network is composed of the cities in Hubei and their interactions (e.g., traffic flow). However, the precise interactions between cities is unknown and must be inferred from observing the epidemic. We propose the Network-Inference-Based Prediction Algorithm (NIPA) to forecast the future prevalence of the COVID-19 epidemic in every city. Our results indicate that NIPA is beneficial for an accurate forecast of the epidemic outbreak.

In the classical susceptible-infected-susceptible (SIS) model, a disease or infection spreads over a given, mostly fixed graph. However, in many real complex networks, the topology of the underlying graph can change due to the influence of the dynamical process. In this paper, besides the spreading process, the network adaptively changes its topology based on the states of the nodes in the network. An entire class of link-breaking and link-creation mechanisms, which we name Generalized Adaptive SIS (G-ASIS), is presented and analyzed. For each instance of G-ASIS using the complete graph as initial network, the relation between the epidemic threshold and the effective link-breaking rate is determined to be linear, constant, or unknown. Additionally, we show that there exist link-breaking and link-creation mechanisms for which the metastable state does not exist. We confirm our theoretical results with several numerical simulations.