December the 3rd, 2018, 2PM, salle des thèses at Faculté Jean Perrin.

Abstract :

This thesis focuses on the field of complex networks analysis. A complex network can be defined as a system of interacting entities often represented by a graph. Two problems related to the study of large networks are addressed in this thesis. Our first goal is to extract relevant knowledge in graphs by identifying community structures. The second problem related to big graphs summarization. The first problem is known as community detection. Indeed, the existence of more dense connected subparts than others is one of the main characteristics of complex graphs. These subparts are called communities. These communities may be overlapping or disjoint and may have several meanings depending on the type of the input graph. The second problem studied is about graph compression : it consists on discovering hidden graph structures and exploiting them to compactly summarize large graphs.

In the first contribution, we introduce a new community concept called k-linked community, allowing us to characterize node/edge centered k-linked community with bounded diameter. Such community admits a node or an edge with a distance at most k/2 from any other node of that community. First, we show how the problem of detecting node/edge centered k-linked overlapping communities can be expressed as a Partial Max-SAT optimization problem. Then, we provide a second method to refine our SAT-based model by incorporating preferences in order to select more efficiently the centroid for each community in the input graph. In the second contribution, we propose two seed-expanding models for overlapping community detection in large complex networks. The first model consists of a relaxation of the clique structure. This relaxation gives rise to a new notion of community named k-clique-star. The second model aims to extend maximal cliques in order to identify overlapping communities in networks. In the last contribution, we propose a novel approach to summaize big data graphs. First, we show that some special graph classes can be represented effeciently as Pseudo Boolean constraints (PB). Then, we propose new several graph classes expressed as PB constraints. Finally, we present a novel PB constraints based algorithm to summarize big graphs. All the proposed methods are efficient and very competitive w.r.t. state-of-the-art approaches in the literature.