《人工智能、机器学习与大数据》课程教学资源（参考文献）Distributed Power-law Graph Computing - Theoretical and Empirical Analysis

Distributed Power-law Graph Computing: Theoretical and Empirical Analysis Cong Xie Ling Yan Dept.of Comp.Sci.and Eng. Dept.of Comp.Sci.and Eng. Shanghai Jiao Tong University Shanghai Jiao Tong University 800 Dongchuan Road 800 Dongchuan Road Shanghai 200240,China Shanghai 200240,China xcgoner1108@qmail.com yling0718@sjtu.edu.cn Wu-Jun Li Zhihua Zhang National Key Lab.for Novel Software Tech. Dept.of Comp.Sci.and Eng. Dept.of Comp.Sci.and Tech. Shanghai Jiao Tong University Nanjing University 800 Dongchuan Road Nanjing 210023,China Shanghai 200240,China liwujun@nju.edu.cn zhang-zhecs.situ.edu.cn Abstract With the emergence of big graphs in a variety of real applications like social networks,machine learning based on distributed graph-computing(DGC)frame works has attracted much attention from big data machine learning community. In DGC frameworks,the graph partitioning(GP)strategy plays a key role to af- fect the performance,including the workload balance and communication cost. Typically,the degree distributions of natural graphs from real applications follow skewed power laws,which makes GP a challenging task.Recently,many methods have been proposed to solve the GP problem.However,the existing GP methods cannot achieve satisfactory performance for applications with power-law graphs. In this paper,we propose a novel vertex-cut method,called degree-based hash- ing(DBH),for GP.DBH makes effective use of the skewed degree distributions for GP.We theoretically prove that DBH can achieve lower communication cost than existing methods and can simultaneously guarantee good workload balance. Furthermore,empirical results on several large power-law graphs also show that DBH can outperform the state of the art. 1 Introduction Recent years have witnessed the emergence of big graphs in a large variety of real applications, such as the web and social network services.Furthermore,many machine learning and data mining algorithms can also be modeled with graphs [14].Hence,machine learning based on distributed graph-computing(DGC)frameworks has attracted much attention from big data machine learning community [14,16,15,7,12,8].To perform distributed(parallel)graph-computing on clusters with several machines(servers),one has to partition the whole graph across the machines in a cluster. Graph partitioning(GP)can dramatically affect the performance of DGC frameworks in terms of workload balance and communication cost.Hence,the GP strategy typically plays a key role in DGC frameworks.The ideal GP method should minimize the cross-machine communication cost, and simultaneously keep the workload in every machine approximately balanced

Distributed Power-law Graph Computing: Theoretical and Empirical Analysis Cong Xie Dept. of Comp. Sci. and Eng. Shanghai Jiao Tong University 800 Dongchuan Road Shanghai 200240, China xcgoner1108@gmail.com Ling Yan Dept. of Comp. Sci. and Eng. Shanghai Jiao Tong University 800 Dongchuan Road Shanghai 200240, China yling0718@sjtu.edu.cn Wu-Jun Li National Key Lab. for Novel Software Tech. Dept. of Comp. Sci. and Tech. Nanjing University Nanjing 210023, China liwujun@nju.edu.cn Zhihua Zhang Dept. of Comp. Sci. and Eng. Shanghai Jiao Tong University 800 Dongchuan Road Shanghai 200240, China zhang-zh@cs.sjtu.edu.cn Abstract With the emergence of big graphs in a variety of real applications like social networks, machine learning based on distributed graph-computing (DGC) frame￾works has attracted much attention from big data machine learning community. In DGC frameworks, the graph partitioning (GP) strategy plays a key role to af￾fect the performance, including the workload balance and communication cost. Typically, the degree distributions of natural graphs from real applications follow skewed power laws, which makes GP a challenging task. Recently, many methods have been proposed to solve the GP problem. However, the existing GP methods cannot achieve satisfactory performance for applications with power-law graphs. In this paper, we propose a novel vertex-cut method, called degree-based hash￾ing (DBH), for GP. DBH makes effective use of the skewed degree distributions for GP. We theoretically prove that DBH can achieve lower communication cost than existing methods and can simultaneously guarantee good workload balance. Furthermore, empirical results on several large power-law graphs also show that DBH can outperform the state of the art. 1 Introduction Recent years have witnessed the emergence of big graphs in a large variety of real applications, such as the web and social network services. Furthermore, many machine learning and data mining algorithms can also be modeled with graphs [14]. Hence, machine learning based on distributed graph-computing (DGC) frameworks has attracted much attention from big data machine learning community [14, 16, 15, 7, 12, 8]. To perform distributed (parallel) graph-computing on clusters with several machines (servers), one has to partition the whole graph across the machines in a cluster. Graph partitioning (GP) can dramatically affect the performance of DGC frameworks in terms of workload balance and communication cost. Hence, the GP strategy typically plays a key role in DGC frameworks. The ideal GP method should minimize the cross-machine communication cost, and simultaneously keep the workload in every machine approximately balanced. 1

Existing GP methods can be divided into two main categories:edge-cut and vertex-cut methods. Edge-cut tries to evenly assign the vertices to machines by cutting the edges.In contrast,vertex-cut tries to evenly assign the edges to machines by cutting the vertices.Figure 1 illustrates the edge- cut and vertex-cut partitioning results of an example graph.In Figure 1 (a),the edges(A,C)and (A,E)are cut,and the two machines store the vertex sets {A,B,D}and [C,E,respectively.In Figure 1(b),the vertex A is cut,and the two machines store the edge sets {(A,B),(A,D),(B,D)} and {(A,C),(A,E),(C,E),respectively.In edge-cut,both machines of a cut edge should maintain a ghost (local replica)of the vertex and the edge data.In vertex-cut,all the machines associated with a cut vertex should maintain a mirror (local replica)of the vertex.The ghosts and mirrors are shown in shaded vertices in Figure 1.In edge-cut,the workload of a machine is determined by the number of vertices located in that machine,and the communication cost of the whole graph is determined by the number of edges spanning different machines.In vertex-cut,the workload of a machine is determined by the number of edges located in that machine,and the communication cost of the whole graph is determined by the number of mirrors of the vertices. (D (a)Edge-Cut (b)Vertex-Cut Figure 1:Two strategies for graph partitioning.Shaded vertices are ghosts and mirrors,respectively Most traditional DGC frameworks,such as GraphLab [14]and Pregel [16],use edge-cut method- s [10,19,20,21]for GP.Very recently,the authors of PowerGraph [7]find that the vertex-cut methods can achieve better performance than edge-cut methods,especially for power-law graph- s.Hence,vertex-cut has attracted more and more attention from DGC research community.For example,PowerGraph [7]adopts a random vertex-cut method and two greedy variants for GP. GraphBuilder [9]provides some heuristics,such as the grid-based constrained solution,to improve the random vertex-cut method. Large natural graphs usually follow skewed degree distributions like power-law distributions,which makes GP challenging.Different vertex-cut methods can result in different performance for power- law graphs.For example,Figure 2(a)shows a toy power-law graph with only one vertex having much higher degree than the others.Figure 2(b)shows a partitioning strategy by cutting the vertices {E,F,A,C,D),and Figure 2(c)shows a partitioning strategy by cutting the vertices [A,E).We can find that the partitioning strategy in Figure 2(c)is better than that in Figure 2(b)because the number of mirrors in Figure 2(c)is smaller which means less communication cost.The intuition underlying this example is that cutting higher-degree vertices can result in fewer mirror vertices. Hence,the power-law degree distribution can be used to facilitate GP.Unfortunately,existing vertex- cut methods,including those in PowerGraph and GraphBuilder,make rarely use of the power-law degree distribution for GP.Hence,they cannot achieve satisfactory performance in natural power- law graphs.PowerLyra [4]tries to combine both edge-cut and vertex-cut together by using the power-law degree distribution.However,it is lack of theoretical guarantee. (b)Bad partitioning D (a)Sample (c)Good partitioning Figure 2:Partition a sample graph with vertex-cut

Existing GP methods can be divided into two main categories: edge-cut and vertex-cut methods. Edge-cut tries to evenly assign the vertices to machines by cutting the edges. In contrast, vertex-cut tries to evenly assign the edges to machines by cutting the vertices. Figure 1 illustrates the edge￾cut and vertex-cut partitioning results of an example graph. In Figure 1 (a), the edges (A,C) and (A,E) are cut, and the two machines store the vertex sets {A,B,D} and {C,E}, respectively. In Figure 1 (b), the vertex A is cut, and the two machines store the edge sets {(A,B),(A,D),(B,D)} and {(A,C),(A,E),(C,E)}, respectively. In edge-cut, both machines of a cut edge should maintain a ghost (local replica) of the vertex and the edge data. In vertex-cut, all the machines associated with a cut vertex should maintain a mirror (local replica) of the vertex. The ghosts and mirrors are shown in shaded vertices in Figure 1. In edge-cut, the workload of a machine is determined by the number of vertices located in that machine, and the communication cost of the whole graph is determined by the number of edges spanning different machines. In vertex-cut, the workload of a machine is determined by the number of edges located in that machine, and the communication cost of the whole graph is determined by the number of mirrors of the vertices. (a) Edge-Cut (b) Vertex-Cut Figure 1: Two strategies for graph partitioning. Shaded vertices are ghosts and mirrors, respectively. Most traditional DGC frameworks, such as GraphLab [14] and Pregel [16], use edge-cut method￾s [10, 19, 20, 21] for GP. Very recently, the authors of PowerGraph [7] find that the vertex-cut methods can achieve better performance than edge-cut methods, especially for power-law graph￾s. Hence, vertex-cut has attracted more and more attention from DGC research community. For example, PowerGraph [7] adopts a random vertex-cut method and two greedy variants for GP. GraphBuilder [9] provides some heuristics, such as the grid-based constrained solution, to improve the random vertex-cut method. Large natural graphs usually follow skewed degree distributions like power-law distributions, which makes GP challenging. Different vertex-cut methods can result in different performance for power￾law graphs. For example, Figure 2 (a) shows a toy power-law graph with only one vertex having much higher degree than the others. Figure 2 (b) shows a partitioning strategy by cutting the vertices {E, F, A, C, D}, and Figure 2 (c) shows a partitioning strategy by cutting the vertices {A, E}. We can find that the partitioning strategy in Figure 2 (c) is better than that in Figure 2 (b) because the number of mirrors in Figure 2 (c) is smaller which means less communication cost. The intuition underlying this example is that cutting higher-degree vertices can result in fewer mirror vertices. Hence, the power-law degree distribution can be used to facilitate GP. Unfortunately, existing vertex￾cut methods, including those in PowerGraph and GraphBuilder, make rarely use of the power-law degree distribution for GP. Hence, they cannot achieve satisfactory performance in natural power￾law graphs. PowerLyra [4] tries to combine both edge-cut and vertex-cut together by using the power-law degree distribution. However, it is lack of theoretical guarantee. (a) Sample (b) Bad partitioning (c) Good partitioning Figure 2: Partition a sample graph with vertex-cut. 2

In this paper,we propose a novel vertex-cut GP method,called degree-based hashing (DBH),for distributed power-law graph computing.The main contributions of DBH are briefly outlined as follows: DBH can effectively exploit the power-law degree distributions in natural graphs for vertex- cut GP. Theoretical bounds on the communication cost and workload balance for DBH can be de- rived,which show that DBH can achieve lower communication cost than existing methods and can simultaneously guarantee good workload balance. DBH can be implemented as an execution engine for PowerGraph [7],and hence all PowerGraph applications can be seamlessly supported by DBH. Empirical results on several large real graphs and synthetic graphs show that DBH can outperform the state-of-the-art methods. 2 Problem Formulation Let G=(V,E)denote a graph,where V={v1,v2,...,Un}is the set of vertices and E CV x V is the set of edges in G.Let VI denote the cardinality of the set V,and hence VI=n.vi and vj are called neighbors if(vi,vj)EE.The degree of vi is denoted as di,which measures the number of neighbors of vi.Please note that we only need to consider the GP task for undirected graphs because the workload mainly depends on the number of edges no matter directed or undirected graphs the computation is based on.Even if the computation is based on directed graphs,we can also use the undirected counterparts of the directed graphs to get the partitioning results. Assume we have a cluster of p machines.Vertex-cut GP is to assign each edge with the two corre- sponding vertices to one of the p machines in the cluster.The assignment of an edge is unique,while vertices may have replicas across different machines.For DGC frameworks based on vertex-cut GP, the workload(amount of computation)of a machine is roughly linear in the number of edges located in that machine,and the replicas of the vertices incur communication for synchronization.So the goal of vertex-cut GP is to minimize the number of replicas and simultaneously balance the number of edges on each machine Let M(e)E{1,...,p}be the machine edge eE is assigned to,and A(v){1,...,p}be the span of vertex v over different machines.Hence,A(v)is the number of replicas of v among different machines.Similar to PowerGraph [7],one of the replicas of a vertex is chosen as the master and the others are treated as the mirrors of the master.We let Master(v)denote the machine in which the master of v is located.Hence,the goal of vertex-cut GP can be formulated as follows: min∑A(训 47 m日=ml<λg.and m∈v1 Nasder(e)=ml<P分 where m∈{l,.,p}denotes a machine,入≥1 and p≥1 are imbalance factors.Wede fineA(vi)as replication factor,maxHeE M(e)=m)as edge-imbalance,and maxV Master()-mas vertex-imbalance.To get a good balance of workload. and p should be as small as possible. The degrees of natural graphs usually follow skewed power-law distributions [3,1]: Pr(d)d-a, where Pr(d)is the probability that a vertex has degree d and the power parameter a is a positive constant.The lower the a is,the more skewed a graph will be.This power-law degree distribu- tion makes GP challenging [7].Although vertex-cut methods can achieve better performance than edge-cut methods for power-law graphs [7],existing vertex-cut methods,such as random method in PowerGraph and grid-based method in GraphBuilder [9],cannot make effective use of the power- law distribution to achieve satisfactory performance

In this paper, we propose a novel vertex-cut GP method, called degree-based hashing (DBH), for distributed power-law graph computing. The main contributions of DBH are briefly outlined as follows: • DBH can effectively exploit the power-law degree distributions in natural graphs for vertex￾cut GP. • Theoretical bounds on the communication cost and workload balance for DBH can be de￾rived, which show that DBH can achieve lower communication cost than existing methods and can simultaneously guarantee good workload balance. • DBH can be implemented as an execution engine for PowerGraph [7], and hence all PowerGraph applications can be seamlessly supported by DBH. • Empirical results on several large real graphs and synthetic graphs show that DBH can outperform the state-of-the-art methods. 2 Problem Formulation Let G = (V, E) denote a graph, where V = {v1, v2, . . . , vn} is the set of vertices and E ⊆ V × V is the set of edges in G. Let |V | denote the cardinality of the set V , and hence |V | = n. vi and vj are called neighbors if (vi , vj ) ∈ E. The degree of vi is denoted as di , which measures the number of neighbors of vi . Please note that we only need to consider the GP task for undirected graphs because the workload mainly depends on the number of edges no matter directed or undirected graphs the computation is based on. Even if the computation is based on directed graphs, we can also use the undirected counterparts of the directed graphs to get the partitioning results. Assume we have a cluster of p machines. Vertex-cut GP is to assign each edge with the two corre￾sponding vertices to one of the p machines in the cluster. The assignment of an edge is unique, while vertices may have replicas across different machines. For DGC frameworks based on vertex-cut GP, the workload (amount of computation) of a machine is roughly linear in the number of edges located in that machine, and the replicas of the vertices incur communication for synchronization. So the goal of vertex-cut GP is to minimize the number of replicas and simultaneously balance the number of edges on each machine. Let M(e) ∈ {1, . . . , p} be the machine edge e ∈ E is assigned to, and A(v) ⊆ {1, . . . , p} be the span of vertex v over different machines. Hence, |A(v)| is the number of replicas of v among different machines. Similar to PowerGraph [7], one of the replicas of a vertex is chosen as the master and the others are treated as the mirrors of the master. We let M aster(v) denote the machine in which the master of v is located. Hence, the goal of vertex-cut GP can be formulated as follows: min A 1 n Xn i=1 |A(vi)| s.t. max m |{e ∈ E | M(e) = m}| < λ|E| p , and max m |{v ∈ V | M aster(v) = m}| < ρ n p , where m ∈ {1, . . . , p} denotes a machine, λ ≥ 1 and ρ ≥ 1 are imbalance factors. We de- fine 1 n Pn i=1 |A(vi)| as replication factor, p |E| max m |{e ∈ E | M(e) = m}| as edge-imbalance, and p n max m |{v ∈ V | M aster(v) = m}| as vertex-imbalance. To get a good balance of workload, λ and ρ should be as small as possible. The degrees of natural graphs usually follow skewed power-law distributions [3, 1]: Pr(d) ∝ d −α , where Pr(d) is the probability that a vertex has degree d and the power parameter α is a positive constant. The lower the α is, the more skewed a graph will be. This power-law degree distribu￾tion makes GP challenging [7]. Although vertex-cut methods can achieve better performance than edge-cut methods for power-law graphs [7], existing vertex-cut methods, such as random method in PowerGraph and grid-based method in GraphBuilder [9], cannot make effective use of the power￾law distribution to achieve satisfactory performance. 3

3 Degree-Based Hashing for GP In this section,we propose a novel vertex-cut method,called degree-based hashing (DBH),to ef- fectively exploit the power-law distribution for GP. 3.1 Hashing Model We refer to a certain machine by its index idz,and the idrth machine is denoted as Pid.We first de- fine two kinds of hash functions:vertex-hash function id verter_hash(v)which hashes vertex v to the machine Pidz,and edge-hash function idr edgehash(e)or idx edge_hash(vi,vj) which hashes edge e=(vi,vi)to the machine Pidz. Our hashing model includes two main components: Master-vertex assignment:The master replica of vi is uniquely assigned to one of the p machines with equal probability for each machine by some randomized hash function verter hash(vi). Edge assignment:Each edge e =(vi,vj)is assigned to one of the p machines by some hash function edge_hash(vi,vj). It is easy to find that the above hashing model is a vertex-cut GP method.The master-vertex as- signment can be easily implemented,which can also be expected to achieve a low vertex-imbalance score.On the contrary,the edge assignment is much more complicated.Different edge-hash func- tions can achieve different replication factors and different edge-imbalance scores.Please note that replication factor reflects communication cost,and edge-imbalance reflects workload-imbalance. Hence,the key of our hashing model lies in the edge-hash function edge_hash(vi,vj). 3.2 Degree-Based Hashing From the example in Figure 2,we observe that in power-law graphs the replication factor,which is defined as the total number of replicas divided by the total number of vertices,will be smaller if we cut vertices with relatively higher degrees.Based on this intuition,we define the edge_hash(vi,vj) as follows: edgehash(vi,vj)= fvertex-hash(vi)if di<dj, (1) verterhash(v;)otherwise. It means that we use the vertex-hash function to define the edge-hash function.Furthermore,the edge-hash function value of an edge is determined by the degrees of the two associated vertices. More specifically,the edge-hash function value of an edge is defined by the vertex-hash function value of the associated vertex with a smaller degree.Hence,our method is called degree-based hashing(DBH).DBH can effectively capture the intuition that cutting vertices with higher degrees will get better performance. Our DBH method for vertex-cut GP is briefly summarized in Algorithm 1,where [n)={1,...,n}. Algorithm 1 Degree-based hashing(DBH)for vertex-cut GP Input:The set of edges E;the set of vertices V;the number of machines p. Output:The assignment M(e)E[p for each edge e. 1:Initialization:count the degree di for each i [n]in parallel 2:for all e =(vi,vj)EE do 3: Hash each edge in parallel: 4: if di<di then 5: M(e)←-verter_hash(i) 6: else M(e)verterhash(vj) 8: end if 9:end for

3 Degree-Based Hashing for GP In this section, we propose a novel vertex-cut method, called degree-based hashing (DBH), to ef￾fectively exploit the power-law distribution for GP. 3.1 Hashing Model We refer to a certain machine by its index idx, and the idxth machine is denoted as Pidx. We first de- fine two kinds of hash functions: vertex-hash function idx = vertex hash(v) which hashes vertex v to the machine Pidx, and edge-hash function idx = edge hash(e) or idx = edge hash(vi , vj ) which hashes edge e = (vi , vj ) to the machine Pidx. Our hashing model includes two main components: • Master-vertex assignment: The master replica of vi is uniquely assigned to one of the p machines with equal probability for each machine by some randomized hash function vertex hash(vi). • Edge assignment: Each edge e = (vi , vj ) is assigned to one of the p machines by some hash function edge hash(vi , vj ). It is easy to find that the above hashing model is a vertex-cut GP method. The master-vertex as￾signment can be easily implemented, which can also be expected to achieve a low vertex-imbalance score. On the contrary, the edge assignment is much more complicated. Different edge-hash func￾tions can achieve different replication factors and different edge-imbalance scores. Please note that replication factor reflects communication cost, and edge-imbalance reflects workload-imbalance. Hence, the key of our hashing model lies in the edge-hash function edge hash(vi , vj ). 3.2 Degree-Based Hashing From the example in Figure 2, we observe that in power-law graphs the replication factor, which is defined as the total number of replicas divided by the total number of vertices, will be smaller if we cut vertices with relatively higher degrees. Based on this intuition, we define the edge hash(vi , vj ) as follows: edge hash(vi , vj ) =  vertex hash(vi) if di < dj , vertex hash(vj ) otherwise. (1) It means that we use the vertex-hash function to define the edge-hash function. Furthermore, the edge-hash function value of an edge is determined by the degrees of the two associated vertices. More specifically, the edge-hash function value of an edge is defined by the vertex-hash function value of the associated vertex with a smaller degree. Hence, our method is called degree-based hashing (DBH). DBH can effectively capture the intuition that cutting vertices with higher degrees will get better performance. Our DBH method for vertex-cut GP is briefly summarized in Algorithm 1, where [n] = {1, . . . , n}. Algorithm 1 Degree-based hashing (DBH) for vertex-cut GP Input: The set of edges E; the set of vertices V ; the number of machines p. Output: The assignment M(e) ∈ [p] for each edge e. 1: Initialization: count the degree di for each i ∈ [n] in parallel 2: for all e = (vi , vj ) ∈ E do 3: Hash each edge in parallel: 4: if di < dj then 5: M(e) ← vertex hash(vi) 6: else 7: M(e) ← vertex hash(vj ) 8: end if 9: end for 4

4 Theoretical Analysis In this section,we present theoretical analysis for our DBH method.For comparison,the ran- dom vertex-cut method (called Random)of PowerGraph [7]and the grid-based constrained solu- tion(called Grid)of GraphBuilder [9]are adopted as baselines.Our analysis is based on random- ization.Moreover,we assume that the graph is undirected and there are no duplicated edges in the graph.We mainly study the performance in terms of replication factor,edge-imbalance and vertex- imbalance defined in Section 2.Due to space limitation,we put the proofs of all theoretical results into the supplementary material. 4.1 Partitioning Degree-fixed Graphs Firstly,we assume that the degree sequence [di is fixed.Then we can get the following expected replication factor produced by different methods. Random assigns each edge evenly to the p machines via a randomized hash function.The result can be directly got from PowerGraph [7]. Lemma 1.Assume that we have a sequence of n vertices [vi and the corresponding degree sequence D={diA simple randomized vertex-cut on p machines has the expected replication factor: 空ap---)] By using the Grid hash function,each vertex has p rather than p candidate machines compared to Random.Thus we simply replace p with p to get the following corollary. Corollary 1.By using Grid for hashing,the expected replication factor on p machines is: 24l0-三--》] Using DBH method in Section 3.2,we obtain the following result by fixing the sequence [h, where h;is defined as the number of v:'s adjacent edges which are hashed by the neighbors of v according to the edge-hash function defined in(1). Theorem 1.Assume that we have a sequence ofn vertices and the corresponding degree sequence D =(di.For each vi.di-hi adjacent edges of it are hashed by vi itself.Define H=hi.Our DBH method on p machines has the expected replication factor: 2---門s--] where hi≤d-1for any. This theorem says that our DBH method has smaller expected replication factor than Random of PowerGraph [7]. Next we turn to the analysis of the balance constraints.We still fix the degree sequence and have the following result for our DBH method. Theorem 2.Our DBH method on p machines with the sequences {vi)1,{di and (hi defined in Theorem I has the edge-imbalance: maxl{e∈E|M(e)=mH +ma ∑(d-h) 1=1 P jElp]vEP; EV/p 2EV/p Although the master vertices are evenly assigned to each machine,we want to show how the ran- domized assignment is close to the perfect balance.This problem is well studied in the model of uniformly throwing n balls into p bins when n>p(Inp)3 [18]

4 Theoretical Analysis In this section, we present theoretical analysis for our DBH method. For comparison, the ran￾dom vertex-cut method (called Random) of PowerGraph [7] and the grid-based constrained solu￾tion (called Grid) of GraphBuilder [9] are adopted as baselines. Our analysis is based on random￾ization. Moreover, we assume that the graph is undirected and there are no duplicated edges in the graph. We mainly study the performance in terms of replication factor, edge-imbalance and vertex￾imbalance defined in Section 2. Due to space limitation, we put the proofs of all theoretical results into the supplementary material. 4.1 Partitioning Degree-fixed Graphs Firstly, we assume that the degree sequence {di} n i=1 is fixed. Then we can get the following expected replication factor produced by different methods. Random assigns each edge evenly to the p machines via a randomized hash function. The result can be directly got from PowerGraph [7]. Lemma 1. Assume that we have a sequence of n vertices {vi} n i=1 and the corresponding degree sequence D = {di} n i=1. A simple randomized vertex-cut on p machines has the expected replication factor: E " 1 n Xn i=1 |A(vi)|     D # = p n Xn i=1  1 −  1 − 1 p di  . By using the Grid hash function, each vertex has √p rather than p candidate machines compared to Random. Thus we simply replace p with √p to get the following corollary. Corollary 1. By using Grid for hashing, the expected replication factor on p machines is: E " 1 n Xn i=1 |A(vi)|     D # = √p n Xn i=1  1 −  1 − 1 √p di  . Using DBH method in Section 3.2, we obtain the following result by fixing the sequence {hi} n i=1, where hi is defined as the number of vi’s adjacent edges which are hashed by the neighbors of vi according to the edge-hash function defined in (1). Theorem 1. Assume that we have a sequence of n vertices {vi} n i=1 and the corresponding degree sequence D = {di} n i=1. For each vi , di − hi adjacent edges of it are hashed by vi itself. Define H = {hi} n i=1. Our DBH method on p machines has the expected replication factor: E " 1 n Xn i=1 |A(vi)|     H, D# = p n Xn i=1  1 −  1 − 1 p hi+1 ≤ p n Xn i=1  1 −  1 − 1 p di  , where hi ≤ di − 1 for any vi . This theorem says that our DBH method has smaller expected replication factor than Random of PowerGraph [7]. Next we turn to the analysis of the balance constraints. We still fix the degree sequence and have the following result for our DBH method. Theorem 2. Our DBH method on p machines with the sequences {vi} n i=1, {di} n i=1 and {hi} n i=1 defined in Theorem 1 has the edge-imbalance: max m |{e ∈ E | M(e) = m}| |E|/p = Pn i=1 hi p + max j∈[p] P vi∈Pj (di − hi) 2|E|/p . Although the master vertices are evenly assigned to each machine, we want to show how the ran￾domized assignment is close to the perfect balance. This problem is well studied in the model of uniformly throwing n balls into p bins when n  p(ln p) 3 [18]. 5