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

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

2、行理论分析，提出改进算法。任算法原理务A.通过random walk得到社团结构的相似度矩阵S从社团每个节点依次ran dom walk （步数自定）,random walk 是在节占i的所有邻居节点 八i中等概率的找到下一个节点j进行游走O在每次random walk的过程中记录经过的点i （不重复）,记录入集合C 中，从集合C中的元素遍历，依次得出两个不等元素i、j,作为矩阵的行列， 记录入矩阵中。从每次Mndom walk得到的矩阵元素进行相加，最终得到相似度矩阵。B.融合相似度矩阵集合C存贮0-n的数值（n为节点数）从相似度矩阵中找寻最大值 Sij,融合第i行和第j行。融合过程为Sin

3、和Sjn取其平均值，赋值给Sino同理融合第i列和第j行。（注意元素Sii值为0）删除j行j列。将i, j作为一个小集合存入集合C中。直到稀疏矩阵元素全为零元素。算法的实现过程：A.通过random walk得到集合C把边的哈希表进行遍历，得到顺序排列的边哈希表（边哈希表中存储的边的节点对，顺序排列则是以起点为顺序进行排列）。得到哈希表后，每次random walk便可以从边哈希表中找到相应的以i为起点的边等概率的取其中 一条边，以此为基础得到random walk遍历中得到的所有点，记录到集合C中B. 得到相似度矩阵，以及融合相似度矩阵 So?使用的行逻辑链表实现，在每次从集合C中遍历，记录

4、行的序号，连接到带行指针组的单链表，按照顺序记录一行的非零兀素（如果链表有相应的 结构体，则结构体对应的元素值加1,如果没有则加入相应的结构体），生成矩 阵之后，遍历找到取大值，行的融合是直接从单链表找到行的兀素 融合，融合 后删除链表中的行，然后对应融合行的兀素转至后在新链表中遍历系数矩阵改 变让其取代原来的值。3.算法改进：由于研究的网络是有权重的有向图网络，对于每次等概率的随机的选 择邻居 节点进行改进，把相应的边的权重加入其中，设节点所有临边的权重和为h,其中一条 边的权重为X,则相应的概率p二x/h,以此概率来实现随机游走。二：将所有度为1的节点去除后，进行随机游走算法，最后得出的矩

5、阵划 分后， 将删除的节点度为1的节点带入已经划分好的相应的社团结构。三：对于融合矩阵的过程中，简单的以平均值为融合后的元素值，要对于融合以最大值和最小值对平均值进行比较。尚是否符合任务书要求进度需宀完成的任务1.对于一直社团结构的复杂网络进行实现，比较算法的复杂度，以及对于网络划分 的准确性。2.卞t大型复杂网络进行社团划分，比较其聚类系数等相关的值。能否按期完成设计（论文）能存在在算法实现的编译过程中，虽然框架已经编译完成，但仍然存在一些bug没问有调通，对random walk算法的改进算法没有突破性的进展。存在题问题拟和解决办法釆1对于算法的编译，进行多次的改进，最终实现算法。取2.加深对于random