De la détection de la structure communautaire des réseaux complexes

Auteur(s): Young, Jean-Gabriel
Direction de recherche: Dubé, Louis J.
Résumé: Une description précise de la structure mésoscopique des réseaux complexes permet de modéliser efficacement les processus de propagation sur réseaux ainsi que la croissance de ces derniers. Cette structure s’exprime en termes d’une décomposition en communautés (ou groupes denses de noeuds structurellement rapprochés), de sorte que l’identification d’une organisation optimale constitue un problème de décision de classe NP-difficile. Plusieurs algorithmes récents permettent d’obtenir des solutions approchées dans un temps polynomial. Toutefois, la nature ad hoc de ces algorithmes rend difficile l’évaluation de leurs qualités et de leurs faiblesses. Cet ouvrage fait état d’un formalisme analytique unifiant la théorie de la détection communautaire via une description matricielle. Dans un premier temps, on démontre qu’une grande classe d’algorithmes de détection est équivalente à un problème d’optimisation dont la solution approximative peut être obtenue par la décomposition spectrale de matrices de coût, fonction de la structure du réseau à l’étude. Ces développements établissent un cadre théorique permettant l’étude rigoureuse d’algorithmes ad hoc, et mènent également à un algorithme de détection original, basé sur des principes fondamentaux d’optimisation continue. Dans un deuxième temps, il est démontré par le biais de la théorie des matrices aléatoires que, pour une classe particulière de réseaux, la structure communautaire (ici a priori connue) laisse une empreinte aisément identifiable dans le spectre des matrices de coût associées. Ces deux points de vue complémentaires, optimisation spectrale et théorie des matrices aléatoires, donnent accès à de nouvelles observations importantes qu’une simple étude numérique ne peut expliquer, tel l’apparition d’une limite de détection intrinsèque. Ces développements analytiques restent toutefois confinés à des modèles de réseaux simples. Pour des problèmes plus complexes, une approche numérique est préconisée. On introduit donc une méthode heuristique de détection permettant d’améliorer les performances de tout algorithme imparfait. Dans la perspective de calibrer cette méthode, on présente également un processus de croissance local polyvalent qui produit des réseaux réalistes possédant une structure communautaire connue.
Type de document: Mémoire de maîtrise
Date de publication: 2014
Date de la mise en libre accès: 20 avril 2018
Lien permanent: http://hdl.handle.net/20.500.11794/25472
Université décernant le diplôme: Université Laval
Collection :Thèses et mémoires

Fichier(s) :
TailleFormat 
31203.pdf5.8 MBAdobe PDFTélécharger
Tous les documents dans CorpusUL sont protégés par la Loi sur le droit d'auteur du Canada.