## 3 Use Cases of Graphs
### Partitioning Algorithm
We represent the files by an _SCSG_ graph, as in Figure 3 or Figure 2 and compute the k-cores decomposition for each representation. The _k-core values_ represent the minimum bytes shared between any vertices belonging to the core. Figure 5 shows the three core decomposition for the CHAIN topology and Figure 6 shows the cores for the STAR connection topology of the _SCSG_ graph. Table 3 shows the vertices contained in each of the three cores for the set of 19 files in Table 1. Note the \"nesting\" of the cores--the top core with 10 vertices (with a minimum sharing 52 bytes) is included in middle core (with a minimum sharing 20 bytes) that in turn is included in the lower core (with a minimum sharing 16 bytes) that contains all the vertices (19 files). To help decide what k-core to extract, _i.e._, where to cut, we also estimate the k-core (deduplicated) sizes. In Figure 7 we show the deduplicated sizes for each core for both connection topologies. The best place to partition the _SCSG_ graph for this small example is by extracting the k-core \"52\" with deduplicated size of 100 bytes as one partition and the remaining part of the graph (the \"periphery\") as the second partition of 60 bytes as the deduplicated size. The \"cut\" size (partitioning cost) is 8 bytes due to cutting the 2 edges (_i.e._, storing the shared bytes in both partitions) between core \"52\" and \"20\" with weights (sharing) 4 bytes each. This is true for both connection topologies CHAIN and STAR. In realistic cases, as shown in the next section, there are thousands of k-cores in the graph, all nested into each others from top, the densest connected, to the sparsest connected toward the periphery. As this small graph example shows, it is a good heuristic to \"cut\" outside the densest k-cores if possible. The edge weights are high inside the densest k-cores, so cutting in the middle of top k-cores is expensive. The densest k-cores for the real workloads are usually small in size, as will be shown next, so they do not need to be cut. \begin{table}
\begin{tabular}{c c c} \hline \hline
**K-Core Value** & **CHAIN** & **STAR** \\ \hline “52” & V1 to V10 & V1 to V11 \\ “20” & “52” and V1 to V15 & “52” and V1, V15 \\ “16” & All Vertics & All Vertics \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The three k-core values and the vertices composing them for each connection topology, CHAIN and STAR, for the 19 files from Table 1. The k-core values represent the minimum bytes shared between any vertices belonging to the core. Figure 7: The k-cores and their (deduplicated) size for the set of 19 files in Table 1 using CHAIN and STAR topology. There are three k-cores for each connection topology: the top core (value “52”) with (deduplicated) size of 100 bytes, the middle core (value “20”) with size of 124 bytes for CHAIN connectivity and 136 bytes for STAR, and the lower core (value “16”) with size 152 for both connection topologies. Results for the Real Workloads WL1 and WL2  
Table 4 shows the characteristics of the _SCSG_ graphs generated from the traces WL1 and WL2. Figure 8 shows the deduplicated (estimated from the graph) core size for each core, for both connection topologies, for workload WL1 (this is similar to Figure 7 for the small set of 19 files). Only the largest component of (deduplicated) size 746 GB (as shown in Table 4) is partitioned with k-cores. As all the vertices are contained in k-core 0, the size of k-core 0 is 746 GB. As can be seen in Figure 8 the sizes of the top k-cores (with minimum sharing between any pair of vertices over 3 GB) are very small. Figure 9 shows how the deduplication loss varies with the number of equal partitions we want to split the WL1 _SCSG_ graph into. To quantify the deduplication loss we define _partitioning cost_ as the amount of replicated data across partitions (due to the edge cuts in the partitioning process) divided by the total amount of removable duplicate data (before partitioning). As can be seen, the smaller the partition sizes are (the more partitions are), the higher the partition cost is.