ESYN：基于动态模型的高效同步聚类算法

doi:10.3969/j.issn.1000-436x.2014.z2.012

Abstract

Abstract:

Clustering is an important research field in data mining.Based on dynamical synchronization model,an efficient synchronization clustering algorithm ESYN is proposed.Firstly,based on local structure information of a non-vector network,a new concept vertex similarity is brought up to describe the link density between vertices.Secondly,the network is vectoried by OPTICS algorithm and turned into one-dimensional coordination sequence.Finally,global coupling analysis is applied to generalized Kuramoto synchronization model,synchronization radius is increased and the optimal clustering result is automatically selected.The experimental results on a large number of synthetic and real-world networks show that proposed algorithm achieves high accuracy.

Key words: clustering, synchronization model, vectorization, modularity

Xue-wen DONG,Chao YANG,Li-jie SHENG,Jian-feng MA. ESYN:efficient synchronization clustering algorithm based on dynamic synchronization model[J]. Journal on Communications, 2014, 35(Z2): 86-93.

Figures/Tables 4

符号	说明
D	网络数据集
N	网络节点数
x	数据集D中一个节点
l_x	节点x映射后的坐标
l_x(t)	时间t时节点x的坐标
ε	同步半径
τ(x)	节点x的邻域，包含x和x的邻居节点
dist(x,y)	节点x,y之间的距离
degree(x)	节点x的度
N_ε(x)	节点x的ε-邻域
$D_{ε}^{t}$	当同步半径为ε，时间为t时的数据集
$C_{ε}^{t}$	当同步半径为ε，时间为t时的聚类结果
$Q_{ε}^{t}$	当同步半径为ε，时间为t时的模块度

References 7

[8]	NEWMAN M . Detecting community structure in networks[J]. The European Physical Journal B-Condensed Matter and Complex System, 2004,38(2): 321-330.
[9]	DEKKER A H , TAYLOR R . Synchronization properties of trees in the Kuramoto model[J]. SIAM Journal on Applied Dynamical Systems, 2013,12(2): 596-617.
[10]	B?HM C , PLANT C , SHAO J ,et al. Clustering by synchronization[A]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. 2010. 583-592.
[11]	黄健斌, 白杨, 康剑梅 ,等. 一种基于同步动力学模型的网络社团发现方法[J]. 计算机研究与发展, 2012,49(10): 2198-2207. HUANG J B , BAI Y , KANG J M ,et al. A network community detection method based on dynamic model of synchronization[J]. Journal of Computer Research and Development, 2012,49(10): 2198-2207.
[12]	ANKERST M , BREUNIG M M , KRIEGEL H P ,et al. OPTICS:orderingpoints to identify the clustering structure[J]. ACM SIGMOD Record, 1999,28(2): 49-60.
[13]	KITSAK M , GALLOS L K , HAVLIN S ,et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010,6(11): 888-893.
[14]	BRYAN K , LEISE T . The $25,000,000,000 eigenvector:The linear algebrabehind Google[J]. Siam Review, 2006,48(3): 569-581.
[15]	GIRVAN M , NEWMAN E . Community structure in social and biologicalnetworks[J]. PNAS, 2002,99(12): 7821-7826.
[16]	ZACHARY W W . An informationflow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977,33(4): 452-473.
[17]	VINH N X , EPPS J , BAILEY J . Information theoretic measures for clusterings comparison:is a correction for chance necessary[A]. Proceedings of the 26th Annual International Conference on Machine Learning[C]. ACM, 2009. 1073-1080.
[1]	GUAN J , GAN Y , WANG H . Discovering pattern-based subspace clusters by pattern tree[J]. Knowledge-Based Systems, 2009,22(8): 569-579.
[2]	ZHU S , WANG D , LI T . Data clustering with size constraints[J]. Knowledge-Based Systems, 2010,23(8): 883-889.
[3]	ESTER M , KRIEGEL H P , SANDER J ,et al. A density-based algorithmfor discovering clusters in large spatial databases with noise[A]. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining[C]. 1996. 226-231.
[4]	KARYPIS G , HAN E H , KUMAR V . Chameleon:hierarchical clusteringusing dynamic modeling[J]. Computer, 1999,32(8): 68-75.
[5]	NEWMAN M E , GIRVAN M . Finding and evaluating community structurein networks[J]. Physical review E, 2004,69(2):026113.
[6]	CLAUSET A , NEWMAN M E , Moore C . Finding community structure invery large networks[J]. Physical review E, 2004,70(6): 6111-6116.
[7]	LEUNG I X , HUI P , LIO P ,et al. Towards real-time communitydetection in large networks[J]. Physical Review E, 2009,79(6): 6107-6117.

Metrics

Recommended 0

No Suggested Reading articles found!

真实网络	ESYN	SYN	LHLC	FastModularity
College-Football	0.92	0.89	0.32	0.23
Zachary’s Karate	1	1	0.42	0.75

ESYN:efficient synchronization clustering algorithm based on dynamic synchronization model

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 7

Related Articles 15

Metrics

Recommended 0

[1]	Yu DONG, Youpeng ZHANG. Conflict evidence combination method based on clustering weighting [J]. Journal on Communications, 2023, 44(3): 157-163.
[2]	Jing ZHAO, Jun LI, Chun LONG, Wei WAN, Jinxia WEI, Kai CHEN. Unsupervised detection method of RoQ covert attacks based on multilayer features [J]. Journal on Communications, 2022, 43(9): 224-239.
[3]	Ao LI, Cong FENG, Yutong NIU, Shibiao XU, Yingtao ZHANG, Guanglu SUN. Multiview clustering method for view-unaligned data [J]. Journal on Communications, 2022, 43(7): 143-152.
[4]	Rong QIAN, Jianting XU, Kejun ZHANG, Hongyu DONG, Fangyuan XING. Research on HMM based link prediction method in heterogeneous network [J]. Journal on Communications, 2022, 43(5): 214-225.
[5]	Yimin MAO, Dejin GAN, Liefa LIAO, Zhigang CHEN. Parallel division clustering algorithm based on Spark framework and ASPSO [J]. Journal on Communications, 2022, 43(3): 148-163.
[6]	Jingge FENG, Yeping HE, Qiuming TAO. Auto-vectorization: recent development and prospect [J]. Journal on Communications, 2022, 43(3): 180-195.
[7]	Zhongping ZHANG, Sen LI, Weixiong LIU, Shuxia LIU. Outlier detection algorithm based on fast density peak clustering outlier factor [J]. Journal on Communications, 2022, 43(10): 186-195.
[8]	Huiqin WANG, Wenbin HOU, Qingbin PENG, Minghua CAO, Rui HUANG, Ling LIU. Step-by-step classification detection algorithm of SPPM based on K-means clustering [J]. Journal on Communications, 2022, 43(1): 161-171.
[9]	Qiang HU, Jiaji SHEN, Guanghui JING, Junwei DU. Service clustering method based on description context feature words and improved GSDMM model [J]. Journal on Communications, 2021, 42(8): 176-187.
[10]	Chunfu JIA, Ruiqi LI, Yafei WANG. Privacy protection scheme of DBSCAN clustering based on homomorphic encryption [J]. Journal on Communications, 2021, 42(2): 1-11.
[11]	Liu LIU, Jianhua ZHANG, Yuanyuan FAN, Li YU, Jiachi ZHANG. Survey of application of machine learning in wireless channel modeling [J]. Journal on Communications, 2021, 42(2): 134-153.
[12]	Ao LI, Zhuo WANG, Xiaoyang YU, Deyun CHEN, Yingtao ZHANG, Guanglu SUN. Robust multiview subspace clustering method based on multi-kernel low-redundancy representation learning [J]. Journal on Communications, 2021, 42(11): 193-204.
[13]	Ruizhang HUANG,Ruina BAI,Yanping CHEN,Yongbin QIN,Xinyu CHENG,Youliang TIAN. CMDC:an iterative algorithm for complementary multi-view document clustering [J]. Journal on Communications, 2020, 41(8): 155-164.
[14]	Feiyue QIU,Bowen CHEN,Tieming CHEN,Guodao ZHANG. Sparsity induced convex nonnegative matrix factorization algorithm with manifold regularization [J]. Journal on Communications, 2020, 41(5): 84-95.
[15]	Xiaofei WANG,Fankui HU,Shuo HUANG. Infrared image segmentation algorithm based on distribution information intuitionistic fuzzy c-means clustering [J]. Journal on Communications, 2020, 41(5): 120-129.