ZQ
Z. Qiu
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>
3 records found
1
Analysis and Design of Networks
Shortest Paths and Effective Resistance
The function of a network is generally related to the transport of items over the underlying graph. For example, in transportation networks, vehicles, trains, ships and aircraft deliver passengers and cargo to their destinations, while in telecommunication networks, IP packets are transmitted to enable data change between devices or users. To enhance the performance of item transmission in networks, such as reducing latency in telecommunication networks, we need to deepen the understanding of how a network supports efficient transport between two nodes and how transmission paths can be determined. Another important research topic concerns the design or construction of networks to meet users’ evolving demands, either by developing new networks from scratch or by modifying existing ones. In this dissertation, the analysis and design of networks for item transmission are considered in three distinct areas.
We first explore the item transmission in networks where the item travels along a single path, usually the shortest path in most practical scenarios. In Chapter 2, we focus on the geometric properties of shortest paths in soft random geometric graphs (SRGGs) in 2-dimensional Euclidean space. We demonstrate that shortest paths are aligned along geodesic curves connecting shortest path endpoints. To quantify the strength of the alignment, we introduce two metrics: the average distance to the geodesic from shortest path nodes and the average path stretch. Both metrics decrease in larger SRGGs with short-range connections. Additionally, we find that the alignment strength is nonmonotonic with respect to the average degree of the SRGG and identify network properties maximizing shortest path alignment. Based on these observations, we establish that the alignment of shortest paths may be sufficiently strong to allow the identification of shortest path nodes based on their proximity to geodesic curves. Extensive simulations confirm that our geometric-based approach predicts shortest path nodes even when node positions in the latent space are not precisely known.
The second part of this dissertation investigates inverse problems of the shortest paths. Given predetermined demands on the shortest path weight, such as upper bounds on delay between nodes in telecommunication networks, we focus on how to dimension the network, both topology and link weights, so that transport along the shortest path between any pair of nodes satisfies the given demands. Chapter 3 introduces the inverse all shortest path problem (IASPP), which asks for a weighted adjacency matrix of a graph such that all the elements in the corresponding shortest path weight matrix do not exceed those of the given demand matrix. We propose the Descending Order Recovery (DOR) algorithm, which exactly solves the IASPP. The network provided by DOR minimized the number of links and the sum of link weights across all networks with the same shortest path weight matrix. As a complement to DOR, a second algorithm, Omega based Link Removal (OLR), leverages effective resistance to solve the IASPP. Chapter 4 further extends IASPP to the modification of existing networks under changing transmission requirements. Inspired by practical scenarios, we study two extensions of IASPP. The first develops a new graph whose shortest path weight matrix equals a predetermined demand matrix while minimizing the total change in link weights from the original graph and an exact approach is proposed. The second variant considers a more constrained scenario in which the graph topology remains unchanged. We propose an algorithm, “distance basis sum” (DBS), for tree topologies commonly found in domains such as telecommunications and industrial networks. Compared with classical approaches, DBS can improve computational efficiency while constructing a graph close to the optimal solution.
In the third part of the dissertation, we investigate item transmission in networks where items propagate along multiple paths between two nodes. In Chapter 5, we study the expected number of nodes and links involved in transferring items between the source and destination in random graphs. Then, we investigate the power dissipation associated with transportation at link level. Further, we address how to construct a network given a predetermined end-to-end power dissipation, which reduces to the “inverse effective resistance problem” of finding a network whose effective resistance matrix matches a given demand. We propose a heuristic algorithm, “Resistor Gap Pruning” (RGP), which provides sparse networks closely approximating the demand effective resistance and performs consistently across different demand scenarios. ...
We first explore the item transmission in networks where the item travels along a single path, usually the shortest path in most practical scenarios. In Chapter 2, we focus on the geometric properties of shortest paths in soft random geometric graphs (SRGGs) in 2-dimensional Euclidean space. We demonstrate that shortest paths are aligned along geodesic curves connecting shortest path endpoints. To quantify the strength of the alignment, we introduce two metrics: the average distance to the geodesic from shortest path nodes and the average path stretch. Both metrics decrease in larger SRGGs with short-range connections. Additionally, we find that the alignment strength is nonmonotonic with respect to the average degree of the SRGG and identify network properties maximizing shortest path alignment. Based on these observations, we establish that the alignment of shortest paths may be sufficiently strong to allow the identification of shortest path nodes based on their proximity to geodesic curves. Extensive simulations confirm that our geometric-based approach predicts shortest path nodes even when node positions in the latent space are not precisely known.
The second part of this dissertation investigates inverse problems of the shortest paths. Given predetermined demands on the shortest path weight, such as upper bounds on delay between nodes in telecommunication networks, we focus on how to dimension the network, both topology and link weights, so that transport along the shortest path between any pair of nodes satisfies the given demands. Chapter 3 introduces the inverse all shortest path problem (IASPP), which asks for a weighted adjacency matrix of a graph such that all the elements in the corresponding shortest path weight matrix do not exceed those of the given demand matrix. We propose the Descending Order Recovery (DOR) algorithm, which exactly solves the IASPP. The network provided by DOR minimized the number of links and the sum of link weights across all networks with the same shortest path weight matrix. As a complement to DOR, a second algorithm, Omega based Link Removal (OLR), leverages effective resistance to solve the IASPP. Chapter 4 further extends IASPP to the modification of existing networks under changing transmission requirements. Inspired by practical scenarios, we study two extensions of IASPP. The first develops a new graph whose shortest path weight matrix equals a predetermined demand matrix while minimizing the total change in link weights from the original graph and an exact approach is proposed. The second variant considers a more constrained scenario in which the graph topology remains unchanged. We propose an algorithm, “distance basis sum” (DBS), for tree topologies commonly found in domains such as telecommunications and industrial networks. Compared with classical approaches, DBS can improve computational efficiency while constructing a graph close to the optimal solution.
In the third part of the dissertation, we investigate item transmission in networks where items propagate along multiple paths between two nodes. In Chapter 5, we study the expected number of nodes and links involved in transferring items between the source and destination in random graphs. Then, we investigate the power dissipation associated with transportation at link level. Further, we address how to construct a network given a predetermined end-to-end power dissipation, which reduces to the “inverse effective resistance problem” of finding a network whose effective resistance matrix matches a given demand. We propose a heuristic algorithm, “Resistor Gap Pruning” (RGP), which provides sparse networks closely approximating the demand effective resistance and performs consistently across different demand scenarios. ...
The function of a network is generally related to the transport of items over the underlying graph. For example, in transportation networks, vehicles, trains, ships and aircraft deliver passengers and cargo to their destinations, while in telecommunication networks, IP packets are transmitted to enable data change between devices or users. To enhance the performance of item transmission in networks, such as reducing latency in telecommunication networks, we need to deepen the understanding of how a network supports efficient transport between two nodes and how transmission paths can be determined. Another important research topic concerns the design or construction of networks to meet users’ evolving demands, either by developing new networks from scratch or by modifying existing ones. In this dissertation, the analysis and design of networks for item transmission are considered in three distinct areas.
We first explore the item transmission in networks where the item travels along a single path, usually the shortest path in most practical scenarios. In Chapter 2, we focus on the geometric properties of shortest paths in soft random geometric graphs (SRGGs) in 2-dimensional Euclidean space. We demonstrate that shortest paths are aligned along geodesic curves connecting shortest path endpoints. To quantify the strength of the alignment, we introduce two metrics: the average distance to the geodesic from shortest path nodes and the average path stretch. Both metrics decrease in larger SRGGs with short-range connections. Additionally, we find that the alignment strength is nonmonotonic with respect to the average degree of the SRGG and identify network properties maximizing shortest path alignment. Based on these observations, we establish that the alignment of shortest paths may be sufficiently strong to allow the identification of shortest path nodes based on their proximity to geodesic curves. Extensive simulations confirm that our geometric-based approach predicts shortest path nodes even when node positions in the latent space are not precisely known.
The second part of this dissertation investigates inverse problems of the shortest paths. Given predetermined demands on the shortest path weight, such as upper bounds on delay between nodes in telecommunication networks, we focus on how to dimension the network, both topology and link weights, so that transport along the shortest path between any pair of nodes satisfies the given demands. Chapter 3 introduces the inverse all shortest path problem (IASPP), which asks for a weighted adjacency matrix of a graph such that all the elements in the corresponding shortest path weight matrix do not exceed those of the given demand matrix. We propose the Descending Order Recovery (DOR) algorithm, which exactly solves the IASPP. The network provided by DOR minimized the number of links and the sum of link weights across all networks with the same shortest path weight matrix. As a complement to DOR, a second algorithm, Omega based Link Removal (OLR), leverages effective resistance to solve the IASPP. Chapter 4 further extends IASPP to the modification of existing networks under changing transmission requirements. Inspired by practical scenarios, we study two extensions of IASPP. The first develops a new graph whose shortest path weight matrix equals a predetermined demand matrix while minimizing the total change in link weights from the original graph and an exact approach is proposed. The second variant considers a more constrained scenario in which the graph topology remains unchanged. We propose an algorithm, “distance basis sum” (DBS), for tree topologies commonly found in domains such as telecommunications and industrial networks. Compared with classical approaches, DBS can improve computational efficiency while constructing a graph close to the optimal solution.
In the third part of the dissertation, we investigate item transmission in networks where items propagate along multiple paths between two nodes. In Chapter 5, we study the expected number of nodes and links involved in transferring items between the source and destination in random graphs. Then, we investigate the power dissipation associated with transportation at link level. Further, we address how to construct a network given a predetermined end-to-end power dissipation, which reduces to the “inverse effective resistance problem” of finding a network whose effective resistance matrix matches a given demand. We propose a heuristic algorithm, “Resistor Gap Pruning” (RGP), which provides sparse networks closely approximating the demand effective resistance and performs consistently across different demand scenarios.
We first explore the item transmission in networks where the item travels along a single path, usually the shortest path in most practical scenarios. In Chapter 2, we focus on the geometric properties of shortest paths in soft random geometric graphs (SRGGs) in 2-dimensional Euclidean space. We demonstrate that shortest paths are aligned along geodesic curves connecting shortest path endpoints. To quantify the strength of the alignment, we introduce two metrics: the average distance to the geodesic from shortest path nodes and the average path stretch. Both metrics decrease in larger SRGGs with short-range connections. Additionally, we find that the alignment strength is nonmonotonic with respect to the average degree of the SRGG and identify network properties maximizing shortest path alignment. Based on these observations, we establish that the alignment of shortest paths may be sufficiently strong to allow the identification of shortest path nodes based on their proximity to geodesic curves. Extensive simulations confirm that our geometric-based approach predicts shortest path nodes even when node positions in the latent space are not precisely known.
The second part of this dissertation investigates inverse problems of the shortest paths. Given predetermined demands on the shortest path weight, such as upper bounds on delay between nodes in telecommunication networks, we focus on how to dimension the network, both topology and link weights, so that transport along the shortest path between any pair of nodes satisfies the given demands. Chapter 3 introduces the inverse all shortest path problem (IASPP), which asks for a weighted adjacency matrix of a graph such that all the elements in the corresponding shortest path weight matrix do not exceed those of the given demand matrix. We propose the Descending Order Recovery (DOR) algorithm, which exactly solves the IASPP. The network provided by DOR minimized the number of links and the sum of link weights across all networks with the same shortest path weight matrix. As a complement to DOR, a second algorithm, Omega based Link Removal (OLR), leverages effective resistance to solve the IASPP. Chapter 4 further extends IASPP to the modification of existing networks under changing transmission requirements. Inspired by practical scenarios, we study two extensions of IASPP. The first develops a new graph whose shortest path weight matrix equals a predetermined demand matrix while minimizing the total change in link weights from the original graph and an exact approach is proposed. The second variant considers a more constrained scenario in which the graph topology remains unchanged. We propose an algorithm, “distance basis sum” (DBS), for tree topologies commonly found in domains such as telecommunications and industrial networks. Compared with classical approaches, DBS can improve computational efficiency while constructing a graph close to the optimal solution.
In the third part of the dissertation, we investigate item transmission in networks where items propagate along multiple paths between two nodes. In Chapter 5, we study the expected number of nodes and links involved in transferring items between the source and destination in random graphs. Then, we investigate the power dissipation associated with transportation at link level. Further, we address how to construct a network given a predetermined end-to-end power dissipation, which reduces to the “inverse effective resistance problem” of finding a network whose effective resistance matrix matches a given demand. We propose a heuristic algorithm, “Resistor Gap Pruning” (RGP), which provides sparse networks closely approximating the demand effective resistance and performs consistently across different demand scenarios.
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.
...
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.
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.
...
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.