|
 
|
[LCd16a] Un partitionnement d’arêtes à base de blocs pour les algorithmes de marche aléatoire dans les grands graphes sociaux.
Conférence Nationale avec comité de lecture : Bases de Données Avancées (BDA), October 2016, pp.-, Poitiers, France,
motcle:
Résumé:
Le partitionnement de graphe est d'un intérêt primordial dans le domaine de la recherche du traitement distribué de graphe. Il joue un rôle de plus en plus important à la fois dans les calculs centrés sur les sommets, comme
dans le modèle de Pregel, et dans l'évaluation de requêtes. Les résultats récents montrent que le
partitionnement des arêtes (vertex-cut) s'avère être plus
efficace
que le partitionnement des sommets (edge-cut) traditionnellement utilisé pour
les calculs sur des graphes réels comme les graphes des réseaux sociaux. Par
conséquence, plusieurs systèmes de calcul de graphe
basés sur cette approche ont été proposés, tels que PowerGraph
(GraphLab2) et GraphX. Toutefois, leurs
stratégies de partitionnement de graphe sont génériques et ne dépendent pas des
algorithmes utilisés pour les différents calculs.
Nous proposons dans cet article une nouvelle stratégie de partitionnement de graphe (de ses arêtes) basée sur des blocs, qui fournit une distribution équilibrée des arêtes et réduit les coûts de communication
pour les calculs utilisant des marches aléatoires.
A notre connaissance, il s'agit de la première fois qu'une stratégie de partitionnement dédiée à des algorithmes de marches aléatoires est proposée dans le modèle de Pregel. Enfin, les expériences montrent
que notre partitionnement a apporté des améliorations significatives concernant les coûts
de communication et les temps d'exécution des différents algorithmes s'appuyant sur des marches aléatoires.
Collaboration:
LIP6
BibTeX
| @inproceedings { | |||
| LCd16a, | |||
| title | = | "{Un partitionnement d’arêtes à base de blocs pour les algorithmes de marche aléatoire dans les grands graphes sociaux.}", | |
| author | = | " Y. Li and C. Constantin and C. du Mouza ", | |
| booktitle | = | "{Bases de Données Avancées (BDA)}", | |
| year | = | 2016, | |
| edition | = | "32", | |
| month | = | "October", | |
| pages | = | "-", | |
| address | = | "Poitiers, France", | |
| } | |||
