基于Laplace矩阵Jordan型的复杂网络聚类算法

doi:10.3969/j.issn.1000-436x.2014.03.002

Abstract

Abstract:

Among existing clustering algorithms,the graph-Laplacian-based spectrum clustering algorithm has rigorous theoretical basis and high accuracy.However,the application of this algorithm is limited by its dependence on the prior knowledge,such as the number and the size of clusters.Based on the Jordan form of graph Laplacian,an algorithm was proposed which can obtain the prior knowledge,and perform the primary clustering based on the eigenvalues of the Jordan form.The modularity density function of clusters was defined,and an improved spectrum clustering algorithm with the help of the function and the primary clustering was proposed.The experiments were conducted on diverse datasets showing that,compared with the classic algorithms such as Fast-Newman and Girvan-Newman,the algorithm can reach a high clustering accuracy and a fast convergence rate.

Key words: complex network, clustering algorithm, Laplace-matrix, Jordan-form, prior knowledge

Jian-wei NIU,Bin DAI,Chao TONG,Guan-ying HUO,Jing PENG. Complex network clustering algorithm based on Jordan-form of Laplace-matrix[J]. Journal on Communications, 2014, 35(3): 11-21.

Figures/Tables 13

References 23

[1]	ALESSANDRO V . Complex networks:the fragility of interdependency[J]. Nature, 2010,464(7291): 984-985.
[2]	SONG C M , QU Z H , NICHOLAS B . Limits of predictability in human mobility[J]. Science, 2010,327: 1018-1021.
[3]	ALESSANDRO V . Predicting the behavior of techno-social system[J]. Science, 2009,325: 425-428.
[4]	DOU B L , LI S S , ZHANG S Y . Social network analysis based on structure[J]. Chinese Journal of Computers, 2012,35(4): 741-753.
[5]	YU L , GAO L , SUN P G . Research on algorithms for complexes and functional modules prediction in protein-protein interaction networks[J]. Chinese Journal of Computers, 2011,34(7): 1239-1251.
[6]	FLAKE G W , LAWRENCE S , GILES C L . Self-organization and identification of Web communities[J]. IEEE Computer, 2002,35(3): 66-71.
[7]	GIRVAN M , NEWMAN M E J . Community structure in social and biological networks[J]. Proc of the National Academy of Science, 2002,9(12): 7821-7826.
[8]	NEWMAN M E J . Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004,69(6): 066133.
[9]	NEWMAN M E J , GIRVAN M . Finding and evaluating community structure in networks[J]. Physical Review E, 2004,69(2): 026113.
[10]	GUIMERA R , AMARAL L A N . Functional cartography of complex metabolic networks[J]. Nature, 2005,433(7028): 895-900.
[11]	FORTUNATO S , BARTHELEMY M . Resolution limit in community detection[J]. Proc of the National Academy of Science, 2007,104(1): 36-41.
[12]	YANG B , LIU D Y , LIU J M , et al. Complex network clustering algorithms[J]. Journal of Software, 2009,20(1): 54-66.
[13]	NEWMAN M E J . Modularity and community structure in networks[J]. Proc of the National Academy of Science, 2006,103(23): 8577-8582.
[14]	SHIGA M , TAKIGAWA I , MAMITSUKA H . A spectral clustering approach to optimally combining numerical vectors with a modular network[A]. Proc of the 13th ACM SIGKDD Int'l Conf on Knowledge Discovery and Data Mining[C]. New York, 2007. 647-656.
[15]	WHITE S , SMYTH P . A spectral clustering approach to finding communities in graphs[A]. Proc of the 5th SIAM Int'l Conf on Data Mining[C]. Philadelphia: SIAM, 2005. 76-84.
[16]	DONETTI L , MUNOZ M A . Improved spectral algorithm for the detection of network communities[A]. Proc of the 8th Int'l Conf.on Modeling Cooperative Behavior in the Social Sciences[C]. New York, 2005. 104-107.
[17]	CAPOCCI A , SERVEDIO V D P , CALDARELLI G , et al. Detection communities in large networks[J]. Computer Science, 2004,3243: 181-187.
[18]	FIEDLER M . Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal, 1973,23(98): 298-305.
[19]	Supporting Website[EB/OL]. . 2012.
[20]	Supporting Website[EB/OL]. . 2012.
[21]	Supporting Website[EB/OL]. , 2011.
[22]	HANSEN L K , SALAMON P . Neural network ensembles[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1990,162(10): 993-1001.
[23]	JURE L , KEVIN J L , MICHAEL W M . Empirical comparison of algorithms for network community detection[A]. Proc of the 19th International Conference on World Wide Web[C]. North Carolina, 2010. 26-30.

Metrics

Recommended 0

No Suggested Reading articles found!

属性	数值
节点数	34
聚类系数	0.316
边数	78
直径	6
三角闭分组数	49
平均最短路径数	2.415

属性	数值
节点数	77
聚类系数	0.209
边数	254
直径	6
三角闭分组	36
平均最短路径数	3.456

属性	数值
节点数	332
聚类系数	0.301
边数	2 126
直径	3
三角闭分组数	2 453
平均最短路径数	2.333

属性	数值
节点数	297
聚类系数	0.292 4
边数	2 359
直径	5
三角闭分组数	3 241
平均最短路径数	2.455 3

Complex network clustering algorithm based on Jordan-form of Laplace-matrix

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 23

Related Articles 15

Metrics

Recommended 0

[1]	Yanfei SUN, Jiazheng YIN, Jin QI, Xiaoxuan HU, Mengting CHEN, Zhenjiang DONG. Topology control based on dynamic graph embedding in Internet of vehicles [J]. Journal on Communications, 2022, 43(6): 133-142.
[2]	Qiuyang GU, Bao WU, Renyong CHI. Link prediction method based on the similarity of high path [J]. Journal on Communications, 2021, 42(7): 61-69.
[3]	Qiuyang GU, Bao WU, Zhaoyang SUN, Renyong CHI. Key node identification algorithm for complex network based on improved grey wolf optimization [J]. Journal on Communications, 2021, 42(6): 72-83.
[4]	Tao HAN, Wei HE, Jun DAI, Yong ZUO, Yang YANG, Xiaohu GE. Connectivity analysis of IoV based on scale-free network [J]. Journal on Communications, 2021, 42(4): 100-108.
[5]	Jinkang ZHU, Mingyang CHAI, Wuyang ZHOU. Three-three-three network architecture and learning optimization mechanism for B5G/6G [J]. Journal on Communications, 2021, 42(4): 62-75.
[6]	Sheng ZHANG,Weikai DAI,Feng WU,Wenxiang LAN. Global efficiency estimation method of complex network based on fractal property [J]. Journal on Communications, 2020, 41(7): 204-212.
[7]	Yiteng WU,Hongtao YU,Ruiyang HUANG,Huawei LI. Theoretical limit of link prediction using a combination method [J]. Journal on Communications, 2020, 41(6): 34-50.
[8]	Shuxin LIU,Xing LI,Hongchang CHEN,Kai WANG. Link prediction method based on matching degree of resource transmission for complex network [J]. Journal on Communications, 2020, 41(6): 70-79.
[9]	Yingzhuo XIANG,Zhengguo XU,Ling YOU. Instruction flow mining algorithm based on the temporal sequence of node communication actions [J]. Journal on Communications, 2019, 40(9): 51-60.
[10]	Fenghua LI,Tianzhu CHEN,Zhen WANG,Linjie ZHANG,Guozhen SHI,Yunchuan GUO. Cross-network access control mechanism for complex network environment [J]. Journal on Communications, 2018, 39(2): 1-10.
[11]	Kun DENG,Wen-ping LI,Fa-hong YU,Jian-pei ZHANG. Overlapping community detection in complex networks based on multi kernel label propagation [J]. Journal on Communications, 2017, 38(2): 53-66.
[12]	HONGHong Z,HANGQing-yang Z,IANLi-chao T,ANGLiang-min W. Distributed key sharing based scheme for security clustering in unattended wireless sensor network [J]. Journal on Communications, 2015, 36(5): 31-39.
[13]	Jun LIU,Jian-zhong QIAO. Research on relevance between k-core and clustering coefficient in complex network [J]. Journal on Communications, 2015, 36(1): 224-229.
[14]	. Complex network clustering algorithm based on Jordan-form of Laplace-matrix [J]. Journal on Communications, 2014, 35(3): 2-21.
[15]	. User interest-aware content replica optimized placement algorithm [J]. Journal on Communications, 2014, 35(12): 3-27.