1、“.....使我能够很快的适应实验室生活。并在随机游走算法的理解以及实现上给与我很多的帮助。我还要感谢同学的帮助。他们在我研究复杂网络以及随机游走算法的过程中给予了我多的鼓励和帮助。尤其是在我实现随机游走算法的过程中给予了我很多启发性的帮助。最后，我还要感谢我的家人，没有他们长久以来的支持和鼓励，我不可能顺利完成大学学业。谨以此文献给我的家人。，就可以根据非零特征值相应的特征向量中的元素对应网络的结点进行分类。其中，所有正元素对应的那些结点都属于同个社区，而所有负元素对应的结点则属于另个社区。因此，我们可以根据网络的矩阵的第二小的特征值将其分为两个社区。这就是谱平分法的基本思想。当网络的确是分成两个社区时，用谱平分法可以得到非常好的效果。但是，当网络不满足这个条件时，谱平分法的优点就不能得到充分体现。事实上，第二小特征值可以作为衡量谱平分法效果的标准它的值越小......”。

2、“.....也称为图的代数连接度。般情况下，计算个矩阵的全部特征向量的时间复杂度为。但是在大多数情况下，实际网络的矩阵是个稀疏矩阵，因此，可以用方法快速计算主要的特征向量。该方法的时间复杂度大致为，其中，表示网络中边的条数。这样，计算的速度可以得到很大程度的提高。但是，如果不能很快将从其它特征值中分离出来，该算法就可能在定程度上有所减慢。换句话说，当网络很明显地分成两个社区时，该算法的速度非常快，否则该算法就未必很有效。北京邮电大学本科毕业设计论文其他经典算法算法算法是种分裂方法，它通过迭代从网络中移除介数最大的边将整个网络分解为各个社区。边的介数定义为网络中经过该边的最短路径的数目。它为区分个社区内部边和外部边连接提供了个度量准则。算法的基本流程如下计算网络中的所有边的介数找到介数最高的边并将它从网络中移除重复步骤，直到每个节点就是个退化社区为止......”。

3、“.....此算法也不能确定迭代的合适步数。快速算法由于算法的时间复杂度较大，所以对大规模的复杂网络的分析效果并不理想。在算法的基础上提出了种快速算法，它是基于贪婪算法思想的种凝聚算法。此算法总的时间复杂度为。整个算法完成后可得到个社区结构分解的树状图，再通过选择在不同位置断开可得到不同的网络社区结构，在这些社区结构中，选择个对应着局部最大的值，就得到最好的网络社区结构。算法该算法与算法相同，都是基于去边，但不是根据边介数选择要去除的边，而是引进了边聚集系数的新指标。整个算法的运行时间为。显然，对于稀疏图，其计算速度要比算法快个数量级。等考虑网络中的三角环即边数为的闭合路径。若个三角环包含条连接不同社区的边，则该三角环中的另两条边中的条仍然连接这两个社区的可能性将很大。但是由于连接不同社区的边非常稀少......”。

4、“.....将条边的边聚集系数定义为包含该边的三角环所占比例,其中分别表示节点和的度，表示网络中实际包含该边的三角环的个数。上式中的分母表示包含该边的最大可能的三角环的个数。算法每步去除的是网络中边聚集系数最小的边，每次去除后，再重新计算每条边的边聚集系数，如此进行下去，直至网络中不存在任何边。算法的不足是该算法依赖于网络中的三角环，如果网络中三角环很少，那么该算法将失去意义。实证研究表明，社会网络中三角环的数量比较大，而在非社会网北京邮电大学本科毕业设计论文络中，三角环的数量则相对较少。这意味着算法更加适合于社会网络。北京邮电大学本科毕业设计论文第四章基于随机游走的社团发现算法本章主要介绍种基于图论的随机游走算法，主要介绍了该随机游走算法的基本原理，以及随机游走算法的编译实现方式。随机游走算法的基本原理在上章节对各种社团发现算法的介绍和比较后......”。

5、“.....该算法的主要实现原理是基于此种方式，即在以任意节点为起点进行有限步数的随机游走，在有限的步数内，相比于在不同的社团间的随机游走，该随机游走是有更大的可能性是停留在同个社团内部的。我们通过记录在每次随机游走过程中的轨迹来作为节点间属于同个社团的证据。正式介于此类原理，我们提出了这种更简单，更直接的划分复杂网络的社团结构的随机游走算法。随机游走算法的相似度矩阵获取随机游走的基本思想是进行多次段较短步数的随机游走，并且把在同次随机游走过程中经历的节点作为他们同属于个社团的证据。这个信息在经过所有的随机游走过程后被补充完整，并被用来作为个基本的信息去划分复杂网络的社团结构，算法的基本过程在图中显示。算法的过程中，我们首先定义的矩阵，把矩阵中的每个元素都赋值为。在考虑算法的随机游走的步数时......”。

6、“.....在随机游走算法的过程中，我们从节点开始进行随机游走，随机游走即从节点的所有邻居节点中等概率的找到它的个邻居节点，作为随机游走的下个节点。在每次随机游走过程中，我们都会用个集合来存储我们这次随机游走过程中所遍历的节点集合中的数据是不重复的，即使我们随机游走的过程中经过多次节点，我们也只在集合中记录次。根据得到的集合，我们随机的选择集合中不相等的元素来作为相似度矩阵的行号和列号，即。与此同时，中的元素对应加。以此遍历复杂网络中的所有节点，得到个集合，并最终得出矩阵的值。在完成矩阵后，矩阵的每个元素表示节点和节点同属于次随机游走的次数，即同属于个社团的可能性的大小。值越大，表示，属于个社团的可能性便越大。北京邮电大学本科毕业设计论文图随机游走算法矩阵的获取随机游走算法的矩阵融合现在我们通过随机游走得到了个相似度矩阵......”。

7、“.....在融合的过程中不断得到新的社团结构。在融合矩阵的过程中，把每次融合的节点数进行记录到新的集合中，在矩阵融合结束后，集合中记录的便是复杂网络最终的社团结构的划分。在融合矩阵的过程中，我们使用的是与描述的凝聚算法相类似的种技术。这种方式的普遍观念是根据相似度矩阵中的元素的相似度的大小来进行融合。融合的方式为从最大的相似度开始融合，以后依次递减类推，在融合结束后得出结果。融合矩阵的算法在图中给出。北京邮电大学本科毕业设计论文图随机游走算法相似度矩阵的融合在矩阵融合的过程中，相似度矩阵的尺寸在每次的融合过程中不断的减少。矩阵在相应行列融合的过程中也在不断地进行变化。而在融合的过程中，几种不同的方式可供我们选择，有最大值，最小主要是在每次遍历的过程中都要需要相似度矩阵的最大值......”。

8、“.....为了降低此算法的复杂度，我们提出种新的融合方式，即设定个相似度元素的临界值，我们将所有的社团间相似度的值大于的社团进行融合，从而得到我们需要的最终结果。如图所示北京邮电大学本科毕业设计论文图改进后的找寻下对要融合的社团算法改进后我们，我们可以看到我们不必再每次随机游走后在相似度矩阵中去寻找新得到的相似度矩阵的最大值元素，因此我们可以看到经过我们改进的算法复杂度，在很大程度上的减少了。以最坏的打算，我们需要次选择融合，我们也可以将算法的复杂度从减少到。作为总结，我们提出这随机游走算法的改进，可以很有效率的将大型复杂网络进行划分，但是由于我们未知大型复杂网络的社团结构的划分，所以我们对于这种改进后的随机游走算法对大型复杂网络社团结构划分的准确度仍是未知的。随机游走算法的应用于加权网络我们上文中介绍的随机游走算法在寻找节点的邻居节点时......”。

9、“.....正如我们上面章节所述，在选择节点的所有所有邻居节点时，我们是等概率的随机的去选择节点的邻居节点中的个邻居节点。但是我们忽略了有权网络中边的权重对于我们次随机游走同属于个社团的影响。因此，在选择节点的邻居节点时，我们要加入边的权重的影响，假设节点对邻居节点的边的权重为那么我们将不再是等概率的随机选择节点的邻居节点，相反的，我们是通过权重的计算来重新给点每个邻居节点被选择的概率，如公式所示的邻居节点为北京邮电大学本科毕业设计论文同时我们可以看到，所有的邻居节点的概率的和其实为，在重新选择邻居节点时，我们便按照我们公式计算出的各自节点的概率来选择随机游走过程中的下个节点。在算法实现过程中，也进行了相应的改进如图所示图改进后的求相应节点概率的算法实现北京邮电大学本科毕业设计论文第七章总结与展望总结本次毕业设计让我收获很多，毕设中......”。