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. / A precise description of the mesoscopic structure of complex systems is necessary to improve models of the dynamical processes on and of networks. However, knowledge of this structure comes at great cost, since finding a optimal decomposition in communities is a problem that belongs to the NP hard complexity class. Multiple recent algorithms yield approximate solutions in polynomial time. Most of these algorithms are collections of ad hoc methods, such that only extensive numerical studies lead to insightful comparisons. In this thesis, we present the basis of a unified theory of community detection, which builds upon recent advances of the spectral theory of complex networks. First, we prove that a large class of detection algorithm is equivalent to an optimization problem that can be solved approximately though the spectral decomposition of a very general cost matrix. Within this framework, otherwise ad hoc algorithms can be studied analytically and rigorously. This point of view also leads to a new, original and first-principled spectral detection algorithm. Second, using random matrix theory, we generalize existing results and prove that the spectrum of a class of modular networks contains valuable information on their mesoscopic structure. These complementary approaches, spectral optimization and random matrix theory, give powerful insights into the spectral theory of complex networks, and their relevance to community structure. These analytical results are unfortunately not yet generalizable to arbitrary networks. For complex cases, we prefer a purely numerical approach. Hence, we introduce a heuristic method that drastically improves the efficiency of existing, imperfect algorithms. To test this method, we also present a local growth process that produces realistic modular networks with known community structure. These networks can then be used as versatile benchmarks.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/25472 |
| Date | 20 April 2018 |
| Creators | Young, Jean-Gabriel |
| Contributors | Dubé, Louis J. |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | English |
| Type | mémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise |
| Format | 1 ressource en ligne (xxiii, 136 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0025 seconds