北 京 邮 电 大 学
本科毕业设计（论文）中期进展情况检查表
学院 学生姓名 指导教师姓名 信息与通信工程学院 专业 学号 所在单位 信息工程 班级 班内序号 职称 设计（论文）题目 复杂网络社团发现算法研究 以 完 成 的 任 务 主要内容: (毕业设计（论文）进展情况，字数一般不少于1000字) 1.完成复杂网络理论研究，其中包括对复杂网络的研究史以及基本概念的理解以及应用，同时对于网络拓扑基本模型及其性质有了基本的了解，对于小世界模型以及无标度网络模型的分析进行了解，理解Internet的拓扑结构和建模，学习复杂网络中的社团结构以及一些基本算法。 2. 完成randomwalk算法研究以及改进：研究random walk算法，并对这种凝聚算法进行理论分析，提出改进算法。 算法原理： A.通过random walk 得到社团结构的相似度矩阵S 从社团每个节点依次random walk（步数自定），random walk是在节点i的所有邻居节点i中等概率的找到下一个节点j进行游走。 在每次random walk的过程中记录经过的点i（不重复），记录入集合C中，从集合C中的元素遍历，依次得出两个不等元素i、j，作为矩阵的行列，记录入矩阵中。 从每次random walk得到的矩阵元素进行相加，最终得到相似度矩阵。 B．融合相似度矩阵 集合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． 通过random walk 得到集合C 把边的哈希表进行遍历，得到顺序排列的边哈希表（边哈希表中存储的边的节点对，顺序排列则是以起点为顺序进行排列）。得到哈希表后，每次random walk便可以从边哈希表中找到相应的以i为起点的边等概率的取其中一条边，以此为基础得到random walk遍历中得到的所有点，记录到集合C中 B． 得到相似度矩阵，以及融合相似度矩阵S。 使用的行逻辑链表实现，在每次从集合C中遍历，记录行的序号，连接到带行指针组的单链表，按照顺序记录一行的非零元素（如果链表有相应的结构体，则结构体对应的元素值加1，如果没有则加入相应的结构体），生成矩阵之后，遍历找到最大值，行的融合是直接从单链表找到行的元素融合，融合后删除链表中的行，然后对应融合行的元素转至后在新链表中遍历系数矩阵改变让其取代原来的 3.算法改进： 一：由于研究的网络是有权重的有向图网络，对于每次等概率的随机的选择邻居节点进行改进，把相应的边的权重加入其中，设节点所有临边的权重和为h，其中一条边的权重为x，则相应的概率p=x/h，以此概率来实现随机游走。 二：将所有度为1的节点去除后，进行随机游走算法，最后得出的矩阵划分后，将删除的节点度为1的节点带入已经划分好的相应的社团结构。 三： 对于融合矩阵的过程中，简单的以平均值为融合后的元素值，要对于融合以最大值和最小值对平均值进行比较。 值。 是否符合任务书要求进度 尚需完成的任务 1. 对于一直社团结构的复杂网络进行实现，比较算法的复杂度，以及对于网络划分的准确性。 2. 对大型复杂网络进行社团划分，比较其聚类系数等相关的值。 能否按期完成设计（论文） 能 在算法实现的编译过程中，虽然框架已经编译完成，但仍然存在一些bug没有调通，对random walk算法的改进算法没有突破性的进展。 存在问题和解决办法 存在问题 采 取 的 办 法 1对于算法的编译，进行多次的改进，最终实现算法。 2.加深对于random walk 算法的理解，从而能够在深层次上对于random walk 算法进行拟 改进。 指导教师 签字 日期 年 月 日 检查小组意见 负责人签字： 年 月 日 注：可根据长度加页。