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.

Even though Kemeny’s constant was first discovered in Markov chains and expressed by Kemeny in terms of mean first passage times on a graph, it can also be expressed using the pseudo-inverse of the Laplacian matrix representing the graph, which facilitates the calculation of a sharp upper bound of Kemeny’s constant. We show that for certain classes of graphs, a previously found bound is tight, which generalises previous results for bipartite and (generalised) windmill graphs. Moreover, we show numerically that for real-world networks, this bound can be used to find good numerical approximations for Kemeny’s constant. For certain graphs consisting of up to 100 K nodes, we find a speedup of a factor 30, depending on the accuracy of the approximation that can be achieved. For networks consisting of over 500 K nodes, the approximation can be used to estimate values for the Kemeny constant, where exact calculation is no longer feasible within reasonable computation time

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.

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.

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.

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.

Cloud-native technologies are widely considered the ideal candidates for the future of vertical application development due to their boost in flexibility, scalability, and especially cost efficiency. Since multi-site support is paramount for 5G, we employ a multi-cluster model that scales on demand, shifting the boundaries of both horizontal and vertical scaling for shared resources. Our approach is based on the liquid computing paradigm, which has the benefit of adapting to the changing environment. Despite being a decentralized deployment shared across data centers, the 5G mobile core can be managed as a single cluster entity running in a public cloud. We achieve this by following the cloud-native patterns for declarative configuration based on Kubernetes APIs and on-demand resource allocation. Moreover, in our setup, we analyze the offloading of both the Open5GS user and control plane functions under two different peering scenarios. A significant improvement in terms of latency and throughput is achieved for the in-band peering, considering the traffic between clusters is ensured by the Liqo control plane through a VPN tunnel. We also validate three end-to-end network slicing use cases, showcasing the full 5G core automation and leveraging the capabilities of Kubernetes multi-cluster deployments and inter-service monitoring through the applied service mesh solution.

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.

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.

In this paper we investigate the controller placement problem on networks using controller reachability as the network performance metric. This metric is defined as the probability that each node can reach at least one controller, given that each link is operational with a fixed probability. By exploring placements for more than 100 real-world networks and by varying the number of controllers from two to five, we find that controller reachability varies greatly with different placements. Obviously, increasing the number of controllers increases the controller reachability. However, the extent of this increase depends on the strategy with which the controllers are placed. The findings indicate that efficient controller placement strategies should be developed to ensure good network performance. In this research, we propose four controller placement strategies. One strategy is based on topological network metrics: node degree and path length between controllers and nodes. The other three heuristic strategies are the greedy algorithm, the classic genetic algorithm and the heuristic genetic algorithm. By validating strategies on real-world networks, we find that all four strategies work well to solve the controller placement problem with respect to controller reachability.

For this study, we investigated efficient strategies for the recovery of individual links in power grids governed by the direct current (DC) power flow model, under random link failures. Our primary objective was to explore the efficacy of recovering failed links based solely on topological network metrics. In total, we considered 13 recovery strategies, which encompassed 2 strategies based on link centrality values (link betweenness and link flow betweenness), 8 strategies based on the products of node centrality values at link endpoints (degree, eigenvector, weighted eigenvector, closeness, electrical closeness, weighted electrical closeness, zeta vector, and weighted zeta vector), and 2 heuristic strategies (greedy recovery and two-step greedy recovery), in addition to the random recovery strategy. To evaluate the performance of these proposed strategies, we conducted simulations on three distinct power systems: the IEEE 30, IEEE 39, and IEEE 118 systems. Our findings revealed several key insights: Firstly, there were notable variations in the performance of the recovery strategies based on topological network metrics across different power systems. Secondly, all such strategies exhibited inferior performance when compared to the heuristic recovery strategies. Thirdly, the two-step greedy recovery strategy consistently outperformed the others, with the greedy recovery strategy ranking second. Based on our results, we conclude that relying solely on a single metric for the development of a recovery strategy is insufficient when restoring power grids following link failures. By comparison, recovery strategies employing greedy algorithms prove to be more effective choices.

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.

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.

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.

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.

Network controllability and its robustness have been widely studied. However, analytical methods to calculate network controllability with respect to node in- and out-degree targeted removals are currently lacking. This paper develops methods, based on generating functions for the in- and out-degree distributions, to approximate the minimum number of driver nodes needed to control directed networks, during node in- and out-degree targeted removals. By validating the proposed methods on synthetic and real-world networks, we show that our methods work reasonably well. Moreover, when the fraction of the removed nodes is below 10% the analytical results of random removals can also be used to predict the results of targeted node removals.

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.

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.

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).