IC Colloquium: Optimisation, control and mitigation of spreading processes
By: David Saad - Aston University
Video of his talk
Abstract
The modern world comprises interlinked networks of contacts between individuals, computing devices and social groups, where infectious diseases, information and opinions propagate through their edges in a probabilistic or deterministic manner via interactions between individual constituents. The spread of information, opinions and marketing material can be modelled and analysed in a similar manner to that of epidemic spreading among humans or animals.
To contain and mitigate the spread of infectious diseases one would like to model the spread accurately, implement effective prevention and mitigation policies and deploy vaccines in a way that minimises the spread. This is a difficult problem and becomes even harder in the presence of infectious but asymptomatic individual states. In the world of marketing and opinion setting, winners are those who maximise the impact by deploying resource to the most influential available nodes at the right time, occasionally in competition (or collaboration) with adversarial (supportive) spreading processes. These can represent opinion formation by political parties (competitive) or diseases that increase the susceptibility to mutual infections (collaborative). Additionally, spreading processes on different networks may be interlinked, providing additional challenge in their mitigation and an incentive to share resources.
I will explain the modelling of epidemic spreading processes and present the probabilistic analytical framework for impact maximisation/minimisation we have developed, addressing the questions of vaccine (budget) deployment and spreading maximisation in single and competitive/collaborative processes. I will also present the analysis of epidemic spreading processes with infectious but asymptomatic states and of interlinked spreading processes on different networks, and the effectiveness of containment and mitigation in both cases.
Message passing for routing and network design in optical communication
Optical communication networks underpin the global digital communications infrastructure and carry most of the Internet traffic. They comprise thousands of kilometres of optical fibres, organised in a complex web of constituent sub-networks. The exponential growth in Internet traffic and energy consumption threatens to overload the existing infrastructure.
One of the key requirements is the routing and wavelength assignment (RWA) for all traffic demands across this complex heterogeneous network in a way that optimises a given objective function, be it low latency, high throughput or resilience. The main constraint in RWA is that any complete individual route, from source to destination, uses the same single wavelength and that separate routes using the same wavelength cannot share the same fibre. This constraint makes the general hard computational routing problem even harder.
Given that routes are constrained to be contiguous and interaction between paths is non-localised, local optimisation methods are insufficient and global optimisation is required. However, global RWA of multiple communication requests is computationally-hard and is currently addressed in small systems by integer/linear programming and its variants, Monte Carlo search, greedy algorithms and various heuristics. The main challenge we address is the RWA under heavy traffic using multiple wavelengths and a large number of origin-destination pairs for various objective functions. This is carried out by mapping the RWA task in the presence of multiple wavelengths onto multi-layer replica of the original graph and utilising probabilistic message-passing techniques, developed independently in several fields including statistical physics, to solve it. These methods allow for messages, in the form of conditional probability values to be passed between nodes and the replicated networks representing the different wavelengths, in a way that keeps the algorithms scalable even for a large number of wavelengths, transmission requests (corresponding to source-destination pairs) and nodes. The algorithm has been tested for a variety of sparse network topologies, both synthetic random graphs and real optical communication networks, and for different objective functions, showing excellent results in obtaining high quality approximate solutions.
Another major task in designing and maintaining optical communication networks is the removal of unnecessary edges or adding new ones in a manner that minimises the impact on throughput in the former and maximises the benefit in the latter. Many edges in operational optical communication networks are legacy fibres that are costly to maintain but are not removed due to the possible operational impact; similarly, adding fibres is expensive and one clearly would like to maximise the benefit from it. Many of the methods used currently for these tasks are topological in nature without considering the typical communication requests, while others rely on simulations or heuristics. We consider the two-level optimisation tasks, of edge removal/addition in parallel to optimal multi-user routing in order the identify the best edges to be removed/added with minimal/maximal impact on a given objective (e.g., throughput, latency or resilience). The methodology used is based on message passing and the resulting algorithms have been tested on synthetic and real networks, showing excellent results compared to existing heuristics.
Routing, network design, message-passing, optimisation
Bio
David Saad received a B.A. degree in physics and a B.Sc. in electrical engineering from Technion, Israel, and an M.Sc. degree in physics and a Ph.D. in electrical engineering from Tel-Aviv University. He holds the 50th Anniversary Chair of Complexity Physics at Aston University, Birmingham, U.K. He was with Edinburgh University in 1992 and has worked in Aston since 1995. His research, published in over 200 papers, focuses on the application of statistical physics methods to various fields, including artificial neural networks, error-correcting codes, multinode communication, network optimization, routing in road and optical communication networks, noisy computation, epidemic spreading, understanding human neuronal networks and advanced inference methods.
More information
Video of his talk
Abstract
The modern world comprises interlinked networks of contacts between individuals, computing devices and social groups, where infectious diseases, information and opinions propagate through their edges in a probabilistic or deterministic manner via interactions between individual constituents. The spread of information, opinions and marketing material can be modelled and analysed in a similar manner to that of epidemic spreading among humans or animals.
To contain and mitigate the spread of infectious diseases one would like to model the spread accurately, implement effective prevention and mitigation policies and deploy vaccines in a way that minimises the spread. This is a difficult problem and becomes even harder in the presence of infectious but asymptomatic individual states. In the world of marketing and opinion setting, winners are those who maximise the impact by deploying resource to the most influential available nodes at the right time, occasionally in competition (or collaboration) with adversarial (supportive) spreading processes. These can represent opinion formation by political parties (competitive) or diseases that increase the susceptibility to mutual infections (collaborative). Additionally, spreading processes on different networks may be interlinked, providing additional challenge in their mitigation and an incentive to share resources.
I will explain the modelling of epidemic spreading processes and present the probabilistic analytical framework for impact maximisation/minimisation we have developed, addressing the questions of vaccine (budget) deployment and spreading maximisation in single and competitive/collaborative processes. I will also present the analysis of epidemic spreading processes with infectious but asymptomatic states and of interlinked spreading processes on different networks, and the effectiveness of containment and mitigation in both cases.
Message passing for routing and network design in optical communication
Optical communication networks underpin the global digital communications infrastructure and carry most of the Internet traffic. They comprise thousands of kilometres of optical fibres, organised in a complex web of constituent sub-networks. The exponential growth in Internet traffic and energy consumption threatens to overload the existing infrastructure.
One of the key requirements is the routing and wavelength assignment (RWA) for all traffic demands across this complex heterogeneous network in a way that optimises a given objective function, be it low latency, high throughput or resilience. The main constraint in RWA is that any complete individual route, from source to destination, uses the same single wavelength and that separate routes using the same wavelength cannot share the same fibre. This constraint makes the general hard computational routing problem even harder.
Given that routes are constrained to be contiguous and interaction between paths is non-localised, local optimisation methods are insufficient and global optimisation is required. However, global RWA of multiple communication requests is computationally-hard and is currently addressed in small systems by integer/linear programming and its variants, Monte Carlo search, greedy algorithms and various heuristics. The main challenge we address is the RWA under heavy traffic using multiple wavelengths and a large number of origin-destination pairs for various objective functions. This is carried out by mapping the RWA task in the presence of multiple wavelengths onto multi-layer replica of the original graph and utilising probabilistic message-passing techniques, developed independently in several fields including statistical physics, to solve it. These methods allow for messages, in the form of conditional probability values to be passed between nodes and the replicated networks representing the different wavelengths, in a way that keeps the algorithms scalable even for a large number of wavelengths, transmission requests (corresponding to source-destination pairs) and nodes. The algorithm has been tested for a variety of sparse network topologies, both synthetic random graphs and real optical communication networks, and for different objective functions, showing excellent results in obtaining high quality approximate solutions.
Another major task in designing and maintaining optical communication networks is the removal of unnecessary edges or adding new ones in a manner that minimises the impact on throughput in the former and maximises the benefit in the latter. Many edges in operational optical communication networks are legacy fibres that are costly to maintain but are not removed due to the possible operational impact; similarly, adding fibres is expensive and one clearly would like to maximise the benefit from it. Many of the methods used currently for these tasks are topological in nature without considering the typical communication requests, while others rely on simulations or heuristics. We consider the two-level optimisation tasks, of edge removal/addition in parallel to optimal multi-user routing in order the identify the best edges to be removed/added with minimal/maximal impact on a given objective (e.g., throughput, latency or resilience). The methodology used is based on message passing and the resulting algorithms have been tested on synthetic and real networks, showing excellent results compared to existing heuristics.
Routing, network design, message-passing, optimisation
Bio
David Saad received a B.A. degree in physics and a B.Sc. in electrical engineering from Technion, Israel, and an M.Sc. degree in physics and a Ph.D. in electrical engineering from Tel-Aviv University. He holds the 50th Anniversary Chair of Complexity Physics at Aston University, Birmingham, U.K. He was with Edinburgh University in 1992 and has worked in Aston since 1995. His research, published in over 200 papers, focuses on the application of statistical physics methods to various fields, including artificial neural networks, error-correcting codes, multinode communication, network optimization, routing in road and optical communication networks, noisy computation, epidemic spreading, understanding human neuronal networks and advanced inference methods.
More information
Practical information
- General public
- Free
Contact
- Host: Lenka Zdeborova