基于进化算法的符号网络结构平衡分析.pdf

《基于进化算法的符号网络结构平衡分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于进化算法的符号网络结构平衡分析作者姓名孙一翔学校导师姓名、职称张青富教授领域电子与通信工程企业导师姓名、职称岳博副研究员申请学位类别工程硕士提交毕业论文日期2014年12月学校代码10701学号1202121466分类TN82号TP18密级公开西安电子科技大学硕士学位论文基于进化算法的符号网络结构平衡分析作者姓名：孙一翔领域：电子与通信工程学位类别：工程硕士学校导师姓名、职称：张青富教授企业导师姓名、职称：岳博副研究员提交日期：2014年12月StructuralBalanceAnalysisinSignedNetwor

2、ksbasedonEvolutionaryAlgorithmAthesissubmittedtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofMasterinElectronicsandCommunicationEngineeringBySunyixiangSupervisor:ZhangqingfuYueboDecember2014西安电子科技大学毕业论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我

3、个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。本论文与资料若有不实之处，本人承担一切的法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用毕业论文的规定，即：研究生在校学习期间论文工作的知识产权单位属西安电子科技大学。学

4、校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合毕业论文研究课题再撰写的文章一律署名单位为西安电子科技大学。（保密的论文在解密后遵守此规定）本论文属于保密，在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要在真实世界中，有许多复杂的系统可以被抽象成网络，比如社交网络、生物网络、协作网络、万维网、电力网，等等。网络通常是通过图的形式来展现的，在一个图中，每个节点都代表一个事物，节点之间的边代表相应事物间存在着某

5、种联系。一般情况下，这些网络中节点之间的边通常意味着友谊、合作、共享和其他一些具有积极意义的联系。但是在某些网络中，同时存在着一些消极的联系：有些联系代表友谊，而有些联系则代表敌对。比如在现实生活中，人与人之间或者团体与团体之间，定期地会被争论、反对意见，有时甚至是冲突所困扰。具有上述特征的网络通常被称之为符号网络。在网络的动态演化过程中，符号网络会渐渐向结构平衡的状态演化。结构平衡是符号网络的一个重要研究领域，从本质上讲，它是符号网络的一项全局特征，这个特征反映了网络的结构特点。有时为了研究符号网络的结构特点，我们需要测量

6、它的不平衡度，换句话说，我们需要测量符号网络从非平衡到平衡之间的距离。为了解决上述问题，我们可以考虑以某种方式计算符号网络的全局结构平衡，但是计算全局结构平衡相当于计算Isingspinglass的基态，它们都是典型的NP-Hard问题。为了快速有效地计算符号网络的全局结构平衡，我们将进化算法用于优化能量函数，进而实现进一步了解符号网络结构特点的目的。围绕这个问题，本论文所做的主要工作如下：1．介绍了基于遗传算法的符号网络结构平衡分析，即GA-SB算法。这部分首先对进化算法和遗传算法进行了简单介绍，然后重点描述了能量函数的概

7、念，之后结合符号网络结构平衡分析的具体情况，对算法的设计进行了详细介绍，并在社交网络和生物网络上进行了实验，最后对实验结果和算法进行了归纳总结，提出不足之处和需要改进的地方。通过对实验结果的归纳总结，我们发现GA-SB只有在处理小规模符号网络时，才能得到满意的结果，一旦网络的规模增大，GA-SB的性能将随即下降，其主要原因是算法收敛速度慢且容易陷入局部最优解，从而最后得到的解不准确。2．针对GA-SB算法存在的种种不足，我们对其进行了改进，提出了基于密母算法的符号网络结构平衡分析，即Meme-SB算法，Meme-SB有效地将

8、遗传算法和局部搜索结合起来，其中局部搜索采用了贪婪策略。这部分首先对密母算法进行了概述，密母算法的这种将种群全局搜索和个体局部搜索相结合的机制使得其搜索效率比传统的遗传算法快上好几个数量级，这也是我们选用密母算法的原I西安电子科技大学硕士学位论文因所在。之后我们结合了符号网络结构平衡分析的