PV
P.F.A. Van Mieghem
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
4 records found
1
Exact network reconstruction from observations of the SIS process in discrete time would be very useful if possible, with implications for tracking the spread of infectious diseases, trends and news on social media. It could provide estimates for the strength of links in a network and the contribution of individual nodes to the spread of an epidemic within a network as well as the underlying structure. This Thesis provides a method for evaluating heterogeneous parameters where each node has a randomly distributed curing probability and each link between two nodes has a randomly distributed infection probability. The parameters are computed via maximum likelihood estimation using between 102 and 104 observations of the SIS process on networks ranging in size from 15 to 55 nodes, for both directed Erdős-Rényi and Barabási-Albert graphs. We vary the network size to demonstrate that for a fixed level of accuracy, the number of required observations increases exponentially with the number of nodes for both the whole network and a subset of links and nodes. We further demonstrate that it may require fewer observations to reconstruct certain nodes based on the degree of the node or reconstruct links based on the degree of the node to which the link is incident. Additionally, if we interpret 106 or more observations as the number of required observations where reconstruction becomes infeasible, a network size of 500 would be infeasible for reconstructing the full network and the approximate limit for partial network reconstruction. The Thesis is extended to look at the SI and SIR models, achieving a similar exponential increase in the number of observations required as the network size increases, for a fixed error.
...
Exact network reconstruction from observations of the SIS process in discrete time would be very useful if possible, with implications for tracking the spread of infectious diseases, trends and news on social media. It could provide estimates for the strength of links in a network and the contribution of individual nodes to the spread of an epidemic within a network as well as the underlying structure. This Thesis provides a method for evaluating heterogeneous parameters where each node has a randomly distributed curing probability and each link between two nodes has a randomly distributed infection probability. The parameters are computed via maximum likelihood estimation using between 102 and 104 observations of the SIS process on networks ranging in size from 15 to 55 nodes, for both directed Erdős-Rényi and Barabási-Albert graphs. We vary the network size to demonstrate that for a fixed level of accuracy, the number of required observations increases exponentially with the number of nodes for both the whole network and a subset of links and nodes. We further demonstrate that it may require fewer observations to reconstruct certain nodes based on the degree of the node or reconstruct links based on the degree of the node to which the link is incident. Additionally, if we interpret 106 or more observations as the number of required observations where reconstruction becomes infeasible, a network size of 500 would be infeasible for reconstructing the full network and the approximate limit for partial network reconstruction. The Thesis is extended to look at the SI and SIR models, achieving a similar exponential increase in the number of observations required as the network size increases, for a fixed error.
Modelling the spread of contagious diseases among people has been a research topic for over a hundred years. However, the increase in computation power in the recent years allows for more advanced scientific models. The well-known susceptible-infected-susceptible model is used to describe the spreading of a disease among a group of people. This is modelled as a network, where persons are represented by nodes and their connections are links in the network. In this thesis, instead of a typical static network, the network itself changes structure based on the disease states of the nodes. In other words, there are two independent processes; the spreading of the disease over the network (state of the nodes) and the adaption of the network to the disease (state of the links). As a spreading model, the Markovian adaptive susceptible-infected-susceptible model (ASIS model for short) is introduced. It is shown that the model has one steady state, named the trivial steady state, in which all individuals are healthy. When the infection rate is sufficiently high, the system undergoes a phase transition from the disease-free state to an endemic state, where most nodes are infected. The state where most nodes are infected is named the metastable state. After being in the metastable state for a long time, the system collapses to the trivial steady state. The spreading of contagious processes is not just limited to disease spreading. Other relevant examples, such as opinion, gossip, fake news, neuron transmittance in the brain, etc. can be modelled using adaptive models as well. In this thesis, the ASIS model is extended by allowing different rules for the link-breaking and link-creation processes in what we call the Generalised ASIS framework. In total 36 models have been analysed simultaneously. Out of the 36 models, 9 showed a partially unstable metastable state. This resulted in rapid oscillations of the number of infected nodes just above the epidemic threshold. The relation between the epidemic threshold and the effective link-breaking rate was also determined. For 5 cases, the epidemic threshold is independent of the effective link-breaking rate. In 18 cases, the epidemic threshold scales linearly in the link-breaking rate. The remaining 13 cases are bounded between a constant and a linear link-breaking rate, however, its exact dependence remains unclear.
In the G-ASIS framework, it was conjectured that the metastable state of the Markov process can be accurately approximated by the steady state of the mean-field approximation. It was shown this is not true for every model. However in the ASIS model, the mean-field approximation showed close resemblance to the averaged stochastic results. This may be caused by a positive correlation between the nodes. For the other models, the deviation from the mean field approximation can probably be contributed to the fact that nodes are not positively correlated. Other higher order mean field approximations should be examined to approximate the averaged behaviour of the Markov process. ...
In the G-ASIS framework, it was conjectured that the metastable state of the Markov process can be accurately approximated by the steady state of the mean-field approximation. It was shown this is not true for every model. However in the ASIS model, the mean-field approximation showed close resemblance to the averaged stochastic results. This may be caused by a positive correlation between the nodes. For the other models, the deviation from the mean field approximation can probably be contributed to the fact that nodes are not positively correlated. Other higher order mean field approximations should be examined to approximate the averaged behaviour of the Markov process. ...
Modelling the spread of contagious diseases among people has been a research topic for over a hundred years. However, the increase in computation power in the recent years allows for more advanced scientific models. The well-known susceptible-infected-susceptible model is used to describe the spreading of a disease among a group of people. This is modelled as a network, where persons are represented by nodes and their connections are links in the network. In this thesis, instead of a typical static network, the network itself changes structure based on the disease states of the nodes. In other words, there are two independent processes; the spreading of the disease over the network (state of the nodes) and the adaption of the network to the disease (state of the links). As a spreading model, the Markovian adaptive susceptible-infected-susceptible model (ASIS model for short) is introduced. It is shown that the model has one steady state, named the trivial steady state, in which all individuals are healthy. When the infection rate is sufficiently high, the system undergoes a phase transition from the disease-free state to an endemic state, where most nodes are infected. The state where most nodes are infected is named the metastable state. After being in the metastable state for a long time, the system collapses to the trivial steady state. The spreading of contagious processes is not just limited to disease spreading. Other relevant examples, such as opinion, gossip, fake news, neuron transmittance in the brain, etc. can be modelled using adaptive models as well. In this thesis, the ASIS model is extended by allowing different rules for the link-breaking and link-creation processes in what we call the Generalised ASIS framework. In total 36 models have been analysed simultaneously. Out of the 36 models, 9 showed a partially unstable metastable state. This resulted in rapid oscillations of the number of infected nodes just above the epidemic threshold. The relation between the epidemic threshold and the effective link-breaking rate was also determined. For 5 cases, the epidemic threshold is independent of the effective link-breaking rate. In 18 cases, the epidemic threshold scales linearly in the link-breaking rate. The remaining 13 cases are bounded between a constant and a linear link-breaking rate, however, its exact dependence remains unclear.
In the G-ASIS framework, it was conjectured that the metastable state of the Markov process can be accurately approximated by the steady state of the mean-field approximation. It was shown this is not true for every model. However in the ASIS model, the mean-field approximation showed close resemblance to the averaged stochastic results. This may be caused by a positive correlation between the nodes. For the other models, the deviation from the mean field approximation can probably be contributed to the fact that nodes are not positively correlated. Other higher order mean field approximations should be examined to approximate the averaged behaviour of the Markov process.
In the G-ASIS framework, it was conjectured that the metastable state of the Markov process can be accurately approximated by the steady state of the mean-field approximation. It was shown this is not true for every model. However in the ASIS model, the mean-field approximation showed close resemblance to the averaged stochastic results. This may be caused by a positive correlation between the nodes. For the other models, the deviation from the mean field approximation can probably be contributed to the fact that nodes are not positively correlated. Other higher order mean field approximations should be examined to approximate the averaged behaviour of the Markov process.
Nowadays, reinforcement learning algorithms on Markov decision processes (MDPs) face computational issues when the state space is large. To reduce this state space of a MDP several state aggregation, or clustering, methodologies have been applied. Recently, a new clustering algorithm has been proposed that is able to cluster states from a single block Markov chain. A block Markov chain is a Markov chain with blocks in its transition matrix that correspond to clusters. Our aim was to investigate the possible combination of state aggregation in reinforcement learning on MDPs with clustering of states on a block Markov chain. First, we investigated the clustering algorithm and its properties to see its performance with different parameters and trajectory length. We compared the statistical properties of a pure Markov chain and the mixed Markov chain generated by a MDP. Afterwards, we verified the performance of the clustering algorithm on this mixed Markov chain. We proposed the BMC-MDP model that is able to model cluster based MDPs. We proposed C-PSRL, an algorithm, that consists of a single clustering step, on this newly introduced model. We compared its performance with a naïve approach and concluded that this new combined approach of clustering and MDP solving on a reduced space is a viable approach that reduces the computational complexity significantly. This research opened up the possibilities of more complex algorithms with, for example, multiple clustering steps. Moreover, if we can extend this clustering algorithm to clustering based on a state and action trajectory, this may results in an increased clustering performance and thereby enhance the performance of this general approach of optimizing on a cluster based MDP.
...
Nowadays, reinforcement learning algorithms on Markov decision processes (MDPs) face computational issues when the state space is large. To reduce this state space of a MDP several state aggregation, or clustering, methodologies have been applied. Recently, a new clustering algorithm has been proposed that is able to cluster states from a single block Markov chain. A block Markov chain is a Markov chain with blocks in its transition matrix that correspond to clusters. Our aim was to investigate the possible combination of state aggregation in reinforcement learning on MDPs with clustering of states on a block Markov chain. First, we investigated the clustering algorithm and its properties to see its performance with different parameters and trajectory length. We compared the statistical properties of a pure Markov chain and the mixed Markov chain generated by a MDP. Afterwards, we verified the performance of the clustering algorithm on this mixed Markov chain. We proposed the BMC-MDP model that is able to model cluster based MDPs. We proposed C-PSRL, an algorithm, that consists of a single clustering step, on this newly introduced model. We compared its performance with a naïve approach and concluded that this new combined approach of clustering and MDP solving on a reduced space is a viable approach that reduces the computational complexity significantly. This research opened up the possibilities of more complex algorithms with, for example, multiple clustering steps. Moreover, if we can extend this clustering algorithm to clustering based on a state and action trajectory, this may results in an increased clustering performance and thereby enhance the performance of this general approach of optimizing on a cluster based MDP.
Web Real-Time communication (WebRTC) is a technology that enables web browsers to establish real-time communication services without the need of specific software or plug-ins. This technology is gaining popularity and is already supported by popular browsers such as Google Chrome, Firefox and Safari. The quality of real-time communication services depends highly on latency. For this reason, real-time flows have different requirements than conventional TCP flows which focus mainly on the transfer of bulk traffic. The IETF created the working group RMCAT (RTP Media Congestion Avoidance Techniques) to define requirements for real-time congestion control algorithms. One of the proposed algorithms is Google Congestion Control (GCC). This is the only real-time congestion control algorithm implemented in commercial browsers such as Google Chrome. Unfortunately, the performance of GCC in wireless networks has not been extensively evaluated. It is not clear yet what limitations a WebRTC communication might encounter in this type of networks, especially when it is competing with other type of flows. This project addressed this issue by evaluating GCC in different technologies, namely in wired, WiFi and 4G networks. Controlled testbeds were used for the evaluation. The experiments followed the evaluation guidelines for real-time congestion control algorithms defined by the IETF. GCC proved to be a compliant RMCAT congestion control algorithm in networks with no contention. However, the results obtained in wireless access technologies revealed that GCC collapses when TCP flows are present in the channel. This issue is not attributed to GCC itself but to channel access methods of this type of networks. It is necessary to implement procedures to assign a different QoS to WebRTC flows in order to overcome this problem.
...
Web Real-Time communication (WebRTC) is a technology that enables web browsers to establish real-time communication services without the need of specific software or plug-ins. This technology is gaining popularity and is already supported by popular browsers such as Google Chrome, Firefox and Safari. The quality of real-time communication services depends highly on latency. For this reason, real-time flows have different requirements than conventional TCP flows which focus mainly on the transfer of bulk traffic. The IETF created the working group RMCAT (RTP Media Congestion Avoidance Techniques) to define requirements for real-time congestion control algorithms. One of the proposed algorithms is Google Congestion Control (GCC). This is the only real-time congestion control algorithm implemented in commercial browsers such as Google Chrome. Unfortunately, the performance of GCC in wireless networks has not been extensively evaluated. It is not clear yet what limitations a WebRTC communication might encounter in this type of networks, especially when it is competing with other type of flows. This project addressed this issue by evaluating GCC in different technologies, namely in wired, WiFi and 4G networks. Controlled testbeds were used for the evaluation. The experiments followed the evaluation guidelines for real-time congestion control algorithms defined by the IETF. GCC proved to be a compliant RMCAT congestion control algorithm in networks with no contention. However, the results obtained in wireless access technologies revealed that GCC collapses when TCP flows are present in the channel. This issue is not attributed to GCC itself but to channel access methods of this type of networks. It is necessary to implement procedures to assign a different QoS to WebRTC flows in order to overcome this problem.