Network Performance Aware Graph Partitioning for Large Graph Processing Systems in the Cloud - Large Scale and Big Data: Processing and Management - page 247

7.7.1 g eometriC m ethoDs
In geometric methods, each node of a graph is associated with a geometric loca-
tion (or coordinate). A classic example of a geometric algorithm is recursive coordi-
nate bisection [11]. This can be efficiently implemented with the multidimensional
binary tree or kD tree data structure. Follow-up research studies (e.g., [26,60]) have
improved the classic methods with more advanced heuristics or bisection methods.
7.7.2 s PeCtral m ethoDs
Spectral graph theory studies the relationships of fundamental properties of graphs
(e.g., algebraic connectivity) and the eigenvectors and eigenvalues of the Laplacian
matrix associated with the graphs [14,20]. In particular, the eigenvector associated
with algebraic connectivity (also known as the Fiedler vector) can be used to partition
graphs. There have many proposals on spectral partitioning and spectral bisection.
With spectral bisections, one can incorporate them into multilevel graph partition-
ing. It should be remarked that most of the results from spectral graph theory are
specific to undirected graphs.
An advantage of the spectral techniques is that they are supported by industrial-
strength softwares, not to mention the availability of advanced optimizations.
7.7.3 m etaheuristiC -b aseD a PProaChes
In general, it is difficult to produce high-quality solutions with approximation
algorithms of theoretical bounds. The metaheuristic approaches have mostly con-
centrated on finding high-quality solutions without performance guarantee in a
reasonable amount of time. Representatives of metaheuristic approaches include
simulated annealing [39], tabu search [66], ant colony optimization [16], and
genetic algorithms [57]. More details of these algorithms can be found in the
su r vey [51].
7.7.4 s treaming g raPh P artitioning
Instead of optimizing the graph partitioning quality, streaming graph partition-
ing emphasizes the graph partitioning performance while achieving a much better
graph partitioning quality than random hashing. It usually requires a simple pass (or
scan) of the graph, and generates the graph partitioning during the scan. Due to the
streaming nature, this category of graph partitioning algorithm can also be appli-
cable to streaming graphs. For online streaming graphs, Aggarwal et al. [3] proposed
an algorithm for clustering graph streams. They used a hash-based compression of
the edges to create microclusters onto a smaller domain space. They showed that
their method provides bounded accuracy in terms of distance computations. Stanton
et al. [72] developed simple heuristics for streaming graph and demonstrated their
effectiveness against simple hashing and Metis schemes. Fennel [74] is a general
framework for streaming graph partitioning. All these studies have demonstrated
significant gains in terms of the communication cost and runtime.