Search

International audience; Les réseaux complexes, appelés aussi "graphes de terrain", apparaissent dans divers contextes tels que l'informatique (e.g. réseaux de pages Web), la sociologie (e.g. réseaux collaboratifs) ou la biologie (e.g. réseaux de régulation de gènes). Une propriété importante et commune à tous ces graphes est qu'ils sont généralement constitués de sous-graphes fortement interconnectés appelés "communautés". La détection de communautés (qui peut être vue comme un problème de partitionnement de graphes) est une problématique très largement étudiée ces dernières années et, dans ce sens, beaucoup d'algorithmes ont été proposés. Bon nombre d'entre eux cherchent à maximiser la fonction de qualité de Newman-Girvan, appelée aussi "modularité" (il s'agit d'un problème NP-difficile). C'est le cas notamment de l'algorithme de Louvain, qui est actuellement le meilleur algorithme en terme de complexité pour calculer des communautés sur de très grands graphes (il est capable de traiter en moins de 3h des graphes ayant plus d'un milliard de sommets et d'arêtes). La modularité présente toutefois plusieurs inconvénients. En la maximisant, on peut trouver des partitions de bonne qualité dans des graphes qui n'ont pas de communautés (des graphes réguliers, des graphes aléatoires, des arbres...). Elle privilégie également des communautés de grande taille. Nous avons ainsi adapté la méthode de Louvain à d'autres critères de qualité (comme le critère de Zahn-Condorcet par exemple). nous obtenons globalement les mêmes performances en terme de temps de calcul que l'algorithme de Louvain classique.De plus, nous avons exhibé une condition suffisante pour savoir si un critère pouvait être intégré à la méthode de Louvain.

We are interested to an optimization problem on graphs (the Vertex Cover) in a very specific context: the huge instances of data. We defined a treatment model based on constraints linked to the limited amount of memory, model for which properties comes from several existing models in the litterature (online, streaming...). We studied several algorithms suitable to this model: we analyzed, first theoretically, the quality of their solutions and their complexities (in worst and average case). We then conducted an experimental study on very large graphs., Nous nous sommes intéressés à un problème d'optimisation sur des graphes (le Vertex Cover) dans un contexte de traitement bien particulier : celui des grandes instances de données. Nous avons défini pour cela un modèle de traitement basé sur des contraintes liées principalement à la quantité de mémoire limitée, modèle qui reprenait des propriétés issues de plusieurs modèles existants dans la littérature (online, streaming...). Nous avons étudié plusieurs algorithmes adaptés à ce modèle : nous avons analysé, tout d'abord de façon théorique, la qualité de leurs solutions ainsi que leurs complexités (en pire cas et en moyenne). Nous avons ensuite mené une étude expérimentale sur de très gros graphes.

We are interested to an optimization problem on graphs (the Vertex Cover) in a very specific context: the huge instances of data. We defined a treatment model based on constraints linked to the limited amount of memory, model for which properties comes from several existing models in the litterature (online, streaming...). We studied several algorithms suitable to this model: we analyzed, first theoretically, the quality of their solutions and their complexities (in worst and average case). We then conducted an experimental study on very large graphs.; Nous nous sommes intéressés à un problème d'optimisation sur des graphes (le Vertex Cover) dans un contexte de traitement bien particulier : celui des grandes instances de données. Nous avons défini pour cela un modèle de traitement basé sur des contraintes liées principalement à la quantité de mémoire limitée, modèle qui reprenait des propriétés issues de plusieurs modèles existants dans la littérature (online, streaming...). Nous avons étudié plusieurs algorithmes adaptés à ce modèle : nous avons analysé, tout d'abord de façon théorique, la qualité de leurs solutions ainsi que leurs complexités (en pire cas et en moyenne). Nous avons ensuite mené une étude expérimentale sur de très gros graphes.

International audience; In this paper, we consider the classical NP-complete VERTEX COVER problem in large graphs. We assume that the size and the access to the input graph impose the following constraints: (1) the input graph must not be modified (integrity of the input instance), (2) the computer running the algorithm has a memory of limited size (compared to the graph) and (3) the result must be sent to an output memory once a new piece of solution is calculated. Despite the severe constraints of the model, we propose three algorithms that satisfy them. We derive exact formulas giving the expected size of the solution they return. This allows us to compare them, in an analytic way. Then, we consider their complexities. We give exact formulas expressing the expected number of requests they perform on the input graph. Again, we compare them analytically. For both comparisons, we show that none of them is better than the two others.The formulas we give can help users to estimate the best balance between quality of the solution and performance.