My thesis deals with community detection in the context of social networks. A social network can be modelized by a graph in which vertices represent members and edges represents relationships. In particular, I study three different definitions for a community. First, a community structure can be defined as a partition of the vertices such that each vertex has a greater proportion of neighbors in its part than in any other part. Secondly, a community can be viewed as a subgraph such that every two vertices are at distance 2 in this subgraph. Finally, in the context of online meeting services, I investigate a definition for potential communities in which members do not know each other but are related by their common neighbors. For those three definitions, I study computational complexity and approximation among problems that relate to the existence of such communities or the community finding in graphs.
Key-words: Combinatorial optimization, Complexity, Approximation, Algorithms, Graphs.
My CV is available here.
The slides of my PhD Defense presentation are available here.
My PhD is available here.
75775 Paris, France