• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Community detection : computational complexity and approximation

Détection de communautés : complexité computationnelle et approximation

Pontoizeau, Thomas (2018), Community detection : computational complexity and approximation, doctoral thesis prepared under the supervision of Bazgan, Cristina, Université Paris Dauphine

View/Open
2018PSLED007.pdf (2.522Mb)
Type
Thèse
Date
2018-06-04
Metadata
Show full item record
Author(s)
Pontoizeau, Thomas
Under the direction of
Bazgan, Cristina
Abstract (FR)
Cette thèse étudie la détection de communautés dans le contexte 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 représentent les relations entre les membres. En particulier, j'étudie quatre différentes définitions de communauté. D'abord, une structure en communautés peut être définie par une partition des sommets telle que tout sommet a une plus grande proportion de voisins dans sa partie que dans toute autre partie. Cette définition peut être adaptée pour l'étude d'une seule communauté. Ensuite, une communauté peut être vue comme un sous graphe tel que tout couple de sommets sont à distance 2 dans ce sous graphe. Enfin, dans le contexte des sites de rencontre, je propose d'étudier une définition de communauté potentielle dans le sens où les membres de la communauté ne se connaissent pas, mais sont liés par des connaissances communes. Pour ces trois définitions, j'étudie la complexité computationnelle et l'approximation de problèmes liés à l'existence ou la recherche de telles communautés dans les graphes.
Abstract (EN)
This thesis deals with community detection in the context of social networks. A social network can be modeled by a graph in which vertices represent members, and edges represent relationships. In particular, I study four different definitions of 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. This definition can be adapted in order to study only one community. Then, a community can be viewed as a subgraph in which every two vertices are at distance 2 in this subgraph. Finally, in the context of online meetup services, I investigate a definition for potential communities in which members do not know each other but are related by their common neighbors. In regard to these proposed definitions, I study computational complexity and approximation within problems that either relate to the existence of such communities or to finding them in graphs.
Subjects / Keywords
Complexité; Algorithme; Graphes; Approximation; Complexity; Algorithm; Graphs; Approximation

Related items

Showing items related by title and author.

  • Thumbnail
    Proportionally dense subgraph of maximum size: Complexity and approximation 
    Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément; Pontoizeau, Thomas (2019) Article accepté pour publication ou publié
  • Thumbnail
    On the complexity of finding a potential community 
    Bazgan, Cristina; Pontoizeau, Thomas; Zsolt, Tuza (2017) Communication / Conférence
  • Thumbnail
    Structural and algorithmic properties of 2-community structures 
    Bazgan, Cristina; Chlebíková, Janka; Pontoizeau, Thomas (2018) Article accepté pour publication ou publié
  • Thumbnail
    Détection de communautés dans les grands réseaux : Application aux réseaux d'interactions de gènes 
    Ben M'Barek, Marwa (2022-10-14) Thèse
  • Thumbnail
    Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée 
    Bonnet, Édouard (2014-11) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo