复杂网络中基于数据场的自适应聚类算法研究徐翠毕业论文答辩

1、整理ppt复杂网络中基于数据场的复杂网络中基于数据场的自适应聚类算法研究自适应聚类算法研究答答 辩辩 人人: : 指导老师指导老师: : 刘玉华刘玉华 教授教授答辩时间：答辩时间：整理ppt目目 录录研究背景与意义1基于数据场的自适应聚类算法实现2基于数据场的多目标自适应聚类算法实现3结论与展望4整理ppt研究背景与意义研究背景与意义(1/3)(1/3)图论图论随机图理论随机图理论复杂网络复杂网络n复杂网络发展史复杂网络发展史n复杂网络簇结构复杂网络簇结构 l 簇内的节点边的连接相互紧密，簇之间节点边的连接稀疏n发现网络簇结构的意义发现网络簇结构的意义当网络复杂化大规模化，我们就很难通过肉眼识

2、别出网络的簇结构，更难预测其行为和功能网络簇结构的研究在社会学中的社区探测、生物学中新陈代谢功能的理解、互联网各大功能的区分等领域有着广泛的应用计算机学院计算机学院整理ppt研究背景与意义研究背景与意义(2/3)(2/3)n 复杂网络聚类算法分析复杂网络聚类算法分析图2.1复杂网络中划分簇结构的聚类算法分类示意图整理pptn本文研究内容本文研究内容l提出节点的重要性因子的概念l构造聚类评价函数l引入数据场拓扑势划分簇l引入节点的相似度概念l构造多目标聚类评价函数 研究背景与意义研究背景与意义(3/3)(3/3)整理ppt 基于数据场的自适应聚类算法实现基于数据场的自适应聚类算法实现(1/6)(

3、1/6)n 算法思想算法思想l指出网络中心节点的评价指标适用于聚类算法中初始节点的选择，提出了节点重要性因子的概念l利用物理场拓扑势和k-means算法的思想成簇l通过构造合适的聚类评价函数来实现算法的自适应性，解决初始簇结构个数难以抉择的问题整理ppt基于数据场的自适应聚类算法实现基于数据场的自适应聚类算法实现(2/6)(2/6)n 节点的重要性因子节点的重要性因子n 聚类评价函数的构建聚类评价函数的构建l簇内相似度(Similarity Within Clusters) ( )( )( )( )CDIiCi CiC i2( )( )11( )inkiiwjijSkxcl 簇间相似度(Sim

4、ilarity Between Clusters) 22( )( )( )(1)11kkijSkccbk kiji l聚类评价函数( )/ (k 1)( )( )/ (nk)bbwwSkSkSk( )( )1Dd iCin1(1)( )nCijjnCidlog ( )log ( ),( , )0d id jiI i j与j直接相连其他1( , )( )(1)log(1)njII i jC inn度中心化度中心化紧密度紧密度中心化中心化互信息互信息中心化中心化整理ppt基于数据场的自适应聚类算法实现基于数据场的自适应聚类算法实现(3/6)(3/6)n 数据场和势数据场和势l定义1 场强函数。在数

5、据场中，空间中共有n个对象，令x代表对象所处位置，则在该数据场中x处对象xi 所产生的势为： 2( )ixxxiixmel定义2势函数。数据场是具有叠加性的，因此，任意数据对象vjV 的拓扑势可定义为：21( )( )ixxnnxiiiiF xxme整理ppt基于数据场的自适应聚类算法实现基于数据场的自适应聚类算法实现(4/6)(4/6)n算法实现流程算法实现流程 按照上面的思想对算法进行实现，可以分为7个步骤，其流程图如右图所示图3.3 本算法流程图 表3-2 本算法与GN算法复杂度比较算法 复杂度说明 GN 算法m为边数，n为节点数 本算法n为节点个数 2()O mn2()O n整理ppt

6、基于数据场的自适应聚类算法实现基于数据场的自适应聚类算法实现(5/6)(5/6)图3.7 本算法与GN算法准确度的曲线图分析仿真结果可以发现，整体来看，本算法的准确度优于GN算法，且稳定性更好。 n仿真结果仿真结果l算法准确性评估+=16inoutZZ整理pptn仿真结果仿真结果l算法有效性评估基于数据场的自适应聚类算法实现基于数据场的自适应聚类算法实现(6/6)(6/6)图3.5 Zachary空手道俱乐部成员关系网络图 3.6 基于GN算法的聚类结果图3.7 基于本文算法的聚类结果整理ppt基于数据场的多目标自适应聚类算法实现基于数据场的多目标自适应聚类算法实现(1/6)(1/6)n 算法

7、思想算法思想l引入节点相似度概念来发现核心外围结构的网络簇结构的中心节点l利用物理场和k-means算法的思想划分簇l构造多目标评价函数以发现不同网络的拓扑结构，且对各种聚类评价函数进行一个综合考量整理pptn 节点相似度的选取节点相似度的选取基于数据场的多目标自适应聚类算法实现基于数据场的多目标自适应聚类算法实现(2/6)(2/6)( )( )( , )( )( )SauvSu vuv n 簇中心节点的选取簇中心节点的选取( )(i, j)sai coreS jSn 多目标聚类函数的构造多目标聚类函数的构造221111( )( )( )2211(2)1(c)1(c 1)(3)(c)(c 1)

8、ccssccciiccbwbwmmd id ix iQQmmmmxMinMaxCutMinMaxCutxSS(c)max(1)(2)(3),(1)(2),(1)(3),(2)(3)cccccccccFfffffffff1,( )0( ),1,2,30,ccif x ist f iiotherwise 当c=1时，规定 。(1)0F集合中元集合中元素的个数素的个数节点节点u的邻的邻居节点集合居节点集合整理ppt基于数据场的多目标自适应聚类算法实现基于数据场的多目标自适应聚类算法实现(3/6)(3/6)n 算法步骤算法步骤Step1 设 core = c1(聚类中心节点集合，c1为网络中度最大的节

9、点)， V1=V - core (聚类中心以外的节点集合)，c=2 ；Step2 若|core|c， V2=V1 ，转 Step3；否则，转 Step4；Step3 若V2，则选择节点集合V2中度最大的节点c1 ，V2=V1-c1，对于 任何vcore，计算S(c1, v) 的值，若S(c1, v)且S(c1) ，则将c1作 为一个聚类中心：core=core c1 ，V1=V1 - c1，否则转Step7；整理ppt基于数据场的多目标自适应聚类算法实现基于数据场的多目标自适应聚类算法实现(4/6)(4/6)Step4 计算集合core中c个节点对集合V1中节点i的影响度，若存在两个中心节点对

10、某节点i的影响度值相等或小于，则将该节点i加入到 Temp集中，否则将节点i加入影响度值最大的中心节点j所在的簇中； Step5 若Temp ，计算与节点i (i Temp )相连的d(i) (d(i)为节点的度数)个节点与集合core中c个节点的势函数之和，并将节点i 加入到势值影响最大的core中的节点所在的簇中；Step6 计算当前簇划分下的聚类评价函数 F(c)值，c=c+1 ，转Step2；Step7 选择 F(c)值最大时的簇拓扑结构输出，算法结束。n 算法步骤算法步骤整理pptl空手道俱乐部网络结果图4.3 本算法对空手道俱乐部网络的划分结果示意图l宽吻海豚家族网络图4.4 宽吻

11、海豚家族网络拓扑结构图基于数据场的多目标自适应聚类算法实现基于数据场的多目标自适应聚类算法实现(5/6)(5/6)n 实验结果分析实验结果分析整理pptn 实验结果分析实验结果分析图4.5 本算法对宽吻海豚网络的划分结果图4.6 GN算法对宽吻海豚网络划分为4个簇结构的结果基于数据场的多目标自适应聚类算法实现基于数据场的多目标自适应聚类算法实现(6/6)(6/6)整理pptn文章小结文章小结l指出网络中心节点的评价指标适用于聚类算法中初始节点的选择，提出了节点重要性因子的概念l引入了节点相似度的概念来挖掘更适合的簇中心节点l通过构造合适的聚类评价函数来实现算法的自适应性，解决初始簇结构个数难以

12、抉择的问题l利用物理场拓扑势和k-means算法的思想成簇提出了一种新的聚类算法。总结与展望总结与展望n 工作展望工作展望l 研究有权有向的复杂网络聚类l 发现重叠的簇结构l 尽可能多的考虑节点的属性整理ppt在校期间发表论文在校期间发表论文n发表论文：发表论文：lYuhua Liu, Cui Xu, Ke Xu, Jianzhi Jin. An Improved Clustering Method Based on Data Field. 2013 2nd International Conference on Advanced in Control Engineering and Info

13、rmation Science(CACE-13), atlantis, Hongkong, China, October 12-13, 2013. (EI收录)lCui Xu, Yuhua Liu, Kaihua Xu and Ke Xu. An Adaptive Clustering Algorithm Based on Data Field in Complex Networks. 2013 Third IEEE International Conference on Information Science and Technology(ICIST 2013), IEEE, Yangzho

14、u, China, March 23-25, 2013. (EI收录)lKe Xu, Yuhua Liu, Cui Xu, Kaihua Xu. A Cluster-based and Range free MDS-MAP Location Scheme in WSN. 3rd International Conference on Computer Engnieering and Network(CENet 2013), Springer, Shanghai, China, July 20-21, 2013. (EI收录)lDi Zhang, Yuhua Liu, Cui Xu and Yo

15、ngqiang Qi. One OCDMA PON System with 2D Multi-Length Two-Weight CHPCs. Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation(ISCCCA-13), atlantis, Taiyuan, China, April 6-7, 2013. (EI收录)lYuhua Liu, Zhenrong Luo, Ke Xu and Cui Xu. The Research of Routing A

16、lgorithm Based on Shortest Path Tree in WSNs. 2013 International Conference on Computer Science, Electronic Technology and Intelligent System(CSETIS 2013), atlantis, Hangzhou, China, March 22-23, 2013. (EI收录)lYuhua Liu, Jianzhi Jin, Yi Zhang and Cui Xu. A New Clustering Algorithm Based on Data Field in Complex Networks. The Journal of Supercomputing, Springer, Vol. 67, No. 3, March, 2014, pp.723-737. (SCI收录)l刘玉华, 张翼, 徐翠徐翠, 晋建志. 一种基于数据场的复杂网络聚类算法. 计算机科学. 2013, 40(11):70-73.l刘玉华, 郑梅容,许凯华, 徐翠徐翠. 基于耦合系数的无标度网络模型 (BA-S)的中心化研究. 计算机科