基于分解多目标优化的符号网络结构平衡研究

发布时间：2017-10-05 09:42

  本文关键词：基于分解多目标优化的符号网络结构平衡研究

  更多相关文章： 符号网络 结构平衡 多目标优化 局部搜索

【摘要】：21世纪,随着科技的迅猛发展,信息领域日新月异,各种网络应用层出不穷。其中,各种购物网站、社交网站、在线社区的快速发展,正潜移默化地改变着我们的生活方式、思维方式。在这样的时代背景下,符号网络在理解、预测复杂网络的拓扑结构、功能、动态发展方面的研究意义越来越明显,如在个性化推荐、用户态度预测方面,整合负边信息,能够提高推荐、预测的准确度。符号网络结构平衡也引起了众多学者的关注,并取得了很多有意义的成果。但是研究多是基于启发式方法或单目标优化,单次运行所得结果单一,在应用中会有很大的局限性。本硕士论文主要针对符号网络的结构平衡进行研究,从多目标优化的角度出发,结合影响网络平衡的具体因素,提出了一种多目标优化模型和基于子集的局部搜索策略。本论文具体所做的工作如下:(1)对研究符号网络结构平衡的论文进行了大量阅读,理解了符号网络的意义,并对现存的符号网络结构平衡算法有了宏观上的理解。(2)从多目标优化角度出发,以弱平衡理论为基础,根据符号网络中不平衡因素的两个方面,将符号网络结构平衡问题建模为多目标优化问题。该模型包含两个目标函数negin、posout,分别表示网络划分中子集内的负边总数目,子集间的正边总数目。由于MOEA/D算法计算复杂度相对较低且生成的Pareto前沿面均匀等特点,本文采用MOEA/D算法作为算法框架,同时,结合具体的符号网络结构平衡问题,充分利用网络的拓扑信息,选取one-way交叉算子和基于节点正邻域的变异算子,设计了MOEA/D-SNB算法解决上述多目标优化问题。通过在人工合成网络和真实网络数据集上同MODPSO、FEC算法的大量对比实验,验证了上述方法在处理结构平衡问题上的有效性。(3)为了进一步提高MOEA/D-SNB算法的搜索力度,结合符号网络结构平衡特性,设计了基于子集的局部搜索策略。该策略侧重于优化多目标模型中的posout函数。从子集的角度,定义了网络划分的邻域。基于贪婪思想,网络划分在每个邻域内寻找能使其posout值降低最多的邻居来进行更新。依次遍历其所有邻域,使最终得到的网络划分中不存在之间只有正连接的子集对。同时,为了防止精英流失,在进行局部搜索之前,会对原始外部种群EP进行备份,最后将经过局部搜索前、后的外部种群合并,并进行非支配排序,返回所有非支配解作为最终的最优解集。通过比较MOEA/D-SNB中加入局部搜索前后在网络数据集上的实验效果,验证了本文所设计的基于子集的局部搜索策略在降低子集间正连接较多的网络划分的不平衡度的方面的有效性。
【关键词】：符号网络 结构平衡 多目标优化 局部搜索
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要5-7
• ABSTRACT7-11
• 符号对照表11-12
• 缩略语对照表12-15
• 第一章 绪论15-21
• 1.1 符号网络研究背景及意义15-16
• 1.2 符号网络结构平衡的研究意义及现状16-18
• 1.3 本文的主要内容与结构安排18-21
• 第二章 符号网络结构平衡相关理论21-29
• 2.1 结构平衡理论21-23
• 2.1.1 三元组模型21-22
• 2.1.2 强平衡理论22
• 2.1.3 弱平衡理论22-23
• 2.2 平衡度量函数23-25
• 2.2.1 基于平衡环路的度量函数23
• 2.2.2 基于特征值的度量函数23-24
• 2.2.3 基于不平衡边的度量函数24-25
• 2.3 符号网络结构平衡相关算法25-27
• 2.4 本章小结27-29
• 第三章 基于分解多目标优化的符号网络结构平衡29-51
• 3.1 引言29
• 3.2 多目标优化29-31
• 3.2.1 多目标优化模型29-30
• 3.2.2 常见多目标优化算法30-31
• 3.3 基于MOEA/D的符号网络结构平衡31-38
• 3.3.1 符号网络结构平衡多目标优化模型31-33
• 3.3.2 算法框架33-34
• 3.3.3 编码方式34-35
• 3.3.4 种群初始化35
• 3.3.5 遗传操作35-37
• 3.3.6 更新37-38
• 3.4 实验分析38-49
• 3.4.1 数据集38-39
• 3.4.2 对比算法及参数设置39-40
• 3.4.3 实验分析40-49
• 3.5 本章小结49-51
• 第四章 基于改进的MOEA/D-SNB算法的符号网络结构平衡51-63
• 4.1 引言51
• 4.2 局部搜索算子设计51-54
• 4.2.1 常用搜索策略51
• 4.2.2 基于子集的局部搜索51-54
• 4.3 实验分析54-61
• 4.3.1 数据集及参数设置54-55
• 4.3.2 实验分析55-61
• 4.4 本章小结61-63
• 第五章 总结与展望63-65
• 5.1 总结63
• 5.2 展望63-65
• 参考文献65-69
• 致谢69-71
• 作者简介71-72

【参考文献】

中国期刊全文数据库 前2条

1 程苏琦;沈华伟;张国清;程学旗;;符号网络研究综述[J];软件学报;2014年01期

2 公茂果;张岭军;马晶晶;焦李成;;Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J];Journal of Computer Science & Technology;2012年03期

，

本文编号：976116