## 4 Improve Ordering Using SemiLocal Moves
### Rank Swap  
Given an existing linear ordering of vertices in a graph we can further improve the cut size (of the fully balanced partition based on it) via semilocal swaps. Note that unlike MinLA heuristic discussed in Section 4.1, this process depends on the pre-selected cut boundaries, that is, the number of final partitions \(k\). Notice that one expects that the semilocal swap operations will be effective once a good initial ordering provided by either the Affinity-based mapping and/or MinLA. Indeed our experimental results show that this procedure is extremely effective and produces cut sizes better than the competition on some public social graphs we tried.  
RankSwap can be implemented in a straightforward way on a distributed (for example, MapReduce) framework as outlined by Algorithm 3.  
```
0: Graph G, number of partitions \(k\), number of intervals per partition \(r\)
0: A partition of \(V(G)\) into \(k\) parts - Controller:
1: Pair nearby partitions
2: Split each partition into \(r\) intervals \(I_{0},\ldots,I_{r-1}\) and randomly pair intervals between paired partitions - Map \(\langle I_{i};I_{j}\rangle\):
3:repeat
4: Pick node pair \(u\in I_{i}\), \(v\in I_{j}\) with the best cut improvement
5: Swap \(u\) and \(v\)
6:until no pair improves the cut
7:for all\(u\in I_{i}\cup I_{j}\)do
8: Emit \(\langle u;r_{u}\rangle\). \(\{r_{u}\) is the new rank of \(u\}\)
9:Reduce\(\langle u;r_{u}\rangle\):
10: Emit \(\langle u;r_{u}\rangle\). [Identity Reducer]
```  
**Algorithm 3**RankSwap\((G,k,r)\)  
Subdividing each partition into intervals is important, especially for small number of partitions \(k\), to achieve parallelism and allowing possibly more time- and memory-consuming swap operations. Pairing the intervals between two partitions can be done in various ways. One simple example is random pairing. Our experiments showed that this is almost as effective as more complicated ones, hence we do not discuss the other methods in detail here.  
The swap operation between two intervals (handled by each Mapper task) can be done in various ways. (The version described in Algorithm 3 is Method 3 below).  
Each approach below starts with computing the cut size reduction as a result of moving a node from one interval to the other. Once these values are computed for each node in the two intervals, the following are the alternatives we tried (from the simplest to more complicated):  
* **Method 1:** Sort the nodes in each interval in descending order by their cut size reduction. Then simply do a pairwise swap between entries at \(i\)-th place in each interval provided that the swap results in a combined reduction. This method is very simple and fast, however, it may have side effects within the interval (and also outside) since it does not account for those.
* **Method 2:** This is a modified version of Method 1 with the addition that after each swap is performed, we also update the cut reduction values of other nodes. This method does only one pass from top to bottom and stops when there is no further improvement.
* **Method 3:** In this method we iterate on Method 2 until we converge to a stable state. In this way we reach a local optimum between two intervals. The other improvement is that instead of pairing entries at \(i\)-th position, we find the best pair in the second interval and swap with that. This is because the top entries in each interval can be neighbors of each other and therefore they may not be the best pair to swap.  
Our extensive studies with these methods confirmed that Method 3 gives the best results in terms of quality at the expense of an acceptable additional cost. It runs fast in practice due to the relatively small sizes of the intervals because of the parallelism we achieve. We can also afford an additional cost in the swap method because each interval pair is handled by a separate Mapper task.