We express the eigenvectors of the Laplacian matrix of a graph as a linear combination of the eigenvectors of the effective resistance matrix of that graph and vice versa. We find partial fraction expansions for the eigenvalues of either matrix in terms of the spectrum of the other matrix as well as the explicit characteristic polynomials and some sums of powers of eigenvalues. We also improve the bounds of the Interlacing Theorem for the eigenvalues of the Laplacian and effective resistance matrix of a same graph.

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.

Threshold graphs are generated from one node by repeatedly adding a node that links to all existing nodes or adding a node without links. In the weighted threshold graph, we add a new node in step i, which is linked to all existing nodes by a link of weight w_i . In this work, we consider the set A_N that contains all Laplacian matrices of weighted threshold graphs of order N. We show that A_N forms a commutative algebra. Using this, we find a common basis of eigenvectors for the matrices in A_N . It follows that the eigenvalues of each matrix in A_N can be represented as a linear transformation of the link weights. In addition, we prove that, if there are just three or fewer different weights, two weighted threshold graphs with the same Laplacian spectrum must be isomorphic.

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.

Many algorithms related to vehicular applications, such as enhanced perception of the environment, benefit from frequent updates and the use of data from multiple vehicles. Federated learning is a promising method to improve the accuracy of algorithms in the context of vehicular networks. However, limited communication bandwidth, varying wireless channel quality, and potential latency requirements may impact the number of vehicles selected for training per communication round and their assigned radio resources. In this work, we characterize the vehicles participating in federated learning based on their importance to the learning process and their use of wireless resources. We then address the joint vehicle selection and resource allocation problem, considering multi-cell networks with multi-user multiple-input multiple-output (MU-MIMO)-capable base stations and vehicles. We propose a “vehicle-beam-iterative” algorithm to approximate the solution to the resulting optimization problem. We then evaluate its performance through extensive simulations, using realistic road and mobility models, for the task of object classification of European traffic signs. Our results indicate that MU-MIMO improves the convergence time of the global model. Moreover, the application-specific accuracy targets are reached faster in scenarios where the vehicles have the same training data set sizes than in scenarios where the data set sizes differ.

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.

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.

Building on the work of Almasan et al. [IEEE Trans. Netw. Sci. Eng. 12, 1649 (2025)10.1109/TNSE.2025.3537162], we propose a continuous-time Markov model for human contact dynamics denoted the continuous random walkers induced temporal graph model (CRWIG). In CRWIG, M walkers move randomly and independently of each other on a Markov graph with N nodes in continuous time. If walkers are in the same state (node of the Markov graph) at time t, a link is created between them in their temporal contact graph G(t), where each walker corresponds to one of the M nodes. We define the exact Markov governing equation that describes the movement of the ensemble of M walkers. We investigate the consequences of the time discretization of CRWIG. We prove that CRWIG is characterized by exponential decay of the initial condition and exponentially tailed intermeeting times of the walkers. We investigate two special cases of CRWIG and derive analytical results supported by simulations. We extend the model to allow for nonexponential sojourn times for the single walkers. The non-Markovian model extension of CRWIG is able to reproduce empirical properties of human mobility observed on data: arbitrary flight length distribution, arbitrary pause-time distribution, and intermeeting time distributions that are power-law with an exponential tail.

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.

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.

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.

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.

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.

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.

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.