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

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

通信学报 ›› 2014, Vol. 35 ›› Issue (3): 11-21.doi: 10.3969/j.issn.1000-436x.2014.03.002

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

牛建伟,戴彬,童超,霍冠英,彭井

北京航空航天大学虚拟现实技术与系统国家重点实验室，北京 100191

出版日期:2014-03-25 发布日期:2017-08-17
基金资助:
国家重点基础研究发展计划（“973”计划）基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;北京市自然科学基金资助项目

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

Jian-wei NIU,Bin DAI,Chao TONG,Guan-ying HUO,Jing PENG

State Key Laboratory of Virtual Reality Technology and Systems,Beihang University,Beijing 100191

Online:2014-03-25 Published:2017-08-17
Supported by:
The National Basic Research Program of China (973 Program);The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National High Technology Research and Development Program of China (863 Program);The National High Technology Research and Development Program of China (863 Program);The Natural Science Foundation of Beijing

摘要/Abstract

摘要：

在目前复杂网络聚类算法中，基于 Laplace 特征值的谱聚类方法具有严密的数学理论和较高的精度，但受限于该方法对簇结构数量、规模等先验知识的依赖，难以实际应用。针对这一问题，基于Laplace矩阵的Jordan型变换，提出了一种先验知识的自动获取方法，实现了基于Jordan矩阵特征向量的初始划分。基于Jordan型特征值定义了簇结构的模块化密度函数，并使用该函数和初始划分结果完成了高精度聚类算法。该算法在多个数据集中的实验结果表明，与目前主流的Fast-Newman算法、Girvan-Newman算法相比，基于Laplace矩阵Jordan型聚类算法在不依赖先验知识的情况下，实现了更高的聚类精度，验证了先验知识获取方法的有效性和合理性。

关键词: 复杂网络, 聚类算法, Laplace矩阵, Jordan型, 先验知识获取

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

牛建伟,戴彬,童超,霍冠英,彭井. 基于Laplace矩阵Jordan型的复杂网络聚类算法[J]. 通信学报, 2014, 35(3): 11-21.

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.

图/表 13

图1

图2

图3

图4

表1

图5

图6

表2

图7

表3

图8

表4

图9

参考文献 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.

属性	数值
节点数	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

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

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

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 23

相关文章 15

Metrics

推荐阅读 0

[1]	孙雁飞, 尹嘉峥, 亓晋, 胡筱旋, 陈梦婷, 董振江. 基于动态图嵌入的车联网拓扑控制[J]. 通信学报, 2022, 43(6): 133-142.
[2]	顾秋阳, 吴宝, 池仁勇. 基于高阶路径相似度的复杂网络链路预测方法[J]. 通信学报, 2021, 42(7): 61-69.
[3]	顾秋阳, 吴宝, 孙兆洋, 池仁勇. 基于改进灰狼优化的复杂网络重要节点识别算法[J]. 通信学报, 2021, 42(6): 72-83.
[4]	朱近康, 柴名扬, 周武旸. 面向B5G/6G的三三三网络体系架构和优化学习机制[J]. 通信学报, 2021, 42(4): 62-75.
[5]	韩涛, 贺威, 代俊, 左勇, 杨旸, 葛晓虎. 基于无标度网络的车联网连通性研究[J]. 通信学报, 2021, 42(4): 100-108.
[6]	张胜,戴维凯,吴锋,蓝文祥. 基于分形特性的复杂网络全局效率估计方法[J]. 通信学报, 2020, 41(7): 204-212.
[7]	吴翼腾,于洪涛,黄瑞阳,李华巍. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020, 41(6): 34-50.
[8]	刘树新,李星,陈鸿昶,王凯. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020, 41(6): 70-79.
[9]	项英倬,徐正国,游凌. 基于节点通信行为时序的指控信息流挖掘算法[J]. 通信学报, 2019, 40(9): 51-60.
[10]	李凤华,陈天柱,王震,张林杰,史国振,郭云川. 复杂网络环境下跨网访问控制机制[J]. 通信学报, 2018, 39(2): 1-10.
[11]	邓琨,李文平,余法红,张健沛. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017, 38(2): 53-66.
[12]	张洛什,王大伟,薛一波. 基于流感知的复杂网络应用识别模型[J]. 通信学报, 2015, 36(3): 161-169.
[13]	刘君,乔建志. 复杂网络中k-核与网络聚集系数的关联性研究[J]. 通信学报, 2015, 36(1): 224-229.
[14]	牛建伟，戴彬，童超，霍冠英，彭井. 基于Laplace矩阵Jordan型的复杂网络聚类算法[J]. 通信学报, 2014, 35(3): 2-21.
[15]	阳小龙，王欣欣，张敏，隆克平，黄琼. 用户兴趣感知的内容副本优化放置算法[J]. 通信学报, 2014, 35(12): 3-27.