Dans le contexte des réseaux complexes, cette thèse s’inscrit dans deux axes : (1) Méthodologiede la détection de communautés et (2) Evaluation de la qualité des algorithmes de détection de communautés. Dans le premier axe, nous nous intéressons en particulier aux approches fondées sur les Leaders (sommets autour desquels s’agrègent les communautés). Premièrement, nous proposons un enrichissement de la méthodologie LICOD qui permet d’évaluer les différentes stratégies des algorithmes fondés sur les leaders, en intégrant différentes mesures dans toutes les étapes de l’algorithme. Deuxièmement, nous proposons une extension de LICOD, appelée it-LICOD. Cette extension introduit une étape d’auto-validation de l’ensemble des leaders. Les résultats expérimentaux de it-LICOD sur les réseaux réels et artificiels sont bons par rapport à LICOD et compétitifs par rapport aux autres méthodes. Troisièmement, nous proposons une mesure de centralité semi-locale, appelée TopoCent, pour remédier au problème de la non-pertinence des mesures locales et de la complexité de calcul élevée des mesures globales. Nous montrons expérimentalement que LICOD est souvent plus performant avec TopoCent qu’avec les autres mesures de centralité. Dans le deuxième axe, nous proposons deux méthodes orientées-tâche, CLE et PLE, afin d’évaluer les algorithmes de détection de communautés. Nous supposons que la qualité de la solution des algorithmes peut être estimée en les confrontant à d’autres tâches que la détection de communautés en elle-même. Dans la méthode CLE nous utilisons comme tâche la classification non-supervisée et les algorithmes sont évalués sur des graphes générés à partir des jeux de données numériques. On bénéficie dans ce cas de la disponibilité de la vérité de terrain (les regroupements) de plusieurs jeux de données numériques. En ce qui concerne la méthode PLE, la qualité des algorithmes est mesurée par rapport à leurs contributions dans une tâche de prévision de liens. L’expérimentation des méthodes CLE et PLE donne de nouveaux éclairages sur les performances des algorithmes de détection de communautés / In this thesis we focus, on one hand, on community detection in complex networks, and on the other hand, on the evaluation of community detection algorithms. In the first axis, we are particularly interested in Leaders driven community detection algorithms. First, we propose an enrichment of LICOD : a framework for building different leaders-driven algorithms. We instantiate different implementations of the provided hotspots. Second, we propose an extension of LICOD, we call it-LICOD. This extension introduces a self-validation step of all identified leaders. Experimental results of it-LICOD on real and artificial networks show that it outperform the initial LICOD approach. Obtained results are also competitive with those of other state-of-the art methods. Thirdly, we propose a semi-local centrality measure, called TopoCent, that address the problem of the irrelevance of local measures and high computational complexity of globalmeasures. We experimentally show that LICOD is often more efficient with TopoCent than with the other classical centrality measures. In the second axis, we propose two task-based community evaluation methods : CLE and PLE. We examine he hypothesis that the quality of community detection algorithms can be estimated by comparing obtained results in the context of other relevent tasks. The CLE approach, we use a data clustering task as a reference. The PLE method apply a link prediction task. We show that the experimentation of CLE and PLE methods gives new insights into the performance of community detection algorithms.

Botnets are a global problem, and effective botnet detection requires cooperation of large Internet Service Providers, allowing near global visibility of traffic that can be exploited to detect them. The global visibility comes with huge challenges, especially in the amount of data that has to be analysed. To handle such large volumes of data, a robust and effective detection method is the need of the hour and it must rely primarily on a reduced or abstracted form of data such as a graph of hosts, with the presence of an edge between two hosts if there is any data communication between them. Such an abstraction would be easy to construct and store, as very little of the packet needs to be looked at. Structured P2P command and control have been shown to be robust against targeted and random node failures, thus are ideal mechanisms for botmasters to organize and command their botnets effectively. Thus this thesis develops a scalable, efficient and robust algorithm for the detection of structured P2P botnets in large traffic graphs. It draws from the advances in the state of the art in Community Detection, which aim to partition a graph into dense communities. Popular Community Detection Algorithms with low theoretical time complexities such as Label Propagation, Infomap and Louvain Method have been implemented and compared on large LFR benchmark graphs to study their efficiency. Louvain method is found to be capable of handling graphs of millions of vertices and billions of edges. This thesis analyses the performance of this method with two objective functions, Modularity and Stability and found that neither of them are robust and general. In order to overcome the limitations of these objective functions, a third objective function proposed in the literature is considered. This objective function has previously been used in the case of Protein Interaction Networks successfully, and used in this thesis to detect structured P2P botnets for the first time. Further, the differences in the topological properties - assortativity and density, of structured P2P botnet communities and benign communities are discussed. In order to exploit these differences, a novel measure based on mean regular degree is proposed, which captures both the assortativity and the density of a graph and its properties are studied. This thesis proposes a robust and efficient algorithm that combines the use of greedy community detection and community filtering using the proposed measure mean regular degree. The proposed algorithm is tested extensively on a large number of datasets and found to be comparable in performance in most cases to an existing botnet detection algorithm called BotGrep and found to be significantly faster.