## 3 Use Cases of Graphs
### Partitioning Algorithm  
To solve the deduplication domain partitioning problem we employ an _SCSG_ graph model, introduced in Section 2.1, to represent the deduplication domain (original set of files in deduplicated form), and to partition this graph into subgraphs that represent subsets of files in deduplicated form, _with minimal loss_ in overall deduplication ratio and without splitting files across partitions (each file, all its chunks, should fit in only one partition). Minimizing the deduplication loss for our _SCSG_ graph model means minimizing the total edge \"cuts\" (sum of edge weights between subgraphs). Remember that in _SCSG_ graphs, edge weights represent the number of bytes (sum of chunk sizes) _shared_ by the two vertices (files) connected by the edge, so if these end vertices are in different partitions, the shared chunks have to be replicated (stored in each partition). As it is well known, the graph partitioning is an NP-complete problem [7]. We want to find a fast algorithm that exploits the characteristics of the content sharing _SCSG_ graphs for real workloads, and provide a good approximate solution to our deduplication domain partitioning. Figure 1 shows the type of content sharing graphs we usually get. Indeed, representing our workloads (described in Section 3.1) by _SCSG_ graphs, we obtain a large number of small _components_ (containing only few files each), and one or a few large components. Therefore, the first step of the partitioning algorithm is _finding the components_ in the graph, which can be done in linear time with the size of the graph (number of edges) by a Breadth First Search (BFS) graph traversal. Generally, we obtain many small components, as in Figure 1, where the _SCSG_ graph consists of \(103\) distinct components, all relatively small with one exception. If each component size (sum of vertex sizes minus connecting edge weights) can fit in a partition (tape in the concrete case), then a greedy heuristic for the bin packing problem (like sorting the components in decreasing order of size and storing the components in this order in each partition) solves our partitioning. However, if some component size is larger than the available space in any partition, then further partitioning of that component is needed. For this we are going to use an important concept, that of a k-core, introduced by social networks researchers [8, 9]. A _k-core_ of a graph is a maximal subgraph in which each vertex is adjacent to at least \(k\) other vertices (within the subgraph); therefore all the vertices within the k-core have a _degree_\(\geq\)\(k\). We use an extension of the k-core concept where each edge contributes its weight (an integer number of bytes \(\geq\)\(1\)) to the computation of \"degree\". The k-cores are nested (like the Russian dolls) one in the other, the highest into the lowest, each vertex having a \"coreness\" number that is the highest \(k\) in the k-cores it belongs to (note that all vertices in a connected component belong to the 1-core, just by being connected). The coreness for all vertices can be computed very fast, in almost linear time in the number of vertices, in one graph traversal with local computation of vertex degrees. In addition to the coreness numbers, in another BFS traversal, we compute the estimated deduplicated size of each k-core, that is, the sum of vertex sizes minus the sum of edge sizes inside each k-core. We use this estimated deduplication size to decide what k-core to extract in an optimal partitioning plan. To illustrate the k-core decomposition and k-core size computation let us take as example the 19 files described in Table 1 and say that we want to partition them into two partitions (subsets) in such a way that (1) we have a minimal loss in deduplication (due to replication of chunks shared across partitions),(2) each file (all its chunks) belongs to only one partition and (3) the partitions have sizes relatively close to each other.