A New Algorithm for Personalized Recommendations in Community Networks
In a graph theory model, clustering is the process of division of vertices in groups, with a higher density of edges in groups than among them. In this paper, we introduce a new clustering algorithm for detecting such groups; we use it to analyze some cla
- PDF / 1,734,473 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 49 Downloads / 170 Views
Abstract In a graph theory model, clustering is the process of division of vertices in groups, with a higher density of edges in groups than among them. In this paper, we introduce a new clustering algorithm for detecting such groups; we use it to analyze some classic social networks. The new algorithm has two distinguished features: non-binary hierarchical tree and the feature of overlapping clustering. A non-binary hierarchical tree is much smaller than the binary-trees constructed by most traditional algorithms; it clearly highlights meaningful clusters which significantly reduce further manual efforts for cluster selections. The present algorithm is tested by several bench mark data sets for which the community structure was known in advance and the results indicate that it is a sensitive and accurate algorithm for extracting community structure from social networks. Keywords Clustering
Graph theory Hierarchical tree Social network
X. Zhou China Information Technology Security Evaluation Center, Beijing, China e-mail: [email protected] X. Xing Y. Liu (&) School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China e-mail: [email protected] X. Xing e-mail: [email protected] X. Xing Y. Liu Key Laboratory of Communication and Information Systems, Beijing Municipal Commission of Education, Beijing Jiaotong University, Beijing 100044, China
Y.-M. Huang et al. (eds.), Advanced Technologies, Embedded and Multimedia for Human-centric Computing, Lecture Notes in Electrical Engineering 260, DOI: 10.1007/978-94-007-7262-5_86, Ó Springer Science+Business Media Dordrecht 2014
763
764
X. Zhou et al.
Introduction Clustering is an important task for the discovery of community structures in networks. Its goal is to sort cases (people, things, events, etc.) into clusters so that the degree of association is relatively strong between members of the same cluster and relatively weak between members of different clusters. Webster [1] defines cluster analysis as ‘‘a statistical classification technique for discovering whether the individuals of a population fall into different groups by making quantitative comparisons of multiple characteristics’’. Various clustering algorithms have been proposed in the literature in many different scientific disciplines. Jain [2] broadly divided these algorithms into two groups: (1) hierarchical algorithm and (2) partitional algorithm. Hierarchical clustering algorithms recursively find nested clusters either in agglomerative mode or in divisive mode. The most well-known hierarchical algorithms are single-link and complete-link; in single-link hierarchical clustering, the two clusters whose two closest members have the smallest distance are merged in each step; in complete-link case, the two clusters whose merger has the smallest diameter are merged in each step. Compared to hierarchical clustering algorithms, partitional clustering algorithms find all the clusters simultaneously as a partition of the data and do not impose a hierarchica
Data Loading...
