Voronoi Diagram-Based Geometric Approach for Social Network Analysis
Social network analysis is aimed at analyzing relationships between social network users. Such analysis aims at finding community detection, that is, group of closest people in a network. Usually, graph clustering techniques are used to identify groups. H
- PDF / 481,977 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 265 Views
Abstract Social network analysis is aimed at analyzing relationships between social network users. Such analysis aims at finding community detection, that is, group of closest people in a network. Usually, graph clustering techniques are used to identify groups. Here, we propose a computational geometric approach to analyze social network. A Voronoi diagram-based clustering algorithm is employed over embedded dataset in the Euclidean vector space to identify groups. Structure-preserving embedding technique is used to embed the social network dataset and learns a low-rank kernel matrix by means of a semi-definite program with linear constraints that captures the connectivity structure of the input graph. Keywords Social network analysis
Geometric clustering Voronoi diagram
1 Introduction Social network analysis is an interesting research area for analyzing the structure and relationships of social network users [1]. Recent works [3, 5, 7, 13] in social network analysis attempt at finding group of closest people in a network (community detection). Usually, visualization techniques are used to analyze such groups in small social networks. However, only a few groups in a social network S. Surendran (&) SCT College of Engineering, Thiruvananthapuram, Kerala, India e-mail: [email protected] D. Chitraprasad TKM College of Engineering, Kollam, Kerala, India e-mail: [email protected] M. R. Kaimal Amrita Vishwa Vidyapeetham, Amritapuri Campus, Kollam, Kerala, India e-mail: [email protected]
G. S. S. Krishnan et al. (eds.), Computational Intelligence, Cyber Security and Computational Models, Advances in Intelligent Systems and Computing 246, DOI: 10.1007/978-81-322-1680-3_39, Springer India 2014
359
360
S. Surendran et al.
are discovered using this approach. Clustering techniques are used for a large social network in identifying more groups and clusters. A social network is represented as a graph G = (V, E), where V represents vertices (nodes or actors), and E denotes edges (ties or relationship between actors). Most large-scale networks share some common patterns that are not noticeable in small networks. Among all the patterns, the well-known characteristics are as follows: scale-free distribution [8], small-world effect [9], and strong community structure [6]. In a community structure, a group of people tend to interact with each other more than those outside the group. That is, vertices in networks are often found to cluster into tightly knit groups with a high density of within-group edges and a low density of between-group edges [3]. Graph clustering methods are used to find community structure in social networks. In this paper, we propose a geometric approach to find community structure in social networks. Voronoi diagram-based geometric clustering approach is employed here for finding communities from graph. This method can give a polynomial time complexity. The rest of the paper organized as follows: In Sect. 2, we discuss related works done in this area. Problem statement is specified in Sect.
Data Loading...
