Nous sommes entourés par une multitude de réseaux d'interactions, issus de contextes très différents. Ces réseaux peuvent être modélisés par des graphes, appelés graphes de terrain. Ils possèdent une structure en communautés, c'est-à-dire en groupes de nœuds très liés entre eux, et peu liés avec les autres. Un phénomène que l'on étudie sur les graphes dans de nombreux contextes est la diffusion. La propagation d'une maladie en est un exemple. Ces phénomènes dépendent d'un paramètre important, mais souvent peu étudié : l'échelle de temps selon laquelle on les observe. Selon l'échelle choisie, la dynamique du graphe peut varier de manière très importante.Dans cette thèse, nous proposons d'étudier des processus dynamiques en utilisant une échelle de temps adaptée. Nous considérons une notion de temps relatif, que nous appelons le temps intrinsèque, par opposition au temps "classique", que nous appelons temps extrinsèque. Nous étudions en premier lieu des phénomènes de diffusion selon une échelle de temps intrinsèque, et nous comparons les résultats obtenus avec une échelle extrinsèque. Ceci nous permet de mettre en évidence le fait qu'un même phénomène observé dans deux échelles de temps différentes puisse présenter un comportement très différent. Nous analysons ensuite la pertinence de l'utilisation du temps intrinsèque pour la détection de communautés dynamiques. Les communautés obtenues selon les échelles de temps extrinsèques et intrinsèques nous montrent qu'une échelle intrinsèque permet la détection de communautés beaucoup plus significatives et détaillées que l'échelle extrinsèque. / We are surrounded by a multitude of interaction networks from different contexts. These networks can be modeled as graphs, called complex networks. They have a community structure, i.e. groups of nodes closely related to each other and less connected with the rest of the graph. An other phenomenon studied in complex networks in many contexts is diffusion. The spread of a disease is an example of diffusion. These phenomena are dynamic and depend on an important parameter, which is often little studied: the time scale in which they are observed. According to the chosen scale, the graph dynamics can vary significantly. In this thesis, we propose to study dynamic processes using a suitable time scale. We consider a notion of relative time which we call intrinsic time, opposed to "traditional" time, which we call extrinsic time. We first study diffusion phenomena using intrinsic time, and we compare our results with an extrinsic time scale. This allows us to highlight the fact that the same phenomenon observed at two different time scales can have a very different behavior. We then analyze the relevance of the use of intrinsic time scale for detecting dynamic communities. Comparing communities obtained according extrinsic and intrinsic scales shows that the intrinsic time scale allows a more significant detection than extrinsic time scale.

La détection de communautés dans les réseaux est aujourd'hui un domaine ayant donné lieu à une abondante littérature. Depuis les travaux de Girvan et Newman en 2002, des centaines de travaux ont été menés sur le sujet, notamment la proposition d'un nombre important d'algorithmes de plus en plus élaborés. Cependant, la majorité de ces travaux portent sur des communautés statiques dans des réseaux statiques. Or, beaucoup de réseaux de terrains sont en fait dynamiques, ils évoluent au cours du temps. L'apport principal de cette thèse est donc la conception d'un algorithme de détection de communautés dynamiques sur des réseaux temporels. Le manuscrit est découpé en quatre sections : La première est un état de l'art, où sont passés en revu les méthodes existantes pour la détection de communauté, statiques, dynamiques, avec et sans recouvrement. La seconde est la présentation de la solution que nous proposons : iLCD, un framework pour la détection de communautés dynamiques dans les réseaux temporels, ainsi que deux implémentations de ce framework. La troisième partie présente les travaux effectués pour valider iLCD sur le plan statique, c'est à dire valider que les communautés trouvées sont pertinentes comparées à d'autres algorithmes existant sur des réseaux statiques. Pour ce faire, nous proposons des idées originales, afin de pouvoir comparer des méthodes sur des graphes réels. Enfin, la dernière partie est consacrée à la validation de l'aspect dynamique d'iLCD. En effet, la dynamique introduit des données supplémentaires : l'apparition et la disparition de communautés, leur évolution en continue, ainsi que des opérations complexes, telles que la fusion ou la division de communautés au cours du temps. Ce sont ces aspects qui sont validés ici, en étudiant en détail les résultats obtenus sur des réseaux réels.