Community Detection in Complex Network Metric Space Nearest Neighbor Search Low Rank Approximation and Optimality

Abstract

Community detection in complex network is an important problem of much interest in recent years. In general a community detection algorithm chooses an objective function and captures the communities of the network by optimizing the objective function and then one uses various heuristics to solve the optimization problem to extract the interesting communities for the user. The objective of this thesis is to bridge the gap between two important research directions 1 complex network analysis which deals with large real newlinegraphs but generally studied via graph theoretic analysis or spectral analysis and 2 data analysis in metric space using geometric distances nearest neighbor search which is a fundamental computational tool for large data analysis and lowrank approximation of distance matrix. In the second chapter we have demonstrated the procedure to transform a graph into points of a metric space and developed the methods of community detection with the help of metric defined for pair of points. We have also studied and analyzed the community structure of the network therein. The results obtained with our approach are very competitive with most of the well known algorithms in the literature and this is justified over the large collection of datasets. On the otherhand it can be observed that time taken by our algorithm is quite less compared to other methods. In the third chapter we have studied the nearest neighbor search problem in complex network by the development of a suitable notion of nearness. The computation of efficient nearest neighbor search among the nodes of a complex network using the metric tree and locality sensitive hashingLSH are also studied and experimented. For evaluation of the proposed nearest neighbor search on complex network we applied it in network community detection problem. Experiments are performed to verify the usefulness of nearness measures for the complex networks and the role of metric tree and LSH to compute fast community detection using nearest neighbor search.