Projects

How to prevent viruses from going viral?

Computer scientists discovered a similarity: the way viruses spread is similar to that of news in social media. The researchers now want to refine their calculation models of how posts go viral and apply them to the spread of SARS-CoV-2. Source: Felipe Esquivel Reed, CC BY-SA 4.0, via Wikimedia Commons

In his previous work, Markus Sinnl was actually concerned with social media such as Twitter. In recent years, he has developed methods to understand how certain posts go viral. When the coronavirus pandemic erupted, he realised that the spread of information in social media showed great similarities with the spread of the coronavirus in the population. In a project funded by the Austrian Science Fund FWF, he now wants to employ his tools in the fight against the coronavirus.

Search for exact solutions

To this end, principal investigator Sinnl plans to expand the methods developed for social media. In his model, the virus is equated to an agent in a network who wants to achieve maximum propagation. “We would model this in exactly the same way as the spread of a message in a social network, but we want to add an extra layer consisting of measures taken from outside the network to prevent spread,” Sinnl explains.

Sinnl uses a method going by the name of integer programming, which involves the solutions of equations that do not contain numbers with fractional components, but only whole numbers. The method is well suited to handling many practical problems in industry or, for instance, public transport timetables, a fact that is corroborated by Sinnl conducting his research at the Institute of Production and Logistics Management at the Johannes Kepler University Linz. The advantage of integer programming: the equations provide more than just probabilities. “Our methods deliver what can be proved to be the optimal solution to the problem,” Sinnl notes emphatically.

Methods from advertising

“In the last few years I applied integer programming to solve influence maximisation, among other things,” he says. “The question was: how can you influence people in social networks?” Whereas such problems do have a tradition in computer science according to Sinnl, most people try to solve them “heuristically”, that is, by finding approximate solutions.

When describing the spread dynamics of the coronavirus, exact solutions would be a novelty; there, too, heuristic methods and approximate solutions have been used up to now. Although models are used to test the effectiveness of certain measures to prevent the spread of the virus, Sinnl explains that it is almost impossible to determine whether they are actually the optimal solution. Sinnl adopts another approach by looking at the situation as an optimisation problem. He maps various measures for reducing spread in his methods and then searches directly for the optimal combination.

The diagram illustrates one step towards the solution of the “competitive influence maximization problem”, which involves two agents, leader (L) and follower (F), who compete for influence in the network. Diagram (a) outlines the given input. Each of the shown connections between two nodes in the network is assigned a probability of influence by the input. Based on these probabilities, various so-called live-arc graphs are created, as shown in (b) and (c), which can be used to easily calculate the influence of L and F for selected initial nodes. In the example, both L and F can choose one initial node. The nodes influenced by the leader at the end of the influence process are highlighted in light blue, those influenced by the follower in dark blue. Source: Michael Kahr et al., CC BY-SA 4.0

High computational effort

Sinnl emphasises that his approach requires a lot of computing power, and his equipment does not allow him to simulate more than 30,000 network nodes – one node corresponding to one person. But right now, practical use in response to the pandemic is not the primary goal, as he says. “This is about basic research. We are trying to show that it is feasible,” Sinnl notes. The project, which was approved by the FWF at the end of 2020, will start in December and is scheduled to run for two years.

Multilevel problem

When a problem involves several levels, it becomes significantly more complex and turns into a so-called “hierarchical” problem. “As a matter of principle, these are very difficult optimisation problems,” Sinnl explains. “The research on this stems from the last 10 to 15 years. Before that, there was simply not enough computing power.” For his calculations, Sinnl plans to use parallel computers, which are supercomputers that often have many hundreds of individual processors working on a problem in parallel. Sinnl will be supported by his research colleague Kübra Taninmiş, with whom he has already collaborated in his research on hierarchical problems, and who is employed using project funds.

Finding new solutions

“Simulations can obviously handle much larger datasets, and by using our exact methods we will only be able to look at smaller and more abstractly modelled problems,” Sinnl says. “But there has been very little work in the direction we are heading towards. So we may be able to find new solutions to controlling the pandemic that can serve as alternative approaches to previous heuristic models.”


Personal details

Markus Sinnl is a computer scientist at the Institute of Production and Logistics Management at the Johannes Kepler University Linz. He is interested in integer programming, social media optimisation and hierarchical optimisation problems. The project “Preventing epidemics in networks using integer programming”, will run from 2021 to 2023 and is funded by the Austrian Science Fund FWF with EUR 154,000.


Publications

Kübra Tanınmış, Necati Aras, İ. Kuban Altınel: Improved x-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks, in: European Journal of Operational Research, Vol. 297, Issue 1, 2022

Evren Güney, Markus Leitner, Mario Ruthmair, Markus Sinnl: Large-scale influence maximization via maximal covering location, in: European Journal of Operational Research, Vol. 289, Issue 1, 2021

Michael Kahr, Markus Leitner, Mario Ruthmair, Markus Sinnl: Benders decomposition for competitive influence maximization in (social) networks, in: Omega, Vol. 100, 2021

Comments (0)

Currently no comments for this article.

Write a comment

Your email address will not be published.