ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Autres revues >>

Ingénierie des Systèmes d'Information

Networking and Information Systems
1633-1311
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 22/3 - 2017  - pp.89-113  - doi:10.3166/isi.22.3.89-113
TITRE
Un partitionnement d’arêtes à base de blocs pour les algorithmes de marches aléatoires dans les grands graphes sociaux

TITLE
A block-based edge-partitionning for random walks algorithms in large social graphs

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.


ABSTRACT
Recent results (Bourse et al., 2014; Gonzalez et al., 2012; Xin et al., 2013) prove that edge partitioning approaches (also known as vertex-cut) outperform vertex partitioning (edge-cut) approaches for computations on large and skewed graphs like social networks. These vertex-cut approaches generally avoid unbalanced computation due to the power-law degree distribution of the graphs. However, these methods, like evenly random assigning (Xin et al., 2013) or greedy assignment strategy (Gonzalez et al., 2012), are generic and do not consider any computation pattern for specific graph algorithm. We propose in this paper a vertex-cut partitioning dedicated to random walks algorithms which takes advantage of graph topological properties. It relies on a blocks approach which captures local communities. Our split and merge algorithms allow to achieve load balancing of the workers and to maintain it dynamically. Our experiments illustrate the benefit of our partitioning since it significantly reduce the communication cost when performing random walks-based algorithms compared with existing approaches.


AUTEUR(S)
Yifan LI, Camelia CONSTANTIN, Cédric DU MOUZA

MOTS-CLÉS
partitionnement de graphes, réseaux sociaux, performance.

KEYWORDS
graph partitioning, social networks, performance.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (391 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier