Computer Science ›› 2018, Vol. 45 ›› Issue (1): 292-296.doi: 10.11896/j.issn.1002-137X.2018.01.051

Previous Articles     Next Articles

Density Clustering Algorithm Based on Laplacian Centrality

YANG Xu-hua, ZHU Qin-peng and TONG Chang-fei   

  • Online:2018-01-15 Published:2018-11-13

Abstract: As an important tool of data mining,clustering analysis can measure similarity between the different data and classify them into different categories.It is wisely applied in pattern recognition,economics,biology and so on.In this paper,a new clustering algorithm was proposed.Firstly,dataset to be classified is converted into a weighted complete graph.Data point is a node and the distance between two data points is used as weight of side between these two data points.Secondly,local importance of each node in the network is calculated and evaluated by Laplacian centrality.The cluster center has higher Laplacian centrality than surrounding neighbor nodes and the node with higher Laplacian centrality has larger distance.Finally,the algorithm is a real parameter-free clustering method,which can classify the dataset automatically without any priori parameters.In this article,the new algorithm was compared with 9 famous clustering algorithms in 6 datasets.Experimental results show that the proposed algorithm has good clustering performance.

Key words: Weighted complete graph,Laplacian centrality,Density clustering

[1] GONDY L A,THOMAS C R B,BAYES N.Programs for machine learning[J].Advances in Neural Information Processing Systems,1993,9(2):937-944.
[2] SUN J G,LIU J,ZHAO L Y.Research on clustering algorithm [J].Journal of Software,2008,19(1):48-61.(in Chinese) 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.
[3] HE L,WU L D,CAI Y C.A survey of clustering algorithms in data mining [J].Application Research of Computers,2007,24(1):10-13.(in Chinese) 贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究,2007,4(1):10-13.
[4] ZARE H Z,MOHAMMADZADEH M.Knowledge discoveryfrom patients’ behavior via clustering-classification algorithms based on weighted eRFM and CLV model:An empirical study in public health care services[J].Iranian Journal of Pharmaceutical Research Ijpr,2016,15(1):355-367.
[5] TANG Y,ZHONG N J,FAN J.An improved recommendation algorithm based on user rating information[J].Computer Scien-ce,2016,43(9):111-115.(in Chinese) 汤颖,钟南江,范菁.一种结合用户评分信息的改进好友推荐算法[J].计算机科学,2016,3(9):111-115.
[6] HE B,DING Y,TANG J,et al(1)Mining diversity subgraph in multidisciplinary scientific coll aboration networks:A meso perspective[J].Journal of Informetrics,2013,7(1):117-128.
[7] MACQUEEN J,LECAM,LUCIEN M.Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability[M].University of California Press,1967:281-297.
[8] HAN X,LIU S F,XU T Q.An improved K-medoids algorithm based on genetic simulated annealing algorithm [J].Journal of Jilin University (Engineering),2015,45(2):619-623.(in Chinese) 韩啸,刘淑芬,徐天琦.基于遗传模拟退火算法的改进K-medoids算法[J].吉林大学学报(工),2015,45(2):619-623.
[9] ARTHUR D,VASSILVITSKII S.k-means++:the advantages of careful seeding[C]∥Eighteenth Acm-Siam Symposium on Discrete Algorithms(SODA 2007).New Orl eans,Louisiana,USA,2007:1027-1035.
[10] SIMOUDIS E,HAN J,FAYYAD U,et al(1)Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining[M].AAAI Press,1996:226-231.
[11] ZHANG T,RAMAKRISHNAN R,LIVNY M.BIRCH:A New Data Clustering Algorithm and Its Applications[J].Data Mining & Knowledge Discovery,1997,1(2):141-182.
[12] XIANG L M,ZHOU W B,ZHONG Y.Based on Gauss Process of improved CLIQUE algorithm [J].Computer Application,2015,35(S2):85-87.(in Chinese) 向柳明,周渭博,钟勇.基于高斯过程的CLIQUE改进算法[J].计算机应用,2015,35(S2):85-87.
[13] RODRIGUEZ A,LAIO A.Machine learning.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[14] ZHOU L,PEI C.Delta-density based clustering with a divide-and-conquer strategy:3DC clustering[J].Pattern Recognition Letters,2016,73(C):52-59.
[15] CHEN Y,ZHAO P,LI P,et al.Finding Communities by Their Centers[J].Scientific Reports,2016,6:24017.
[16] LI Y,JIA C,YU J.A parameter-free community detection me-thod based on centrality and dispersion of nodes in complex networks[J].Physica A Statistical Mechanics & Its Applications,2015,438:321-334.
[17] NEWMAN M E.Analysis of weighted networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,70(2):056131.
[18] CIMINI G,SQUARTINI T,GABRIELLI A,et al.Estimatingtopological properties of weighted networks from limited information[J].Physical Review E Statistical Physics Plasmas Fluids &Related Interdisciplinary Topics,2015,92(4-1):040802.
[19] ZHAO X W,LIANG J Y.A hybrid data attribute weighted clustering algorithm based on the information entropy [J].Journal of Computer Research and Development,2016,53(5):1018-1028.(in Chinese) 赵兴旺,梁吉业.一种基于信息熵的混合数据属性加权聚类算法[J].计算机研究与发展,2016,53(5):1018-1028.
[20] QI X,FULLER E,LUO R,et al.A novel centrality method for weighted networks based on the Kirchhoff polynomial[J].Pattern Recognition Letters,2015,58(C):51-60.
[21] QI X,FULLER E,WU Q,et al.Laplacian centrality:A new centrality measure for weighted networks[J].Information Scien-ces,2012,194(5):240-253.
[22] ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[23] FU L,MEDICO E.FLAME,a novel fuzzy clustering method for the analysis of DNA microarray data[J].BMC Bioinfor Matics ,2007,8(1):3.
[24] WIWIE C,BAUMBACH J,RTTGER R.Comparing the performance of biomedical clustering methods[J].Nature Methods,2015,12(11):1033.
[25] HUANG D C,QIAN C K.Based on dimension attribute distance mixed attribute affinity propagation clustering algorithm [J].Computer Science,2015,42(Z11):55-57.(in Chinese) 黄德才,钱潮恺.基于维度属性距离的混合属性近邻传播聚类算法[J].计算机科学,2015,42(Z11):55-57.
[26] NAVARRO J,FRENK C,WHITE S M.A Universal Density Profile from Hierarchical Clustering[J].Astrophysical Journal,2009,490(2):493-508.
[27] DING J,SHAH S,CONDON A.densityCut:an efficient andversatile topological approach for automatic clustering of biologi-cal data[J].Bioinformatics,2016,2(17):2567-2576.
[28] WANG Y L,CHEN B,WANG X L,et al.Improved adaptivespectral clustering algorithm based on density adjustment [J].Control and Decision,2014(9):1683-1687.(in Chinese) 王雅琳,陈斌,王晓丽,等.基于密度调整的改进自适应谱聚类算法[J].控制与决策,2014(9):1683-1687.
[29] BADER G D,HOGUE C W.An automated method for finding molecular complexes in large protein interaction networks[J].BMC Bioinformatics,2003,4(1):2.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .