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

复杂网络中基于数据场的自适应聚类算法研究 答辩人 指导老师 刘玉华教授答辩时间 计算机学院 目录 研究背景与意义 1 3 复杂网络发展史 复杂网络簇结构簇内的节点边的连接相互紧密 簇之间节点边的连接稀疏 发现网络簇结构的意义当网络复杂化大规模化 我们就很难通过肉眼识别出网络的簇结构 更难预测其行为和功能网络簇结构的研究在社会学中的社区探测 生物学中新陈代谢功能的理解 互联网各大功能的区分等领域有着广泛的应用 计算机学院 计算机学院 研究背景与意义 2 3 复杂网络聚类算法分析 图2 1复杂网络中划分簇结构的聚类算法分类示意图 计算机学院 本文研究内容提出节点的重要性因子的概念构造聚类评价函数引入数据场拓扑势划分簇引入节点的相似度概念构造多目标聚类评价函数 研究背景与意义 3 3 计算机学院 基于数据场的自适应聚类算法实现 1 6 算法思想指出网络中心节点的评价指标适用于聚类算法中初始节点的选择 提出了节点重要性因子的概念利用物理场拓扑势和k means算法的思想成簇通过构造合适的聚类评价函数来实现算法的自适应性 解决初始簇结构个数难以抉择的问题 计算机学院 基于数据场的自适应聚类算法实现 2 6 节点的重要性因子 聚类评价函数的构建 簇内相似度 SimilarityWithinClusters 簇间相似度 SimilarityBetweenClusters 聚类评价函数 度中心化 紧密度中心化 互信息中心化 计算机学院 基于数据场的自适应聚类算法实现 3 6 数据场和势 定义1场强函数 在数据场中 空间 中共有n个对象 令x代表对象所处位置 则在该数据场中x处对象xi所产生的势为 定义2势函数 数据场是具有叠加性的 因此 任意数据对象vj V的拓扑势可定义为 计算机学院 基于数据场的自适应聚类算法实现 4 6 算法实现流程按照上面的思想对算法进行实现 可以分为7个步骤 其流程图如右图所示 图3 3本算法流程图 表3 2本算法与GN算法复杂度比较 计算机学院 基于数据场的自适应聚类算法实现 5 6 图3 7本算法与GN算法准确度的曲线图 分析仿真结果可以发现 整体来看 本算法的准确度优于GN算法 且稳定性更好 仿真结果算法准确性评估 计算机学院 仿真结果算法有效性评估 基于数据场的自适应聚类算法实现 6 6 图3 5Zachary空手道俱乐部成员关系网络 图3 6基于GN算法的聚类结果 图3 7基于本文算法的聚类结果 计算机学院 基于数据场的多目标自适应聚类算法实现 1 6 算法思想 引入节点相似度概念来发现核心外围结构的网络簇结构的中心节点利用物理场和k means算法的思想划分簇构造多目标评价函数以发现不同网络的拓扑结构 且对各种聚类评价函数进行一个综合考量 计算机学院 节点相似度的选取 基于数据场的多目标自适应聚类算法实现 2 6 簇中心节点的选取 多目标聚类函数的构造 当c 1时 规定 集合中元素的个数 节点u的邻居节点集合 计算机学院 基于数据场的多目标自适应聚类算法实现 3 6 算法步骤 Step1设core c1 聚类中心节点集合 c1为网络中度最大的节点 V1 V core 聚类中心以外的节点集合 c 2 Step2若 core c V2 V1 转Step3 否则 转Step4 Step3若V2 则选择节点集合V2中度最大的节点c1 V2 V1 c1 对于任何v core 计算S c1 v 的值 若S c1 v 且S c1 则将c1作为一个聚类中心 core core c1 V1 V1 c1 否则转Step7 计算机学院 基于数据场的多目标自适应聚类算法实现 4 6 Step4计算集合core中c个节点对集合V1中节点i的影响度 若存在两个中心节点对某节点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 值最大时的簇拓扑结构输出 算法结束 算法步骤 计算机学院 空手道俱乐部网络结果 图4 3本算法对空手道俱乐部网络的划分结果示意图 宽吻海豚家族网络 图4 4宽吻海豚家族网络拓扑结构图 基于数据场的多目标自适应聚类算法实现 5 6 实验结果分析 计算机学院 实验结果分析 图4 5本算法对宽吻海豚网络的划分结果 图4 6GN算法对宽吻海豚网络划分为4个簇结构的结果 基于数据场的多目标自适应聚类算法实现 6 6 计算机学院 文章小结指出网络中心节点的评价指标适用于聚类算法中初始节点的选择 提出了节点重要性因子的概念引入了节点相似度的概念来挖掘更适合的簇中心节点通过构造合适的聚类评价函数来实现算法的自适应性 解决初始簇结构个数难以抉择的问题利用物理场拓扑势和k means算法的思想成簇提出了一种新的聚类算法 总结与展望 工作展望研究有权有向的复杂网络聚类发现重叠的簇结构尽可能多的考虑节点的属性 计算机学院 在校期间发表论文 发表论文 YuhuaLiu CuiXu KeXu JianzhiJin AnImprovedClusteringMethodBasedonDataField 20132ndInternationalConferenceonAdvancedinControlEngineeringandInformationScience CACE 13 atlantis Hongkong China October12 13 2013 EI收录 CuiXu YuhuaLiu KaihuaXuandKeXu AnAdaptiveClusteringAlgorithmBasedonDataFieldinComplexNetworks 2013ThirdIEEEInternationalConferenceonInformationScienceandTechnology ICIST2013 IEEE Yangzhou China March23 25 2013 EI收录 KeXu YuhuaLiu CuiXu KaihuaXu ACluster basedandRangefreeMDS MAPLocationSchemeinWSN 3rdInternationalConferenceonComputerEngnieeringandNetwork CENet2013 Springer Shanghai China July20 21 2013 EI收录 DiZhang YuhuaLiu CuiXuandYongqiangQi OneOCDMAPONSystemwith2DMulti LengthTwo WeightCHPCs Proceedingsofthe2ndInternationalSymposiumonComputer Communication ControlandAutomation ISCCCA 13 atlantis Taiyuan China April6 7 2013 EI收录 YuhuaLiu ZhenrongLuo KeXuandCuiXu TheResearchofRoutingAlgorithmBasedonShortestPathTreeinWSNs 2013InternationalConferenceonComputerScience ElectronicTechnologyandIntelligentSystem CSETIS2013 atlantis Hangzhou China March22 23 2013 EI收录 YuhuaLiu JianzhiJin YiZhangandCuiXu ANewClusteringAlgorithmBasedonDataFieldinComplexNetworks TheJournalofSupercomputing Springer Vol 67 No 3 March 2014 pp 723 737 SCI收录 刘玉华 张翼 徐翠 晋建志 一种基于数据场的复杂网络聚类算法 计算机科学 2013 40 11 70 73 刘玉华 郑梅容 许凯华 徐翠 基于耦合系数的无标度网络模型 BA S 的中心化研究 计算机科学 2013 40 5 70 73 YuhuaLiu WenwenDai Ya