Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/139675
Title: Community Detection in Complex Network Metric Space Nearest Neighbor Search Low Rank Approximation and Optimality
Researcher: Saha, Suman
Guide(s): Ghrera, Satya Prakash
Keywords: Community Detection
Complex Network
Low-Rank Approximation And Optimality
Metric Space
Nearest Neighbor Search
University: Jaypee University of Information Technology, Solan
Completed Date: 2016
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.
URI: http://hdl.handle.net/10603/139675
Appears in Departments:Department of Computer Science Engineering

Files in This Item:
File Description SizeFormat 
01_tittle.pdfAttached File156.16 kBAdobe PDFView/Open
02_declaration.pdf248.93 kBAdobe PDFView/Open
03_certificate.pdf243.89 kBAdobe PDFView/Open
04_acknowledgement.pdf522.13 kBAdobe PDFView/Open
05_contents.pdf100.43 kBAdobe PDFView/Open
06_list of tables and figures.pdf114.15 kBAdobe PDFView/Open
07_chapter1.pdf265.15 kBAdobe PDFView/Open
08_chapter2.pdf257.47 kBAdobe PDFView/Open
09_chapter3.pdf242.66 kBAdobe PDFView/Open
10_chapter4.pdf227.43 kBAdobe PDFView/Open
11_chapter5.pdf238.46 kBAdobe PDFView/Open
12_conclussion.pdf79.48 kBAdobe PDFView/Open
13_publications.pdf100.78 kBAdobe PDFView/Open


Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.