|
 
|
[LCd17a] Un partitionnement d'arêtes à base de blocs pour les algorithmes de marches aléatoires dans les grands graphes sociaux.
Revue Nationale avec comité de lecture : Journal Ingénierie des Systèmes d'Information (ISI), vol. 22(3), pp. 89-113, 2017Mots clés: partitionnement de graphes, passage à l'échelle, marches aléatoires
Résumé:
Des résultats récents (Bourse et al., 2014; Gonzalez et al., 2012; Xin et al., 2013)
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. Compte tenu de la distribution de type
« power-law » de la plupart des graphes, le partitionnement des arêtes (vertex-cut) permet
d’éviter des calculs asymétriques. Par conséquent, plusieurs systèmes de calcul de graphe
basés sur cette approche ont été proposés, tels que PowerGraph (GraphLab2) (Gonzalez et al.,
2012) et GraphX (Xin et al., 2013). Leurs stratégies de partitionnement sont génériques et ne
dépendent pas des algorithmes utilisés pour effectuer les différents calculs. Nous proposons
dans cet article une nouvelle stratégie de partitionnement de graphe (de ses arêtes) optimisant
l’exécution des algorithmes basés sur les marches aléatoires qui prennent en compte les
propriétés topologiques des graphes. Notre stratégie est basée sur la construction de blocs
qui modélisent des communautés locales. Notre approche de partitionnement en blocs fournit
une distribution équilibrée des arêtes sur les noeuds de calcul et permet de la maintenir
dynamiquement. Les coûts de communication pour les calculs utilisant des marches aléatoires
sont réduits de manière significative par rapport aux approches existantes.
Collaboration:
LIP6
BibTeX
| @article { | |||
| LCd17a, | |||
| title | = | "{Un partitionnement d'arêtes à base de blocs pour les algorithmes de marches aléatoires dans les grands graphes sociaux.}", | |
| author | = | "Y. Li and C. Constantin and C. du Mouza", | |
| journal | = | "Ingénierie des Systèmes d'Information (ISI)", | |
| year | = | 2017, | |
| volume | = | 22, | |
| number | = | 3, | |
| pages | = | "89-113", | |
| } | |||
