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.

Evaluating the performance of quantum devices is an important step towards scaling quantum devices and eventually using them in practice. The great number of available quantum metrics and the different hardware technologies used to develop quantum computers complicate this evaluation. In addition, different computational paradigms implement quantum operations in different ways. A prominent quantum metric is given by the Q-score metric of Atos. This metric was originally introduced as a standalone way to benchmark devices using the Max-Cut problem. In this work, we show that the Q-score defines a framework of quantum metrics, which allows benchmarking using different problems, user settings and solvers. To showcase the applicability of the framework, we showcase a second Q-score in this framework, called the Q-score Max-Clique. This yields, to our knowledge, the first application-level metric capable of natively comparing three different paradigms of quantum computing. This metric is evaluated on these computational quantum paradigms - quantum annealing, gate-based quantum computing, and photonic quantum computing - and the results are compared to those obtained by classical solvers.

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.

Water Distribution Networks (WDNs) are critical infrastructures that ensure a continuous supply of safe water to homes. In the face of challenges, like water scarcity, establishing resilient networks is imperative, especially in regions vulnerable to water crises. This study evaluates the resilience of network designs through graph theory, including its hydraulic feasibility using EPANET software, an aspect often overlooked. Novel mathematical algorithms, including Resilience by Design (RbD) and Resilience-strengthening (RS) algorithms, provide cost-effective and resilient network designs, even with budget constraints. A novel metric, Water Availability (WA), is introduced to offer a comprehensive measure of network resilience, thereby addressing ongoing discrepancies in resilience evaluation methods. Practical benefits are illustrated through a case study in which a resilient-by-design reclaimed water network is created, and an existing equivalent non-resilient network is improved. The resilient-by-design network demonstrates remarkably better results compared to the equivalent non-resilient design, including up to a 36 % reduction in the probability of service disruptions and a nearly 65 % decrease in the annual average unserved water due to service disruptions. These findings underscore the enormous advantages of a resilience-focused network design approach. When compared to the equivalent non-resilient design, the resilient-by-design network generated effectively safeguards up to a significant 91,700m³ of water from the impacts of water disruption events over a 50-year operational period. In addition, the resilient-by-design WDN solution incurs a subtle decrease in overall costs compared to consuming tap water from the drinking WDN baseline over a 50-year operational period. These findings highlight the cost-effectiveness of the approach, even offering financial benefits. This paper builds on our previous research by expanding its scope to include resilience considerations, providing algorithms that can be easily adapted from reclaimed to drinking WDNs. Ultimately, we contribute to the enhancement of water resource management and infrastructure planning in ever-evolving urban environments.

We introduce two new methods for approximating the all-terminal reliability of undirected graphs. First, we introduce an edge removal process: remove edges at random, one at a time, until the graph becomes disconnected. We show that the expected number of edges thus removed is equal to (Formula presented.), where (Formula presented.) is the number of edges in the graph, and (Formula presented.) is the average of the all-terminal reliability polynomial. Based on this process, we propose a Monte-Carlo algorithm to quickly estimate the graph reliability (whose exact computation is NP-hard). Moreover, we show that the distribution of the edge removal process can be used to quickly approximate the reliability polynomial. We then propose increasingly accurate asymptotics for graph reliability based solely on degree distributions of the graph. These asymptotics are tested against several real-world networks and are shown to be accurate for sufficiently dense graphs. While the approach starts to fail for “subway-like” networks that contain many paths of vertices of degree two, different asymptotics are derived for such networks.

We propose an analytical approach to approximate the average two-Terminal reliability (ATT R) for graphs where a fraction of the nodes is removed. The approximation is based on the generating function of the network's degree distribution under random node removals and stochastic degree-based node removals. Through validation on synthetic graphs, including Erdos Renyi random graphs and Barabasi-Albert graphs, as well as four real-world networks from the Internet Topology Zoo, we observe that the analytical method effectively approximates the average two-Terminal reliability under random node removals for synthetic graphs. In the case of real-world graphs under random and stochastic degree-based node removals or synthetic graphs under stochastic degree-based node removals, the analytical ap-proximation yields reasonably accurate results when the fraction of removed nodes is small, specifically less than 10%, provided that the initial analytical approximation closely aligns with the real ATT R values.

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.

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.

The total effective resistance, also called the Kirchhoff index, provides a robustness measure for a graph G. We consider two optimization problems of adding k new edges to G such that the resulting graph has minimal total effective resistance (i.e., is most robust)—one where the new edges can be anywhere in the graph and one where the new edges need to be incident to a specified focus node. The total effective resistance and effective resistances between nodes can be computed using the pseudoinverse of the graph Laplacian. The pseudoinverse may be computed explicitly via pseudoinversion, yet this takes cubic time in practice and quadratic space. We instead exploit combinatorial and algebraic connections to speed up gain computations in an established generic greedy heuristic. Moreover, we leverage existing randomized techniques to boost the performance of our approaches by introducing a sub-sampling step. Our different graph- and matrix-based approaches are indeed significantly faster than the state-of-the-art greedy algorithm, while their quality remains reasonably high and is often quite close. Our experiments show that we can now process larger graphs for which the application of the state-of-the-art greedy approach was impractical before.

Network controllability and its robustness has been widely studied. However, analytical methods to calculate network controllability with respect to node removals are currently lacking. This paper develops methods, based upon generating functions for the in- and out-degree distributions, to approximate the minimum number of driver nodes needed to control directed networks, during random and targeted node removals. By validating the proposed methods on synthetic and real-world networks, we show that our methods work very well in the case of random node removals and reasonably well in the case of targeted node removals, in particular for moderate fractions of attacked nodes.

In this paper we study encounter-based density estimation using different random walks and analyse the effects of the step-size on the convergence of the density approximation. Furthermore, we analyse different types of random walks, namely, a uniform random walk, with every position equally likely to be visited next, a classical random walk and a quantum-inspired random walk, where the probability distribution for the next state is sampled from a quantum random walk. We find that walks with additional steps lead to faster convergence, but that the type of step, quantum-inspired or classical, has only a marginal effect.

We present a mechanical model for an oscillator with one degree of freedom under the influence of a flowing medium. Under fairly general conditions we show that the ensuing differential equation has at most two limit cycles and we give examples where exactly two limit cycles will occur. The implications of this result are that it is possible for a system of this kind to exhibit galloping even when the so-called Den Hartog criterion of local instability is not satisfied.

Network controllability is a critical attribute of dynamic networked systems. Investigating methods to restore network controllability after network degradation is crucial for enhancing system resilience. In this study, we develop an analytical method based on degree distributions to estimate the minimum fraction of required driver nodes for network controllability under random node additions after the random removal of a subset of nodes. The outcomes of our method closely align with numerical simulation results for both synthetic and real-world networks. Additionally, we compare the efficacy of various node recovery strategies across directed Erdös-Rényi (ER) networks, swarm signaling networks (SSNs), and directed Barabàsi Albert (BA) networks. Our findings indicate that the most efficient recovery strategy for directed ER networks and SSNs is the greedy strategy, which considers node betweenness centrality. Similarly, for directed BA networks, the greedy strategy focusing on node degree centrality emerges as the most efficient. These strategies outperform recovery approaches based on degree centrality or betweenness centrality, as well as the strategy involving random node additions.

The endeavour towards making power distribution systems (PDSs) smarter has made the interdependence on communication network indispensable. Further, prospective high penetration of intermittent renewable energy sources in the form of distributed energy resources (DERs) has resulted in the necessity for smart controllers on such DERs. Inverters are employed for the purpose of DC to AC power conversion in the distribution network where the present standards require these inverters to be smart. In general, distributed energy resource management systems (DERMS) calculate and send set points/operating points to these smart inverters using protocols such as smart energy profile (SEP) 2.0. Given the nature of sites at which such DERs are installed i.e., home area networks with a pool of IoT(Internet-of-Things) devices, the opportunity for a malicious actor to sabotage the operation is typically higher than that for a transmission system. National Electric Sector Cyber-security Organization Resource (NESCOR) has described several failure scenarios and impact analyses in case of cyber attacks on DERs. One such failure scenario concerns attacks on real/reactive power control commands. In this paper, it is demonstrated that physical invariant based security on the edge devices, i.e. smart controllers deployed in DER inverters, is an effective approach to minimize the impact of cyber attacks targeting reactive power control in DER inverters. The proposed defense is generic and can also be extended to attacks on real-power control. The proposed defense is validated on a co-simulation platform (OpenDSS and MATLAB/SIMULINK).

The original version of this Article contained an error in the Abstract, which incorrectly read: ‘Here, we show theoretically, and experimentally with a multi-robot system, that such a transition from simple to complex contagion can also bed observed in an archetypal model of distributed decision-making devoid of any thresholds or nonlinearities.’ The correct form of the fourth sentence in the Abstract is: ‘Here, we show theoretically, and experimentally with a multi-robot system, that such a transition from simple to complex contagion can also be observed in an archetypal model of distributed decision-making devoid of any thresholds or nonlinearities.’