Distributed bipartite graph clustering

Bipartite graphs are graphs whose vertices can be divided into two independent sets (X and Y) such that no two graph vertices within the same set are adjacent. There are many real-world examples which display natural bipartite structure. For instance, a bipartite graph where the distinct set of vertices are people and books and edges represent buying relationship between them. Another prominent example is a bipartite graph where the vertex sets are candidates and jobs and if a candidate applies to job, there is an edge between the corresponding vertices. In this thesis, we implement a distributed bipartite clustering method for large and sparse data. There are several approaches to cluster data which is bipartite in nature. For example k-means clustering method can be applied to the both sides of the graph separately. But bipartite clustering requires a clustering method that clusters data simultaneously. Spectral clustering is a way to cluster bipartite data simultaneously which means assigning vertices from both sides into the same coherent cluster. We use multi bipartitioning clustering algorithm which is based on spectral clustering in this thesis along with some other bipartite partitioning algorithms such as Bifennel, Aweto and etc. There are some steps that need to be done before bipartite graph is clustered. Firstly, bipartite graph is converted into adjacency matrix where rows represent one set of vertices of bipartite graph and columns represent the other set of vertices. If there is an edge between two vertices, then the value of the corresponding cell of the adjacency matrix is assigned to 1, otherwise it is assigned to 0. After having the adjacency matrix, the Laplace form of the adjacency matrix is created. This matrix is also known as degree matrix. Degree matrices namely D1 and D2 are constructed for X and Y respectively. Then adjacency matrix is multiplied with D1 and D2. Lastly, the spectral algorithm runs Singular Value Decomposition (SVD) on the formed adjacency matrix and finds second singular left and right vectors. After finding second singular right and left vectors, k-means clustering algorithm is run on these vectors to cluster data. This method only partitions the data into two cluster. But finding other singular vectors (2.,3.,...) other than only the second one, more clusters can be obtained. In this thesis, we used distributed SVD algorithm to find singular left and right vectors of adjacency matrix when the matrix is large and sparse. Distributed SVD algorithm divides the matrix into column-wise sub matrices and calculates SVD on these sub matrices independently. It is capable of finding the singular values, left and right vectors when the matrix is rectangular (number of rows are much more smaller than number of columns or vice versa) and dense. In other words, the rank of the sub matrices must be equal to the rank of the adjacency matrix itself. Because of the sparsity of the data, the rank that is less in sub matrices than the adjacency matrix xxi causes to find singular values and vectors with high error. We proposed an algorithm, called Ranky, to handle this problem. Ranky algorithm detects the rows which cause the rank of the sub matrices less then the rank of the adjacency matrix and fills accordingly in order to make them equal. Despite the Ranky algorithm can handle this problem, balanced clusters can not be obtained because of the sparse matrix. After that, we used partitioning algorithms to compress the adjacency matrix into dense matrix and then applied spectral clustering. There are several partitioning algorithms such as Hash, Grid, Aweto, Bifennel etc. But only Aweto and Bifennel take the advantage of bipartite graphs as we know. We use Bifennel partitioning algorithm and Distributed Bifennel algorithm to compress the data due to their efficiency and less replication factor. Lastly, we decompress the partitions to get final clusters. The evaluation criteria is the replication factor that measures partitioning algorithm performance in terms of the number of replicated vertices. The experimental results on a real world data set show that Distributed Bifennel algorithm has outperformed Bifennel algorithm in terms of execution time, while both algorithms produce equally likely replication factor, using different datasets. Each algorithm is run on the same datasets with different partitioning numbers (500 and 1000). Distributed Bifennel algorithm has partitioned the data 10 times faster than Bifennel using at most 28 threads. The algorithm was implemented in C++ and run on a 28 cores and 128 GB RAM machine running Linux. More experimental results with different settings are given in chapter 5.