Alogorithm for fast and accurate detection of sources developed as part of Renoir project

The study, featuring researchers from Warsaw, Wroclaw and the Rensselaer Polytechnic Institute from New York State, has been published in the scientific journal Scientific Reports, which is published by Nature Publishing Group.

Locating spread sources is often important in an increasingly interconnected world, for example to find patient one in an epidemic, or the source of a rumour spreading in a social network. In many circumstances, locating the source may save lives or property.

Finding efficient methods of source detection is therefore crucial, and the researchers say that the fundamental component of such a system is a fast algorithm.

The researchers from Warsaw based their work on a study done in 2012 that resulted in the Pinto-Thiran-Vetterli algorithm (PTVA), but they sped up this algorithm using a variety of approaches.

The new algorithm, which they have dubbed GMLA, makes it possible to rapidly process large networks made of tens of thousands of nodes, which the old algorithm was not able to do.

According to lead researcher Robert Paluch, the crucial components of both algorithms are nodes in the analysed network which act as observers; they tell the researchers when a piece of information reached them.

Whereas PTVA examines each of the observers, GMLA focuses only on high-quality observers, which are likeliest to be closest to the source. This is why the algorithm is faster.

The algorithm only calculates the likelihood of a node being the source, the final verification still needs to be made by humans.

The researchers tested the algorithm on multiple networks in a controlled environment and it mostly performed better than PTVA. In also performed better when tested on real-life example, the file-sharing network Gnutella.

Paluch said the algorithm performs better in particular in networks that closely mimic real-life networks, for example social media, where people have a thousand connections or more.

Nevertheless, he said accuracy was still an issue and the next step was to improve the algorithm so that it will be more likely to find sources in networks with many nodes.

Renoir project

The purpose of Renoir project is to analyse the dynamics of information spreading in a collaboration between social sciences experts, journalists and scientists specialised in big data and complex systems.

The principal aim is to determine how information spreads in media and online to then produce a model that can explain the spreading and, in the final phase, even predict it.

The project consortium features the Warsaw University of Technology as coordinator, and the STA, the Jožef Stefan Institute from Ljubljana and the Wroclaw University of Technology as partners.

The consortium members have additionally partnered with the Nanyang University of Technology from Singapore, and the Rensselaer Polytechnic Institute, Stanford University, University of California Santa Cruz, University of California Davis, Carnegie Mellon University, Northeastern University and Notre Dame University from the US.

The project is co-financed by the European Union in the framework of the Marie Sklodowska Curie actions of the research and innovation programme Horizon 2020. The action is focused on the development of human resources in science, the development of research and innovation work, and improvement of professional competences of researchers.