论文部分内容阅读
随着社会和信息科技的进步,人们发现了越来越多的复杂系统。为了更好地从复杂系统中得到有效信息,人们将复杂系统抽象成复杂网络。通过对复杂网络进行研究,人们已经发现复杂网络具有小世界性、无标度性和社区结构等普遍特性。其中,复杂网络中的社区结构可以表示为网络中关系紧密的节点及它们之间具有的边的集合。社区结构给人最直观的感觉就是其内部节点之间链接较为紧密而与复杂网络中的其他节点之间链接较为稀疏。由于社区结构的这种特性,使其能很容易的应用到传播控制、需求推荐、链接预测、组织架构分析等领域。因此,如何高效准确地进行社区发现成为了当今的重要研究方向。本文通过深入分析目前较新的两种社区发现算法中存在的特有问题,并有针对性的提出了对应的解决方案,从而提高了社区发现的准确性。第一,针对基于社区隶属图模型的社区发现算法在利用马尔科夫蒙特卡洛方法采样时,样本拒绝率高导致算法效率和全局最优解探测概率低的问题,利用改进的马尔科夫蒙特卡洛方法提高了算法的效率和稳定性。未改进之前的算法,在马尔科夫蒙特卡洛采样的迭代计算过程中易出现“停滞”现象,即多次迭代得到的采样结果均是相同的样本,导致得到的样本集在解空间中分布不均匀,进而影响算法效率和全局最优解的探测概率。基于此,本文提出了在马尔科夫蒙特卡洛采样方法中引入模拟回火策略,对被拒绝的样本添加第二次的接受尝试,从而增大采样的接受概率,降低了采样过程中的过高拒绝率,以提高全局最优解的探测概率与速度。最后,通过在斯坦福大学网络分析小组提供的四种真实网络数据上进行实验验证,结果表明改进方案具有可行性。第二,针对基于群集关系模型的重叠社区发现算法在通过非负矩阵分解求得社区隶属矩阵的过程中,忽略了节点自身周围的局部结构会对隶属矩阵产生影响的问题,本文拟在求解社区隶属矩阵时,充分考虑节点自身周围的局部结构并将采用节点之间结构的相似程度来具体化局部结构产生的影响。基于此,本文采用了在链接预测领域取得良好效果的四种节点间相似性算法分别融入原算法之中。最后,通过在斯坦福大学网络分析小组提供的四种真实网络数据上进行实验验证,结果表明改进之后的算法,提高了社区发现质量。