Using contact tracing data provided by the Cyprus Ministry of Health, infection trees for the first four waves of the COVID-19 epidemic are constructed. In these trees, nodes represent infected individuals, while links indicate the direction of transmission between them. For each infection tree of N nodes, the hopcount distribution from the root node to all other nodes is calculated. The empirical distribution is then compared to the hopcount distribution of infection trees generated by a non-Markovian SI process on a complete graph, with Weibull infection times characterized by a shape parameter α. We compute the values of the shape parameter α that best fit the empirical distribution and find that only values of α>1 are obtained, while the Markovian case is characterized by α=1. A Weibull distributed infection time with shape parameter α>1 is characterized by a unimodal density function with a peak at finite time, consistent with previous findings in the literature. Our analysis therefore suggests that the spreading process is most likely governed by non-Markovian dynamics, and that non-Markovianity can be detected solely from the topology of the infection trees. Finally, we analyze the evolution of the empirical distribution of the number of secondary infections caused by each node in the infection trees across different time windows to estimate the effective reproduction number. In practice, the average number of secondary infections seems to often provide a lower bound of the reproduction number computed by the Cyprus Ministry of Health. When the last level of the trees, composed predominantly of terminal nodes that do not generate further infections, is excluded, the estimate reflects more accurately the dynamics of the epidemic.

The shortest path problem is related to many dynamic processes on networks, ranging from routing in communication networks to signaling in molecular interaction networks. When the network is fully known, the shortest path problem can be solved precisely and in polynomial time. If, however, the network of interest is only partially observable, the shortest path problem is no longer straightforward. Inspired by the shortest path problem in partially observable networks, we investigate the geometric properties of shortest paths in Euclidean soft random geometric graphs (SRGGs). We find that shortest paths are aligned along geodesic curves connecting shortest path end points. The strength of the shortest path alignment, as quantified by the average distance to geodesic from shortest path nodes and the average path stretch, is higher for larger SRGGs with short-range connections. In addition, we find that the strength of the shortest path alignment is nonmonotonic with respect to the average degree of the SRGG. Based on these observations, we establish the conditions under which the alignment of shortest paths may be sufficiently strong to allow the identification of shortest path nodes based on their proximity to geodesic curves. We show that in partially observable networks with uncertain node positions, our geometric approach can outperform network-based shortest path algorithms. In practical settings, our findings may have applications to navigation, wireless routing, and flow characterization in infrastructure networks.

A threshold graph is generated from a single node by repeatedly adding either a node i connected to all existing nodes with a common link weight w_i > 0 or a node i connected to none. Let G_w be a weighted threshold graph encoded by the weight vector w = (w₁, w₂, …, w_N ) with w_i ≥ 0. A closed-form expression for the pseudoinverse of its Laplacian matrix Q_w is derived via spectral decomposition, which yields an explicit formula for the effective resistance matrix Ω_w. We present a detailed structural characterization of the matrix Ω_w and determine a subset of the spectrum of the matrix Ω_w in terms of the weights w_i . As an application, we show that when the missing links of a threshold graph are sequentially added in nondecreasing order of effective resistance, the threshold property of the graph is preserved at each step until the complete graph of the same size is obtained.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.