北京邮电大学本科毕业设计(论文)中期进展情况检查表.doc

《北京邮电大学本科毕业设计(论文)中期进展情况检查表.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京邮电大学本科毕业设计（论文）中期进展情况检查表学院信息与通信工程学院专业信息工程班级学生姓名学号班内序号指导教师姓名所在单位职称设计（论文）题目复杂网络社团发现算法研究以完成的任务主要内容:(毕业设计（论文）进展情况，字数一般不少于1000字)1.完成复杂网络理论研究，其中包括对复杂网络的研究史以及基本概念的理解以及应用，同时对于网络拓扑基本模型及其性质有了基本的了解，对于小世界模型以及无标度网络模型的分析进行了解，理解Internet的拓扑结构和建模，学习复杂网络中的社团结构以及一些基本算法。2.完成randomwa

2、lk算法研究以及改进：研究randomwalk算法，并对这种凝聚算法进行理论分析，提出改进算法。算法原理：A.通过randomwalk得到社团结构的相似度矩阵S从社团每个节点依次randomwalk（步数自定），randomwalk是在节点i的所有邻居节点i中等概率的找到下一个节点j进行游走。在每次randomwalk的过程中记录经过的点i（不重复），记录入集合C中，从集合C中的元素遍历，依次得出两个不等元素i、j，作为矩阵的行列，记录入矩阵中。从每次randomwalk得到的矩阵元素进行相加，最终得到相似度矩阵。B．融合

3、相似度矩阵集合C存贮0-n的数值（n为节点数）从相似度矩阵中找寻最大值S[i][j]，融合第i行和第j行。融合过程为S[i][n]和S[j][n]取其平均值，赋值给S[i][n]。同理融合第i列和第j行。（注意元素S[i][i]值为0）删除j行j列。将i，j作为一个小集合存入集合C中。直到稀疏矩阵元素全为零元素。算法的实现过程：A．通过randomwalk得到集合C把边的哈希表进行遍历，得到顺序排列的边哈希表（边哈希表中存储的边的节点对，顺序排列则是以起点为顺序进行排列）。得到哈希表后，每次randomwalk便可以从边哈

4、希表中找到相应的以i为起点的边等概率的取其中一条边，以此为基础得到randomwalk遍历中得到的所有点，记录到集合C中B．得到相似度矩阵，以及融合相似度矩阵S。 使用的行逻辑链表实现，在每次从集合C中遍历，记录行的序号，连接到带行指针组的单链表，按照顺序记录一行的非零元素（如果链表有相应的结构体，则结构体对应的元素值加1，如果没有则加入相应的结构体），生成矩阵之后，遍历找到最大值，行的融合是直接从单链表找到行的元素融合，融合后删除链表中的行，然后对应融合行的元素转至后在新链表中遍历系数矩阵改变让其取代原来的值。3.算法改

5、进：一：由于研究的网络是有权重的有向图网络，对于每次等概率的随机的选择邻居节点进行改进，把相应的边的权重加入其中，设节点所有临边的权重和为h，其中一条边的权重为x，则相应的概率p=x/h，以此概率来实现随机游走。二：将所有度为1的节点去除后，进行随机游走算法，最后得出的矩阵划分后，将删除的节点度为1的节点带入已经划分好的相应的社团结构。三：对于融合矩阵的过程中，简单的以平均值为融合后的元素值，要对于融合以最大值和最小值对平均值进行比较。尚需完成的任务是否符合任务书要求进度1.对于一直社团结构的复杂网络进行实现，比较算法的复

6、杂度，以及对于网络划分的准确性。2.对大型复杂网络进行社团划分，比较其聚类系数等相关的值。存在问题和解决办法能否按期完成设计（论文）能存在问题在算法实现的编译过程中，虽然框架已经编译完成，但仍然存在一些bug没有调通，对randomwalk算法的改进算法没有突破性的进展。拟采取的办法1对于算法的编译，进行多次的改进，最终实现算法。2.加深对于randomwalk算法的理解，从而能够在深层次上对于randomwalk算法进行改进。指导教师签字日期年月日检查小组意见负责人签字：年月日注：可根据长度加页。