Avec la multiplication des sources d’informations sur Internet tels que les blogs (sites des journaux en ligne ou les sites 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é 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 publications, dont la plus importante est "Cost-effective Outbreak Detection in Networks", et un site, https://opencascades.org , qui montre comment choisir 100 blogs ou 5000 blogs pour maximiser les informations importantes recues 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 noeuds non surveillés est un problème NP-complet. Il n’est donc 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 presque 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 transmettre l’information mais cette solution 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.
Source :
– https://www.blogcascades.org/
– "Cost-effective Outbreak Detection in Networks" – Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, Natalie Glance – https://www.cs.cmu.edu/~jure/pubs/detect-kdd07.pdf
Pour en savoir plus, contacts :
– Explication en vidéo : https://videolectures.net/solomon_leskovec_ceod/
– Propagation dans les réseaux : https://www.cs.cmu.edu/~jure/pubs
– Placement des capteurs dans les réseaux: https://www.cs.cmu.edu/~krausea/research.html
Code brève
ADIT : 52042
Rédacteur :
Jean-Baptiste Kempf – [email protected]
