间跟数据集的个数有关系。图在上谱平分法和优化的谱平分法的收敛曲线图在上谱平分法和优化的谱平分法的收敛曲线山东师范大学硕士学位论文本章小结在本章里，我们首先对谱平分法进行了详细的描述，然后引入两种算法分别对其中的过程进行了优化算法似的矩阵的特征值和特征向量的求解不再是个奢侈的时间浪费，算法使得算法在选取初始聚类中心的时候有了比较准确的定位。优化后的谱平分法更有利于在编程模型上实现，也更能够发挥的优势。山东师范大学硕士学位论文第五章优化的谱平分法在上的实现优化的谱平分法在上的实现上面的章节已经对谱平分法在两个方面进行了速度的优化，是利用算法来计算矩阵的特征值和特征向量二是利用算法对进行了优化，这样有利于解决算法在开始选取聚类中心的盲目性，进步加快了划分的速度。但是，随着网络规模的扩大，数据也成指数形式增长，单纯地对串行算法进行优化已经不能满足人们的需要，于是人们提出了对算法的并行化。是种并行化编程模型，这种模型的好处就是隐藏了底层的许多实现细节，使程序员从消息传递等繁复的问题中解脱出来，能够专注于自己的程序设计。这种编程模式是把数据划分成若干个数据块，分别分配到不同的数据节点，基于这种形式，要求并行算法必须是高内聚低耦合的。通过对谱平分法的研究发现，算法的时间消耗主要在以下几个方面相似度矩阵的构建对行标准化矩阵的特征值特征向量的求解和对新的样本空间的聚类。根据上述对算法的优化以及的特性，发现上述三个过程都很适合进行并行，但是这几个过程有先后顺序，整体是串行的，但是它们的每步都可以并行起来。下面将对这三个过程的并行化进行详细的描述。相似度矩阵构建的并行化本文的相似度采用共享最近邻来衡量，相似度矩阵的定义为设网络有个节点，相似度矩阵定义为，其中表示的邻居集合，其中若，之间有边相连，则，否则。由于相似度矩阵是个对阵矩阵，所以，只需要计算上三角阵或者下三角阵，在计算的时候，每对节点之间只需要计算次，而且为了避免重复计算，在对于任意个节点，只需要计算序号在它之后的节点，为了负载均衡，将下标与其他节点的相似度计算和下标与其他节点的相似度计算放在起，而将下标与其他节点的相似度计算和下标与其他节点的相似度计算放在起，以此类推。基于上述理论，相似度矩阵构建的数据结构为个邻接表形式，数组的头为网络里面的节点编号，每个节点后面的链表为按顺序插入的所有邻居节点，以便于后面对共享最近邻进行计算。数据的存储结构如下图山东师范大学硕士学位论文节点邻居邻居邻居邻居邻居邻居邻居邻居邻居邻居邻居邻居图网络的邻接表存储结构构建邻接表的过程相对比较简单，首先确定数据的读入类型，这里选择点对格式的文本文件，个点对代表条边的两个顶点，如。按照分布式文件系统的数据存储和处理结构，对于每个点对，将第个顶点作为，第二个顶点作为输入存储，然后将这两个节点互换，再重复上述步骤，直到网络中的所有点对全部读入。然后在阶段，根据每个值进行规约，就得到了上述邻接表。创建邻接表后，我们将邻接表作为构建相似度矩阵的输入。将邻接表放入中，使集群中的所有都可以对其进行访问。因为计算相似度矩阵时，节点的相似度计算和和其他节点的相似度计算是彼此独立的，我们就可以把各个节点的相似度计算依次分配给不同的机器同时去完成。对于点和其他节点的相似度计算，要依次计算和个节点，„，的相似值，即要计算个节点的相似度，要计算个节点的相似度，„„，要计算个节点的相似度，要计算个节点的相似度，为了均衡计算节点的负载，我们把和的相似度计算放到起，和的相似度计算放到起，以此类推的分配下去，每个都会计算节点的相似度，并把他们存入中，所有的节点与其他节点相似值计算完毕后，即得到相似度矩阵。并行构建相似度矩阵的过程伪代码如图所示山东师范大学硕士学位论文图构建相似度矩阵的和过程特征值特征向量的求解的并行化算法是种将对称矩阵通过正交相似变换变成对称三对角矩阵的算法。方法目前被认为是求解大型矩阵特征值问题的最有效方法，与子空间迭代法相比，其计算量要少得多。它把原拉普拉斯矩阵转换成三对角矩阵，将三对角矩阵的特征向量变换到原问题的特征向量，可以证明该三对角矩阵的特征向量就是矩阵特征值的近似值。从前面章节介绍的算法可以看出，矩阵和向量相乘是最耗时的操作，矩阵在上是按行存放的，各个计算节点可以并行访问，每次计算就不需要移动矩阵，而只移动向量就可以了。这样各个计算节点就可以并行计算和矩阵的各行的乘积，我们可以使用过程来实现这个过程。得到和矩阵各行的乘积后，经过过程，就可以快读计算，加快了迭代的过程。并行算法求解特征向量算法的伪代码如图所示。图并行求解特征向量算法的伪代码法的过程山东师范大学硕士学位论文算法的并行化算法在单机上具有较好的聚类效果，同时也适用于编程模型。算法有两处适合进行并行计算，是使用方法对原始数据集进行粗糙地簇的划分，因为这个过程是只是基于数据的距离，所以，在数据划分的时候，只需要将数据按照平衡负载的条件下均分给机群中的各个数据节点，在每个计算节点中先进行优化，然后，再将结果回送给控制节点，进而得到整个数据集合的划分然后，根据优化的算法，从簇中选取个节点作为初始聚类中心，然后将这些中心作为初始聚类中心，并把它们存放于全局变量，再通过计算其他弱标记节点到聚类中心的距离，从而达到社团划分的目的。并行算法的具体过程为将新的样本空间数据平均分配机群中的各个计算节点在每个计算节点本地进行运算，找到本地的划分簇，即并行的过程，并行的过程伪代码如图所示将每个计算节点的划分结果整合到控制节点，即并行的过程，并行的过程伪代码如图所示控制节点在多个子集中心中选取个作为的初始聚类中心，并作为全局变量放在中对每个弱标记节点和个之外的簇中的所有节点重新分配到各数据节点，然后计算其到每个聚类中心的距离，并归入相应的簇中，即算法的过程，伪代码如图所示更新聚类中心，直到中心点不再变化或者达到迭代次数为止，即算,图并行的伪代码个四核内存存储器硬盘网络千兆以太网操作系统编号社团网络样本大小节点数节点数山东师范大学硕士学位论文图并行的伪代码实验分析实验环境本实验使用台相同配置的计算机来搭建集群，使用其中的台作为分布式文件系统的节点，使用它来管理剩下的台数据节点。实验从加速比准确率扩展性上，验证并行的谱平分法的性能。表为实验中用到的计算机的配置情况表集群计算机的配置实验中的计算机使用的都是操作系统，是遵循开源软件原则的系统。搭建实验环境，需要注意以下几点首先要保证各台计算机之间的网络是畅通的，即能够相互通。由于及其相关的代码都是在基础上开发的，所以运行之前需要正确安装。般将其安装到目录下，然后配置环境变量。要求所有机器上的部署目录结构要相同，并且都有个相同的用户名的账户，所以需要每台机器建个同名的用户。需要到的无密码公钥验证方式的，所以需要设置到其他台的无密码公钥认证方式的。在设置之前先要安装服务并开启，如果没有安装可以使用命令进行安装。这里由于篇幅限制不再赘述，详细步骤可参照权威指南。处理器个四核内存存储器硬盘网络千兆以太网操作系统编号社团网络样本大小节点数节点数山东师范大学硕士学位论文实验结果及分析为了测试算法的可扩展性加速比准确性，我们使用种图模型，生成社团结构可明显变化的人工社团网络。在这种图模型中，我们使用三个参数来调整生成的图。在这种图模型中，网络中节点的度和社团的规模是随着幂律的分布而分布的，分别由和来定义。参数表示与个节点相连的所有边中连接至其他社团的比例。通过调整，我们可以调整网络的社团明显程度。在程序中可以使用和图中每个社团谢福鼎,张磊,嵇敏,黄丹种基于谱平分法的社团划分算法计算机科学,,,,,,,,,杨冬青,马秀莉,唐世渭数据库系统概念,北京机械工业出版社,,,王宇,王志坚志愿计算模型形式化方法软件学报,,,,,,,,,,,,,解,汪小帆复杂网络中的社团结构分析算法研究综述复杂系统与复杂性科学王林,戴冠中复杂网络中的社区发现理论与应用科技导报,,,山东师范大学硕士学位论文,,,,山东师范大学硕士学位论文攻读硕士学位期间的主要成果发表或录用的学术论文李尚英,高玲复杂网络社团划分算法研究,信息技术与信息化山东师范大学硕士学位论文致谢在山东师范大学三年的硕士研究生生活即将结束，是我人生的这重要阶段中，得到了许多老师和同学的热情帮助和关怀，直心存感激，借此机会，向他们致以最诚挚的谢意。首先要感谢的是我的导师高玲，年我有幸成为她的学生，并在她的悉心指导下完成学业。高老师治学严谨胸襟宽广凡事以身作则，无论在学习上还是在生活上都深深地影响着我，并伴随我的生，对于我的学习老师花费了大量的心血，很多时候为自己感觉羞愧，辜负了老师细心培养，不过，我会直努力的。在此向我的恩师致以最诚挚的谢意,感谢学院为我们提供的实验室，组营造了良好的学习氛围，大家在学术和技术上的交流和讨论使我得到很大的提高。在实验室几年的学习中，让我的实际解决问题的能力得到了很大的提高，老师们教会了很多生活上的道理，如沐春风般的关怀，深深地打动我。在这还要感谢曾经给我传授知识的老师们。感谢刘方爱教授刘培玉教授张化祥教授杨峰教授王新华教授王化雨副教授王红教授张永胜教授秦茂玲副教授马学强副教授。他们教学风