复杂网络中的重叠社区结构检测算法研究

摘要

现实世界中的很多系统都是以网络的形式存在,比如在我们人际交往中的关系网络,科研系统中的论文合著关系网,计算机的路由网络,生命科学中的蛋白质网络等等。社区结构是复杂网络一个十分重要的特性,它可以揭示社会网络的隐藏规律和行为特征。网络社区结构检测问题也成为近些年研究的热点问题,有很多社区检测算法被提了出来。
　　在实际网络中,一个节点往往不能简单的分到某一个社区中,而是被几个相互重叠的社区所共享,比如一个人可以属于科学家社区并且同时也是一个摄影师。检测网络中的重叠社区往往要比传统社区检测复杂很多。在本文中,我们围绕网络重叠社区检测问题展开,主要内容阐述如下:
　　(1)提出了一种基于多目标免疫的重叠社区检测算法。算法将重叠社区检测问题抽象为一个多目标优化问题,并利用非支配邻域免疫算法(NNIA)来对目标函数进行优化。算法通过同时优化两个相互冲突的目标函数来找到满意的社区结构。算法采用了一种新的编码方式以及交叉和变异算子,并使用非负矩阵分解来提高算法的局部搜索能力。算法不仅可以找出网络中的重叠社区,而且可以确定节点属于每个社区的隶属度。
　　(2)针对重叠社区检测问题普遍存在的计算效率过低的问题,我们提出利用GPU来提高重叠社区检测算法的运行效率。通过对贝叶斯非负矩阵分解算法进行并行化提出了P-BNMF算法。另外,针对网络邻接矩阵的存储限制问题,提出了优化版的算法Sparse-NMF算法。该算法利用CSR格式对邻接矩阵进行稀疏表示,只需要存储邻接矩阵中的非零值,以此来节省网络的存储空间。实验表明P-BNMF和 Sparse-NMF算法都可以显著提高 NMF算法的运行效率,而且 Sparse-BNMF算法可以处理更大规模的网络。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1研究背景及意义

1.2社区检测问题研究历史和发展概述

1.3本文主要工作

1.4本文的结构安排

第二章 复杂网络相关理论

2.1 复杂网络的基本概念

2.2 现有的复杂网络社区检测算法

2.3网络结构的评价指标

第三章 基于进化多目标优化与NMF的社区结构检测算法

3.1引言

3.2相关背景

3.2基于多目标免疫算法的网络重叠社区检测

3.3实验及分析

3.4本章小结

第四章 基于GPGPU平台的并行社区结构检测算法

4.1引言

4.2 GPU通用计算平台介绍

4.3 贝叶斯NMF算法

4.4 基于GPU的并行贝叶斯NMF重叠社区检测算法

4.5 Sparse-BNMF算法

4.6实验及分析

4.7本章小结

第五章 总结和展望

致谢

参考文献

硕士期间成果