Approximation dynamique de clusters dans un graphe social : méthodes et applications
Dynamic approximation of clusters in a social network : methods and applications
Algorithmes de streaming
Graphes dynamiques
Clustering
Approximation
Streaming algorithms
Dynamic graphs
Clustering
Approximation
Graphes dynamiques
Algorithmes
Approximation, Théorie de l'
Grilles informatiques
Analyse des données
Nous étudions comment détecter des clusters dans un graphe défini par un flux d’arêtes, sans stocker l'ensemble du graphe. Nous montrons comment détecter de gros clusters de l'ordre de ?n dans des graphes qui ont m = O(n log(n)) arêtes, tout en stockant ?n.log(n) arêtes. Les graphes sociaux suivent le régime où m satisfait cette condition. Nous étendons notre approche aux graphes dynamiques définis par les arêtes les plus récentes du flux et à plusieurs flux. Nous proposons des méthodes simples et robustes afin de détecter ces clusters de manière approchée.Nous définissons la corrélation de contenu de deux flux ?(t) par la similarité de Jaccard de leurs clusters, dans les fenêtres au temps t. Nous proposons une méthode simple et efficace pour approcher cette corrélation en ligne et montrons que pour les graphes aléatoires dynamiques qui suivent une loi de puissance, nous pouvons garantir une bonne approximation.Une des applications est l’analyse des flux Twitter. Nous calculons les corrélations de contenu de ces flux en ligne. Nous proposons ensuite une recherche par corrélation où les réponses aux ensembles de mots-clés sont entièrement basées sur les petites corrélations des flux. Les réponses sont ordonnées par les corrélations, et les explications peuvent être tracées avec les clusters stockés.
We study how to detect clusters in a graph defined by a stream of edges, without storing the entire graph. We show how to detect large clusters in the order of ?n in graphs that have m = O(n log(n)) edges, while storing ?n.log(n) edges. Social graphs satisfy this condition m. We extend our approach to dynamic graphs defined by the most recent stream of edges and multiple streams. We propose simple and robust methods based on the approximation to detect these clusters.We define the content correlation of two streams ?(t) is the Jaccard similarity of their clusters in the windows before time t. We propose a simple and efficient method to approach this online correlation and show that for dynamic random graphs that follow a power law, we can guarantee a good approximation.As an applications we follow Twitter streams and compute their content correlations online. We then propose a search by correlation where answers to sets of keywords are entirely based on the small correlations of the streams. Answers are ordered by the correlations, and explanations can be traced with the stored clusters.
Electronic Thesis or Dissertation
Text
fr
PDF
7286735
https://docassas.u-paris2.fr/nuxeo/site/esupversions/0b8fac0c-9239-4fc4-8046-430a74690e70
Vimont
Guillaume
1993-10-01
FR
249496437
http://www.theses.fr/2019PA020007
2019PA020007
2019-10-24
Informatique
Paris 2
026403145
Doctorat
Docteur es
non
oui
Rougemont
Michel de
MADS_DIRECTEUR_DE_THESE_1
032468423
Chevalier
Céline
MADS_MEMBRE_DU_JURY_1
091517427
Spyratos
Nicolas
MADS_MEMBRE_DU_JURY_2
070368260
Prieur
Christophe
MADS_RAPPORTEUR_1
060559497
Salamatian
Kavé
MADS_RAPPORTEUR_2
154190500
École doctorale des sciences économiques et gestion, sciences de l'information et de la communication (Paris)
MADS_ECOLE_DOCTORALE_1
157546896
Université Panthéon-Assas (Paris). Centre de recherches en économie du droit
MADS_PARTENAIRE_DE_RECHERCHE_1
228932114
Laboratoire d'informatique algorithmique, fondements et applications (Paris)
MADS_PARTENAIRE_DE_RECHERCHE_2
113845677
ddc:004
Rougemont
Michel de
Chevalier
Céline
Spyratos
Nicolas
Prieur
Christophe
Salamatian
Kavé
École doctorale des sciences économiques et gestion, sciences de l'information et de la communication (Paris)
Université Panthéon-Assas (Paris). Centre de recherches en économie du droit
Laboratoire d'informatique algorithmique, fondements et applications (Paris)
PDF
7286735