A computational geometric approach for overlapping community (cover) detection in social network

Real networks are composed of communities of varying dimensions. The identification of groups forms a significant tool in analyzing the structural and functional characteristics of complex networks. It finds application in diverse domains such as biology, web mining, social sciences etc. Discovering communities in large scale networks provide a summarized representation of the whole network, thus it becomes easy to visualize and interpret. In actual scenario, a node may belong to more than one community, i.e. the communities in the network can overlap. The cover detection aims at identifying such nodes based on graph topology information. The proposed work performs cover detection by following a computational geometry and fuzzy approach. Computational geometric techniques employed discovers clusters of nodes and then fuzzy function is defined for obtaining the covers. The curse of dimensionality is a major challenge in data clustering. For processing, the huge graph data can be viewed in the form of sparse matrix. The data on a reduced dimension space can be clustered with less effort and cost preferred to actual dimension. Here the Laplacian Eigenmap method is used for performing dimensionality reduction. The clustering algorithm should be carefully chosen depending upon the nature of requirement. A new height balanced tree called Cluster Tree (C-Tree) is introduced here for clustering. The quality of clusters generated is evaluated using modularity measurement. The resultant clusters are then analyzed using fuzzy approach for the detection of covers. This work focus only on undirected graphs, later it can be extended to work for directed graphs.