Sous-graphes denses: algorithmes et analyse de complexité de certains problèmes de recherche et de couverture
Antoine Castillon · HAL (Le Centre pour la Communication Scientifique Directe) · 2024
With the rapid rise of the Internet and the development of social networks, massive graphs containing billions of vertices and edges have appeared. The dense subparts, also called clusters, existing in these graphs are essential to many applications. For instance, they can be used for recommendations, fraud detection or compression. The search for clusters in a graph is a well known issue in computer science and the most classic formalizations such as the clique are of paramount importance in complexity theory.In this thesis we studied different formalizations of the cluster concept that are more suited to the applications cases previously mentioned. In addition to the different formalizations, we divided our study between two main objectives: the search for maximal clusters, or at least large clusters in a graph and the coverage of a graph with clusters. We mainly focused on exact approaches by favoring parameterized approaches.Concerning the objective of finding large clusters, we first studied relaxations of clique such as s-clubs, s-cliques and degree-based quasi-cliques. Due to their non-hereditary nature (on induced subgraphs), these relaxations are very difficult to study and many complexity questions are still open. Therefore, we proposed new techniques, well adapted to non-hereditary formalizations, that allowed us to classify the parameterized complexity of the search problems associated with these relaxations. We consider classical graph parameters such as k, the size of the searched subgraph, l=n-k, the size of its complement, the maximum degree of the graph, its h-index or its degeneracy.Then, we studied the concept of proportionally dense subgraphs (PDS), where each vertex in the subgraph has proportionally more neighbors inside the subgraph than outside. Derived from the concept of community structure introduced by Olsen in 2013, it differs from previously mentioned relaxations by considering both the links inside and outside the subgraph. By re-using some techniques used for clique relaxations, we manage to obtain the parameterized complexity classification of the PDS problem for almost all graph parameters presented in The Graph Parameter Hierarchy by Manuel Sorge.Regarding the second objective, we have proposed a new variant of the Cluster Editing problem where the goal is to transform a graph into a disjoint union of quasi-cliques with a minimum number of edge modifications. We have studied different types of modifications: additions, deletions or editions as well as two types of quasi-cliques: degree and density quasi-cliques. We have also been interested in the problems of partitioning a graph into quasi-cliques. For each problem introduced, we provided its classical complexity and studied the parameterization by k, the maximum number of authorized modifications.We then focused on an application of quasi-clique partitioning to graph compression. Inspired by the method presented in Dense Subgraph Summarization, we proposed several improvements allowing a rapid decrease in computation time while maintaining the compression ratio and the representativeness of the summary obtained.We also proposed an extension of dense subgraph search to temporal graphs. We introduced the Activated Graph model where vertices can be active and inactive in order to better reflect the reality of some networks. In this context, we were interested in the search for induced subgraphs verifying certain properties. The problem associated with a property π is called π-AGP. First, we proved that, as for static graphs, π-AGP is NP-hard for any hereditary, non-trivial and polynomial-time (HNTP) π property. Second, we proposed different parameterized approaches by also proposing algorithms valid for HNTP π properties as well as more precise results in the case where π is the independence property.To conclude, during this thesis we studied the search for dense subgraphs in a graph. We favored parameterized complexity approaches to provide exact solutions to our problems while maintaining a certain efficiency of the algorithms.