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

Authors: Young, Jean-Gabriel
Advisor: Dubé, Louis J.
Abstract: 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.
Document Type: Mémoire de maîtrise
Issue Date: 2014
Open Access Date: 20 April 2018
Permalink: http://hdl.handle.net/20.500.11794/25472
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
SizeFormat 
31203.pdf5.8 MBAdobe PDFView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.