Graph clustering using k-Neighbourhood Attribute Structural similarity

被引:26
作者
Boobalan, M. Parimala [1 ]
Lopez, Daphne [1 ]
Gao, X. Z. [2 ]
机构
[1] VIT Univ, Sch Informat Technol & Engn, Vellore 632014, Tamil Nadu, India
[2] Aalto Univ, Sch Elect Engn, Otaniementie 17, Aalto 00076, Finland
关键词
Clustering; graph; k-Neighbourhood; Structural; Attribute similarity; COMMUNITY STRUCTURE;
D O I
10.1016/j.asoc.2016.05.028
中图分类号
TP18 [人工智能理论];
学科分类号
140502 [人工智能];
摘要
A simple and novel approach to identify the clusters based on structural and attribute similarity in graph network is proposed which is a fundamental task in community detection. We identify the dense nodes using Local Outlier Factor (LOF) approach that measures the degree of outlierness, forms a basic intuition for generating the initial core nodes for the clusters. Structural Similarity is identified using k-neighbourhood and Attribute similarity is estimated through Similarity Score among the nodes in the group of structural clusters. An objective function is defined to have quick convergence in the proposed algorithm. Through extensive experiments on dataset (DBLP) with varying sizes, we demonstrate the effectiveness and efficiency of our proposed algorithm k-Neighbourhood Attribute Structural (kNAS) over state-of-the-art methods which attempt to partition the graph based on structural and attribute similarity in field of community detection. Additionally, we find the qualitative and quantitative benefit of combining both the similarities in graph. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码:216 / 223
页数:8
相关论文
共 37 条
[1]
Aggarwal CC, 2010, ADV DATABASE SYST, V40, P275, DOI 10.1007/978-1-4419-6045-0_9
[2]
Arthur D, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1027
[3]
Ball G.H., 1967, PROMENADE OUTLINE PA
[4]
Brandes U, 2003, LECT NOTES COMPUT SC, V2832, P568
[5]
LOF: Identifying density-based local outliers [J].
Breunig, MM ;
Kriegel, HP ;
Ng, RT ;
Sander, J .
SIGMOD RECORD, 2000, 29 (02) :93-104
[6]
SPARCL: an effective and efficient algorithm for mining arbitrary shape-based clusters [J].
Chaoji, Vineet ;
Al Hasan, Mohammad ;
Salem, Saeed ;
Zaki, Mohammed J. .
KNOWLEDGE AND INFORMATION SYSTEMS, 2009, 21 (02) :201-229
[7]
Community structure of the physical review citation network [J].
Chen, P. ;
Redner, S. .
JOURNAL OF INFORMETRICS, 2010, 4 (03) :278-290
[8]
Clustering Large Attributed Graphs: A Balance between Structural and Attribute Similarities [J].
Cheng, Hong ;
Zhou, Yang ;
Yu, Jeffrey Xu .
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA, 2011, 5 (02)
[9]
Clauset A, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.066111
[10]
Dongen Stijn, 2000, A cluster algorithm for graphs