PV

P.F.A. Van Mieghem

info

Please Note

158 records found

Journal article (2026) - Pavlos Alexandros Dimitriou, Matteo D’Alessandro, Brian L. Chang, Valentinos Silvestros, Elisavet Constantinou, Costas Pitris, Panayiotis Kolios, Piet Van Mieghem
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. ...
Journal article (2026) - Robin Persoons, Piet van Mieghem
We consider temporal networks that are a union of disjoint cliques at all times t. We call temporal networks that consist of disjoint cliques temporal clique graphs. We extend the exact solution of mean-field SIS epidemics with self-infections on the complete graph, derived by Prasse et al. [Chaos 31, 063115 (2021)], to all temporal clique graphs. Temporal clique graphs cover a range of commonplace models of network dynamics, including metapopulation models and specifically random-walker-induced temporal graphs. Since the exact solution of mean-field SIS on temporal clique graphs is piecewise (i.e., given by different functions on different intervals), we apply further approximations and find an approximate expression for the expected fraction of infected individuals, called the prevalence y(t), at all times t, with as parameters only the infection rate β, the curing rate δ, and the average size θj of each clique j in the steady state of the network dynamics. Our strongest assumption is that the contact network is static and in its steady state, effectively ignoring all graph dynamics. Despite the drastic assumptions, in ignoring any temporal aspects of the contact network, the approximation is remarkably accurate, when the number of walkers is high. We assess our prevalence approximation (15) and indicate and explain its accuracy. ...
Journal article (2026) - Yingyue Ke, Piet van Mieghem
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 wi > 0 or a node i connected to none. Let Gw be a weighted threshold graph encoded by the weight vector w = (w1, w2, …, wN ) with wi ≥ 0. A closed-form expression for the pseudoinverse of its Laplacian matrix Qw 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 wi . 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. ...
Journal article (2026) - Brian L. Chang, Piet Van Mieghem
Non-Markovian theory provides the most accurate stochastic description of an infection spreading on a contact graph with a general distribution of the infection time and curing time. However, the infection time is not directly measurable and instead the generation time is measured in real-world epidemics. Here we show that if the generation time follows approximately a Weibull distribution with shape parameter α, then the Weibull infection time of the spreading process possesses a similar shape parameter α. For a large list of published generation times in biological, mainly respiratory epidemics, the Weibull shape parameter α is computed, which reveals that nearly always α > 1. The impact of this observation is that a complicated non-Markovian analysis is not needed, because the well-established Markovian case α = 1 provides a lower bound for the epidemic threshold and an upper bound for the basic reproduction number and the nodal infection probabilities in the contact graph. ...
Journal article (2026) - Piet Van Mieghem
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. ...
Journal article (2025) - Piet Van Mieghem, Xinhan Liu
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 Fj of sets of j links whose removal retains the graph G connected, which is helpfull because the exact computation of Fj is NP-hard. ...
Journal article (2025) - Matteo D'Alessandro, Piet Van Mieghem
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 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 0, . . ., G K –1 with the lowest mean squared error. We also examine the performance of RWIG for periodic temporal graph sequences. ...
Journal article (2025) - Anton David Almasan, Sergey Shvydun, Ingo Scholtes, Piet Van Mieghem
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. ...
Journal article (2025) - Yingyue Ke, Piet Van Mieghem
Degree-based graph construction is a fundamental problem in network science. A graph is simple if there are no self-loops and no multiple links between any pair of nodes in the graph. A degree sequence d = (d1 , d2, ... , dN) is graphical if d can be represented as the degree sequence of at least one simple graph, where the graph is called a realization of the sequence d. In this work, we introduce a novel method (LSFGR) for generating simple graphs from graphical degree sequences, focusing additionally on connectedness and on assortativity. LSFGR guarantees connected graphs for all potentially connected degree sequences. In the case where a degree sequence has no simple realization, LSFGR produces graphs with at most one node with self-loops. In addition, the graphs generated from LSFGR characterize real-world networks with medium assortativity. ...
Journal article (2025) - Brian L. Chang, Piet Van Mieghem
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. ...

Monte Carlo, Laplace, and Stochastic Approximations and a Greedy Link-Augmentation Strategy

Journal article (2025) - Xinhan Liu, Robert Kooij, Piet Van Mieghem
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. ...
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. ...
Journal article (2025) - Yingyue Ke, Willem H. Haemers, Piet VAN MIEGHEM
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 wi . In this work, we consider the set AN that contains all Laplacian matrices of weighted threshold graphs of order N. We show that AN forms a commutative algebra. Using this, we find a common basis of eigenvectors for the matrices in AN . It follows that the eigenvalues of each matrix in AN 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. ...
Journal article (2025) - Maria Raftopoulou, José Mairton B. da Silva, Remco Litjens, H. Vincent Poor, Piet Van Mieghem
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. ...
Journal article (2024) - Piet Van Mieghem, Ivan Jokic
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. ...
Journal article (2024) - Zili Zhou, Cong Li, Piet Van Mieghem, Xiang Li
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. ...
Journal article (2024) - Ana P. Millán, Elisabeth C.W. van Straaten, Cornelis J. Stam, Ida A. Nissen, Sander Idema, Piet Van Mieghem, Arjan Hillebrand
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. ...
Journal article (2024) - Zhihao Qiu, Ivan Jokic, Siyu Tang, Rogier Noldus, Piet Van Mieghem
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. ...