复杂网络社团划分算法的-.研究与实现

《复杂网络社团划分算法的-.研究与实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1．1．1背景1．1人们生活在一个充斥着各种复杂网络的世界中，现实世界中的诸多系统都以网络的形式存在的，各种现实存在的和抽象的网络出现在人们生活的各个角落，随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同的性质，即社团结构【l】。大量的实证研究表明，许多网络是异构的，也就是说复杂网络不是由一大批性质完全相同的节点随机地连接在一起的，而是许多不通类型的节点的组合，相同类型的节点之间存在较多的连接，而不同类型的节点之间的连接则相对较少，我们把满足同一类型中的节点以及这

2、些节点之间的边所构成的子图被称为网络中的社团(community)。整个网络是由若干个社团构成的，每个社团内部的节点之间的连接相对非常紧密，但是各个社团之间的连接相对来说比较稀疏，由于这些网络具有很高的复杂性，因此被称为“复杂网络(complexnetwork)"，这些发现直接导致了网络社团结构的研究。1．1．2意义信息技术的迅猛发展使人类快速进入了网络时代，从Intemet到WWW，从大型电力网络到全球交通网络，从生物的大脑到新陈代谢网络，从科研合作网络到各种经济、政治、社会关系网络SNS等，

3、人们生活在充满格式各样的复杂网络的世界当中，人类社会日益网络化，需要人类对各种人工和自然的复杂网络的行为有更好的认识[21，复杂网络中自动搜寻或发现社团具有重要的实用价值，社团划分有很多实际的用途，如社会网络中的社团代表根据兴趣或背景而形成的真实的社会团体；引文网络中的社团代表针对同一主题的相关论文；万维网中的社团就是讨论相关主题的若干网站13州：而生物化学网络或者电子电路网络中的社团可以是某一类功能单元。发现这些网络中的社团有助于我们更加有效地理解和开发这些网络。例如多处理器并行计算中的处理器

4、分配，人际关系网络的团体划分等等。因此，对复杂网络中的社团结构划分算法的研究有较现实的意义。目前这一研究方向正逐渐受到更多的关注15J。2复杂网络社团划分算法的研究与实现1．2国内外研究现状由于复杂网络社团划分研究具有重要的理论意义和应用价值，它不仅成为计算机领域中最具挑战性的基础性研究课题之一，也吸引了来自物理、数学、生物、社会学和复杂性科学等众多领域的研究者，掀起了一股研究热潮。目前这一领域的理论研究还处于起步阶段，虽然已经提出了很多经典的复杂网络社团结构划分算法，但是还没能有一种相对统一的

5、算法解决大多数网络划分的问题，另外，目前算法在效率和精度上都尚不能满足很多实际应用需求。从2002年至今，新的方法层出不穷，新的应用领域不断被拓展，不同领域的权威国际杂志和多个重要的国际学术会议多次报道这方面的研究工作。复杂网络社团划分方法已成为图论、复杂网络、数据挖掘等基础理论的重要组成部分和相关课程的核心内容，国际知名的研究性大学计算机系也开设了“TheStructureofInformationNetworks’’和“NetworksandDynamics"课程．国内也出现了一些研究复杂网

6、络的专著和图书。1．3本文工作本文工作主要围绕以下几个方面展开。首先对现有的复杂网络社团划分算法进行深入研究，归纳现有算法的研究思路，在此工作基础上对现有算法的优缺点进行总结，明确当前复杂网络社团划分算法尚需解决的问题，对本文算法的设计给出指导。其次，在综合前人的研究成果基础上，本文将对笔者提出的两种复杂网络社团划分算法的设计思路以及算法效果给出论证。文中提出的第一种算法是基于遗传规律的复杂网络社团划分算法，本文将详细论述如何将遗传算法应用到了复杂网络社团划分的过程中，文中还将提供针对此算法提出

7、的可扩展的基因编码方案，对文中引入的可提高收敛速度的孤立点修复策略进行说明，还将对该算法具有在复杂网络的海量社团划分方案中搜索到较优可接受划分方案的能力给出证明。文中提出的第二种算法是基于引力定律的复杂网络社团划分算法，本文将围绕该算法的两个主要部分进行说明，本算法第一个要点是利用节点相对位置关系对节点进行分类的引力聚类算法，第二个要点是生成节点相对位置关系的弹性算法。该部分将重点论述弹性算法是如何将复杂网络邻接关系快速映射到二维空间，使关联度较高的节点形成相对致密的节点簇，从而使原本不存在位置

8、信息的节点具有了相对位置关系这以过程的。文中给出了一种近似计算方法优化弹性算法的绪论3执行效率。论文最后用实验证明此算法能识别出复杂网络社团结构，并且在不需要先验信息的情况下表现出较优的划分速度和划分精度。最后，论文将介绍为辅助上述划分算法研究而进行的辅助研究和开发工作，文中给出了复杂网络社团划分算法的验证实验原理和过程，实现了多个对比算法，做了大量的实验和分析，给出了构建测试复杂网络的方法，搭建了用于算法研究的可扩展实验平台。1．4论文章节安排按照论述的内容，本文对各个章节的写作进行了如下安排