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.

Continuous-time Markov processes are governed by the Chapman-Kolmogorov differential equation. We show that replacing the standard time derivative of the governing equation with a Caputo fractional derivative of order 0<α<1, leads to a fractional differential equation whose solution can describe the state probabilities of a class of non-Markovian stochastic processes. We show that the same state probabilities also solve a system of equations that describe semi-Markov processes in which the sojourn times follow a Mittag-Leffler distribution, contrasting the usual Markov processes with exponentially distributed sojourn times. We apply the fractional framework to the ɛ-SIS epidemic process on any contact graph and we propose a microscopic epidemic description in which infection and curing events follow a Mittag-Leffler distribution and are not independent. We analytically prove that the description exactly solves the fractional extension of the Chapman-Kolmogorov differential equation, and we provide an extensive study of how the dependence between events strongly affects the dynamics of the spreading process. We conclude verifying the proposed framework with Monte Carlo simulations.

We study human mobility networks through timeseries of contacts between individuals. Our proposed Random Walkers Induced temporal Graph (RWIG) model generates temporal graph sequences based on independent random walkers that traverse an underlying graph in discrete time steps. Co-location of walkers at a given node and time defines an individual-level contact. RWIG is shown to be a realistic model for temporal human contact graphs, which may place RWIG on a same footing as the Erdos-Renyi (ER) and Barabasi-Albert (BA) models for fixed graphs. Moreover, RWIG is analytically feasible: we derive closed form solutions for the probability distribution of contact graphs.

We derive an expression for the exact probability Pr[i∼j] of a link between a node i with degree di and a node j with degree dj in a graph belonging to the class of Erdos-Rényi G(N,L) random graphs with N nodes and L links. The probability Pr[i∼j] is commonly approximated as didj2L and appears in the formula of Newman's modularity, which plays a crucial rule in community detection in networks. We show that, when applied to graphs not belonging to the class of Erdos-Rényi random graphs, our formula for Pr[i∼j] is considerably more accurate than didj2L and leads to the detection of different clusters or partitions than the original modularity formula.

We examine the Random Walkers Induced temporal Graph (RWIG) model, which generates temporal graphs based on the co-location principle of M independent walkers that traverse the underlying Markov graph with different transition probabilities. Given the assumption that each random walker is in the steady state, we determine the steady-state vector s̃and the Markov transition matrix P _i of each walker w _i that can reproduce the observed temporal network G ₀, . . ., G _{K –1} with the lowest mean squared error. We also examine the performance of RWIG for periodic temporal graph sequences.

We extend the N-intertwined mean-field approximation (NIMFA) for the susceptible-infectious-susceptible (SIS) epidemiological process to time-varying networks. Processes on time-varying networks are often analyzed under the assumption that the process and network evolution happen on different timescales. This approximation is called timescale separation. We investigate timescale separation between disease spreading and topology updates of the network. We introduce the transition times T(r) and T¯(r) as the boundaries between the intermediate regime and the annealed (fast changing network) and quenched (static network) regimes, respectively, for a fixed accuracy tolerance r. By analyzing the convergence of static NIMFA processes, we analytically derive upper and lower bounds for T¯(r). Our results provide insights and bounds on the time of convergence to the steady state of the static NIMFA SIS process. We show that, under our assumptions, the upper-transition time T¯(r) is almost entirely determined by the basic reproduction number R0 of the network. The value of the upper-transition time T¯(r) around the epidemic threshold is large, which agrees with the current understanding that some real-world epidemics cannot be approximated with the aforementioned timescale separation.

Finding the source of an epidemic is important, because correct source identification can help to stop a budding epidemic or prevent new ones. We investigate the backward equations of the N-intertwined mean-field approximation susceptible-infectious-susceptible (SIS) process. The backward equations allow us to trace the epidemic back to its source on networks of sizes up to at least N=1500. Additionally, we show that the source of the "more realistic"Markovian SIS model cannot feasibly be found, even in a "best-case scenario,"where the infinitesimal generator Q, which completely describes the epidemic process and the underlying contact network, is known. The Markovian initial condition s(0), which reveals the epidemic source, can be found analytically when the viral state vector s(t) is known at some time t as s(0)=s(t)e-Qt. However, s(0) can hardly be computed, except for small times t. The numerical errors are largely due to the matrix exponential e-Qt, which is severely ill-behaved.

Although eigenvectors belong to the core of linear algebra, relatively few closed-form expressions exist, which we bundle and discuss here. A particular goal is their interpretation for graph-related matrices, such as the adjacency matrix of an undirected, possibly weighted graph.

Federated learning is an effective method to train a machine learning model without requiring to aggregate the potentially sensitive data of agents in a central server. However, the limited communication bandwidth, the hardware of the agents and a potential application-specific latency requirement impact how many and which agents can participate in the learning process at each communication round. In this paper, we propose a selection metric characterizing each agent’s importance with respect to both the learning process and the resource efficiency of its wireless communication channel. Leveraging this importance metric, we formulate a general agent selection optimization problem, which can be adapted to different environments with latency or resource-oriented constraints. Considering an example wireless environment with latency constraints, the agent selection problem reduces to the 0/1 Knapsack problem, which we solve with a fully polynomial approximation. We then evaluate the agent selection policy in different scenarios, using extensive simulations for an example task of object classification of European traffic signs. The results indicate that agent selection policies which consider both learning and channel aspects provide benefits in terms of the attainable global model accuracy and/or the time needed to achieve a targeted accuracy level. However, in scenarios where agents have a limited number of data samples or where the latency requirement is very stringent, a pure learning-based agent selection policy is shown to be more beneficial during the early or late stages of the learning process.

Epidemic forecasts are only as good as the accuracy of epidemic measurements. Is epidemic data, particularly COVID-19 epidemic data, clean, and devoid of noise? The complexity and variability inherent in data collection and reporting suggest otherwise. While we cannot evaluate the integrity of the COVID-19 epidemic data in a holistic fashion, we can assess the data for the presence of reporting delays. In our work, through the analysis of the first COVID-19 wave, we find substantial reporting delays in the published epidemic data. Motivated by the desire to enhance epidemic forecasts, we develop a statistical framework to detect, uncover, and remove reporting delays in the infectious, recovered, and deceased epidemic time series. Using our framework, we expose and analyze reporting delays in eight regions significantly affected by the first COVID-19 wave. Further, we demonstrate that removing reporting delays from epidemic data by using our statistical framework may decrease the error in epidemic forecasts. While our statistical framework can be used in combination with any epidemic forecast method that intakes infectious, recovered, and deceased data, to make a basic assessment, we employed the classical SIRD epidemic model. Our results indicate that the removal of reporting delays from the epidemic data may decrease the forecast error by up to 50%. We anticipate that our framework will be indispensable in the analysis of novel COVID-19 strains and other existing or novel infectious diseases.

Except for the empty graph, we show that the orthogonal matrix X of the adjacency matrix A determines that adjacency matrix completely, but not always uniquely. The proof relies on interesting properties of the Hadamard product Ξ = X ◦ X. As a consequence of the theory, we show that irregular co-eigenvector graphs exist only if the number of nodes N ≥ 6. Coeigenvector graphs possess the same orthogonal eigenvector matrix X, but different eigenvalues of the adjacency matrix. Co-eigenvector graphs are the dual of co-spectral graphs, that share all eigenvalues of the adjacency matrix, but possess a different orthogonal eigenvector matrix. We deduce general properties of co-eigenvector graph and start to enumerate all co-eigenvector graphs on N = 6 and N = 7 nodes. Finally, we list many open problems.

Epilepsy surgery is the treatment of choice for drug-resistant epilepsy patients, but up to 50% of patients continue to have seizures one year after the resection. In order to aid presurgical planning and predict postsurgical outcome on a patient-by-patient basis, we developed a framework of individualized computational models that combines epidemic spreading with patient-specific connectivity and epileptogeneity maps: the Epidemic Spreading Seizure and Epilepsy Surgery framework (ESSES). ESSES parameters were fitted in a retrospective study (N = 15) to reproduce invasive electroencephalography (iEEG)-recorded seizures. ESSES reproduced the iEEG-recorded seizures, and significantly better so for patients with good (seizure-free, SF) than bad (nonseizure-free, NSF) outcome. We illustrate here the clinical applicability of ESSES with a pseudo-prospective study (N = 34) with a blind setting (to the resection strategy and surgical outcome) that emulated presurgical conditions. By setting the model parameters in the retrospective study, ESSES could be applied also to patients without iEEG data. ESSES could predict the chances of good outcome after any resection by finding patient-specific model-based optimal resection strategies, which we found to be smaller for SF than NSF patients, suggesting an intrinsic difference in the network organization or presurgical evaluation results of NSF patients. The actual surgical plan overlapped more with the model-based optimal resection, and had a larger effect in decreasing modeled seizure propagation, for SF patients than for NSF patients. Overall, ESSES could correctly predict 75% of NSF and 80.8% of SF cases pseudo-prospectively. Our results show that individualised computational models may inform surgical planning by suggesting alternative resections and providing information on the likelihood of a good outcome after a proposed resection. This is the first time that such a model is validated with a fully independent cohort and without the need for iEEG recordings.

Although resource management schemes and algorithms for networks are well established, we present two novel ideas, based on graph theory, that solve inverse all shortest path problem. Given a symmetric and non-negative demand matrix, the inverse all shortest path problem (IASPP) asks to find a weighted adjacency matrix of a graph such that all the elements in the corresponding shortest path weight matrix are not larger than those of the demand matrix. In contrast to many inverse shortest path problems that are NP-complete, we propose the Descending Order Recovery (DOR) that exactly solves a variant of IASPP, referred to as optimised IASPP. The network provided by DOR minimized the number of links and the sum of the link weights among all the graphs with the same shortest path weight matrix. Our second proposed algorithm, Omega-based Link Removal (OLR), solves the optimised IASPP by utilising the effective resistance from flow networks. The essence of our idea is the applications of properties of flow networks, such as electrical power grids, to compute the needed resources in path networks subject to end-To-end demands, such as telecommunication networks where quality of service constraints specify the end-To-end demands.

Predicting future dynamics on networks is challenging, especially when the complete and accurate network topology is difficult to obtain in real-world scenarios. Moreover, the higher-order interactions among nodes, which have been found in a wide range of systems in recent years, such as the nets connecting multiple modules in circuits, further complicate accurate prediction of dynamics on hypergraphs. In this work, we proposed a two-step method called the topology-agnostic higher-order dynamics prediction (TaHiP) algorithm. The observations of nodal states of the target hypergraph are used to train a surrogate matrix, which is then employed in the dynamical equation to predict future nodal states in the same hypergraph, given the initial nodal states. TaHiP outperforms three latest Transformer-based prediction models in different real-world hypergraphs. Furthermore, experiments in synthetic and real-world hypergraphs show that the prediction error of the TaHiP algorithm increases with mean hyperedge size of the hypergraph, and could be reduced if the hyperedge size distribution of the hypergraph is known.

We propose a linear clustering process on a network consisting of two opposite forces: attraction and repulsion between adjacent nodes. Each node is mapped to a position on a one-dimensional line. The attraction and repulsion forces move the nodal position on the line, depending on how similar or different the neighbourhoods of two adjacent nodes are. Based on each node position, the number of clusters in a network and each node's cluster membership is estimated. The performance of the proposed linear clustering process is benchmarked on synthetic networks against widely accepted clustering algorithms such as modularity, Leiden method, Louvain method and the non-back tracking matrix. The proposed linear clustering process outperforms the most popular modularity-based methods, such as the Louvain method, on synthetic and real-world networks, while possessing a comparable computational complexity.

Modelling temporal networks is an open problem that has attracted researchers from a diverse range of fields. Currently, the existing modelling solutions of time-evolving graphs do not allow us to provide an accurate graph sequence. In this paper, we examine the network dynamics from a system identification perspective. We prove that any periodic graph sequence can be accurately modelled as a linear process. We propose two algorithms, called Subspace Graph Generator (SG-gen) and Linear Periodic Graph Generator (LPG-gen), for modelling periodic graph sequences and provide their performance on artificial graph sequences. We further propose a novel model, called Linear Graph Generator (LG-gen), that can be applied to non-periodic graph sequences. Our experiments on artificial and real networks demonstrate that many temporal networks can be accurately approximated by periodic graph sequences.

Interpreting natural language is an increasingly important task in computer algorithms due to the growing availability of unstructured textual data. Natural Language Processing (NLP) applications rely on semantic networks for structured knowledge representation. The fundamental properties of semantic networks must be taken into account when designing NLP algorithms, yet they remain to be structurally investigated. We study the properties of semantic networks from ConceptNet, defined by 7 semantic relations from 11 different languages. We find that semantic networks have universal basic properties: they are sparse, highly clustered, and many exhibit power-law degree distributions. Our findings show that the majority of the considered networks are scale-free. Some networks exhibit language-specific properties determined by grammatical rules, for example networks from highly inflected languages, such as e.g. Latin, German, French and Spanish, show peaks in the degree distribution that deviate from a power law. We find that depending on the semantic relation type and the language, the link formation in semantic networks is guided by different principles. In some networks the connections are similarity-based, while in others the connections are more complementarity-based. Finally, we demonstrate how knowledge of similarity and complementarity in semantic networks can improve NLP algorithms in missing link inference.

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.

Epilepsy surgery is the treatment of choice for drug-resistant epilepsy patients, but only leads to seizure freedom for roughly two in three patients. To address this problem, we designed a patient-specific epilepsy surgery model combining large-scale magnetoencephalography (MEG) brain networks with an epidemic spreading model. This simple model was enough to reproduce the stereo-tactical electroencephalography (SEEG) seizure propagation patterns of all patients (N = 15), when considering the resection areas (RA) as the epidemic seed. Moreover, the goodness of fit of the model predicted surgical outcome. Once adapted for each patient, the model can generate alternative hypothesis of the seizure onset zone and test different resection strategies in silico. Overall, our findings indicate that spreading models based on patient-specific MEG connectivity can be used to predict surgical outcomes, with better fit results and greater reduction on seizure propagation linked to higher likelihood of seizure freedom after surgery. Finally, we introduced a population model that can be individualized by considering only the patient-specific MEG network, and showed that it not only conserves but improves the group classification. Thus, it may pave the way to generalize this framework to patients without SEEG recordings, reduce the risk of overfitting and improve the stability of the analyses.

In this paper, we focus on the link density in random geometric graphs (RGGs) with a distance-based connection function. After deriving the link density in D dimensions, we focus on the two-dimensional (2D) and three-dimensional (3D) space and show that the link density is accurately approximated by the Fréchet distribution, for any rectangular space. We derive expressions, in terms of the link density, for the minimum number of nodes needed in the 2D and 3D spaces to ensure network connectivity. These results provide first-order estimates for, e.g., a swarm of drones to provide coverage in a disaster or crowded area.