Search

In this thesis we study the algorithmic complexity of optimization problems related to the study of social networks. A social network can be modeled by a graph in which the vertices represent the members and the edges their relations. We are interested in two different problems, graph anonymization and community detection.The anonymization of graphs has already been studied and many formalizations of the concept have been proposed in the form of properties. To satisfy them, it is often necessary to transform the initial graph. We will then be careful to provide algorithms that minimize its alteration during the anonymization process. In this thesis we measure the alteration by the number of elementary transformations performed on the graph. We propose to study the minimization of the number of edge rotations required on a graph in order for it to respect a given anonymization property in different cases. Empirical work has already been published and we have tried to pursue it on the complexity and approximation angle. The use of this new operator has allowed for more encouraging negative as well as positive theoretical results than with the previous ones.A community is a social group sharing a common space, goods or interests. This is reflected on the graph by strong connections between its individuals. There are many ways to characterize communities and we focus on definitions based on the optimization of a density function. More precisely, we study a problem of partitioning into dense subgraphs where we try to maximize a global density function. We continue the first works undertaken on this subject and propose more thorough results.For these two problems we have studied different classes including classes of sparse graphs, relatively similar to social networks., Dans cette thèse nous étudions la complexité algorithmique de problèmes d’optimisation liés à l’étude des réseaux sociaux. Un réseau social peut être modélisé par un graphe dans lequel les sommets représentent les membres et les arêtes, leurs relations. Nous nous intéressons à deux problématiques différentes, l’anonymisation de graphes et la détection de communautés. L’anonymisation de graphes a déjà été étudiée et de nombreuses formalisations du concept ont été proposées sous forme de propriétés. Pour les satisfaire, il faut souvent transformer le graphe initial. On sera alors attentif à fournir des algorithmes qui minimisent son altération lors du processus d’anonymisation. Dans cette thèse nous mesurons l’altération subie par le nombre de transformations élémentaires effectuées sur le graphe. Nous proposons d’étudier la minimisation du nombre de rotations d’arêtes nécessaires sur un graphe afin que celui-ci respecte une propriété d’anonymisation donnée dans différents cas de figure. Des travaux empiriques ont déjà été publiés et nous nous sommes attachés à les poursuivre sous l’angle de la complexité et de l’approximation. L’utilisation de ce nouvel opérateur a permis des résultats théoriques négatifs ainsi que positifs, l’ensemble étant plus encourageant que les résultats sur les précédents opérateurs. Une communauté est un groupe social partageant un espace, des biens ou des intérêts communs. Cela se reflète sur le graphe par des fortes connexions entre ses individus. Il existe de nombreuses manières de caractériser les communautés et nous nous sommes concentrés sur les définitions basées sur l’optimisation d’une fonction de densité. Plus précisément nous étudions un problème de partition en sous-graphes denses où l’on cherche à maximiser une fonction de densité globale. Nous poursuivons les premiers travaux entrepris sur ce sujet et proposons des résultats plus approfondis.