Avec la multiplication des source d’informations sur Internet, les blogs, les sites des journaux en ligne ou les site de nouvelles, recevoir la plupart des informations importantes sans avoir besoin de trop multiplier le nombre de sources peut s’avérer plus que complexe.
Des chercheurs de l’université Carnegie Mellon (Pittsburgh, Pennsylvania, USA), ont utilisés des techniques appliquées pour des réseaux de distribution de l’eau, notamment lors de la Bataille de Capteurs pour les Réseaux de distribution d’Eau en 2006 (BWSN). En effet, savoir où placer au mieux les détecteurs de défaillances dans un réseau de distribution pose des problèmes similaires à savoir quelles sources d’information suivre pour ne pas rater de nouvelles importantes. Cette initiative, sponsorisée par Intel, Microsoft, HP, NTT et IBM, a conduit à plusieurs papiers de recherche, dont le plus important est « Cost-effective Outbreak Detection in Networks », et un site, Open Cascades , qui montre comment choisir 100 blogs ou 5000 blogs pour minimiser les manquements d’informations importantes tout en minimisant le coût de lecture.
Dans des réseaux dynamiques, optimiser les fonctions de recherches en fonction de certains critères tels que la minimisation de temps de détection des défaillance ou la minimisation de la population de nœuds non surveillés est un problème NP-complet, donc il n’est pas possible de trouver la solution optimale pour des réseaux importants. Cependant, en démontrant que la plupart des fonctions de détection des brèches sont sous-modulaires, leur algorithme, CELF, arrive à une solution presqu’optimale (une fraction de 1/2*(1-1/e)) dans tous les cas.
Par exemple, pour maximiser l’information vue sur les sites de nouvelles sur Internet et les blogs, une solution naïve consiste à prendre les plus gros sites, qui ont plus de chance de colporter l’information mais elle coûte cher en temps de lecture. Par contre, une collection de plus petits sites, de meilleure qualité et correctement choisis, de par les propriétés de sous-modularité, apportera plus d’information pour un moindre temps.
Ainsi leur algorithme se révèle être plusieurs centaines de fois plus rapide et moins coûteux qu’un simple algorithme glouton, tout en atteignant près de 90% de la solution optimale. Cet algorithme est probablement applicable à de nombreux autres domaines où les graphes et les réseaux jouent un rôle important.