## 6 Empirical Studies
### Comparison to Previous Work  
The most relevant among the previous work are the scalable label propagation-based algorithms of [PERSON] (2000) and [PERSON] et al. [PERSON] et al. (2019). The former reports their results on an internal graph (for Facebook) and a public social graph, LiveJournal, while the latter reports results on LiveJournal and Twitter. Table 2 compares our results to prior work on LiveJournal. The cut sizes in the table for \(k=40,60,80\) for Reference [PERSON] and [PERSON] (2000) and all the numbers for Reference [PERSON] et al. (2019) are approximates taken from the graph provided in Reference [PERSON] and [PERSON] (2000) as they do not report the exact values. The numbers in parentheses show the maximum imbalance in partition sizes, and the cut sizes are reported as fractions of total number of edges in the graph.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline \(k\) & [4] (\(-\)0.5 mm) (\%) & Spinner (\%) & Aff (\%) & Combination (\%) \\ \hline
20 & 37\% & 38\% & 35.71\% & **27.50\%** \\
40 & 43\% & 40\% & 40.83\% & **33.71\%** \\
60 & 46\% & 43\% & 43.03\% & **36.65\%** \\
80 & 47.5\% & 44\% & 43.27\% & **38.65\%** \\
100 & 49\% & 46\% & 45.05\% & **41.53\%** \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison to prior work on LiveJournal. The main entries are the ratio of edges cut by the clustering over the total number of edges in the graph. The number of clusters is denoted by \(k\). Numbers in parentheses are permissible imbalance (Best results in each row are typeset in bold for easier spotting).  
Figure 9: Convergence rate of Aff+Metric (**top**) and Aff+Swap (**bottom**) on World-roads.  
Even our initial linear embedding (obtained by constructing the hierarchical clustering based on a weighted version of the input, where edge weights denote the number of common neighbors between two vertices) is consistently better than the best previous result. Our algorithm with the postprocessing obtains 15% to 25% improvement over the previous results (better for smaller \(k\)) and it only requires a couple of postprocessing rounds to converge. We take note that the results of Reference [4] allow 5% imbalance whereas our results produce almost perfectly balanced partitions.  
Twitter is another public graph, for which the results of state-of-the-art minimum-cut partitioning is available. In Table 3 we report and compare the results of our main algorithm, Combination, for this graph to the best previous methods. (Numbers for Reference [21] are quoted from Reference [19]).  
Algorithms developed in References [5; 21] are suitable for the streaming model but one can implement variants of those algorithms in a distributed manner. Our implementation of a natural distributed version of the FENNEL algorithm does not achieve the same results as those reported for the streaming implementation reported in Reference [5]. However, we compare our algorithm directly to the numbers reported on Twitter by FENNEL [5].  
Finally we report in Table 4 the cut sizes for another public graph, Friendster, so others can compare their results with it. The running time of our algorithms are not affected with large \(k\) the running time difference for \(k=2\) and tens of thousands is less than 1%, well within the noise associated with the distributed system. In fact, construction of the initial ordering is independent of \(k\), and the post-processing steps may only take advantage of the increased parallelism possible for large \(k\).  
We also make our partitions for Twitter, LiveJournal and Friendster publicly available [23].