关于随机游走的动态社团划分算法.doc

munity-,-detectingisanNP-,(keeptryingtofindwayout).’(푛3).Intheend,-detecting,Randomwalk,Markovchain,Lin-earequations,NormalisedLaplacianMatrixII万方数据目录中文摘要....................................I英文摘要....................................II第一章引言1第二章重要网络和社团结构划分算法介绍4网络介绍................................4算法介绍................................6社团量化标准.........................6社团发现和划分算法.....................8第三章复杂网络的动态划分算法14经典算法的局限性..........................14基于随机游走的算法.........................15基本思想和理论基础.....................15对距离矩阵的分析......................17算法流程............................19第四章算法复杂度分析和改进20复杂度分析..............................20算法的改进..............................23第五章模型测试25随机图.................................25空手道社团..............................27海豚图.................................27第六章总结与展望29参考文献30附录一程序代码33III万方数据第一章引言以计算机和因特网的普及与发展为基础的当今信息革命的爆炸式推动力无时不刻地在向我们展示着大规模的数据处理能力的重要性,从搜索引擎到人工智能都可以看到网络的重要意义。网络是用来表现事物本身与事物之间的联系的抽象出来的一种概念和工具,现实生活中的网络随处可见:如交通网络,因特网,社交网络,生物代谢网络,种群网络,关系合作网络等。而很多问题的有效解决往往取决于对复杂系统抽象出来的复杂网络的分析和挖掘。小世界(small-world)网络模型因其同时具有较小的平均路径和聚簇特性被大家所关注。这个模型是由Watts和Strogatz共同提出,它描述了介于随机图和规则图形之间的一种状态。自此之后,许多学者都发现现实中的很多复杂网络都具有这样的特性。随后Barab´asi和Albert引入了另一个模型-无标度网络。此模型很好的解释了