基于单视图和多视图的复杂网络的社区检测研究

发布时间：2020-04-09 05:24

【摘要】：21世纪是数据爆发式增长的年代,从这些海量的数据中提取有用的信息变得越来越重要。社区结构是复杂网络的重要属性,随着复杂网络的建立,社区检测研究备受关注。传统的社区检测都试图通过各种算法来获得一个高的评价函数,模块度是广泛使用的评价函数,由于模块度自身的分辨率存在局限性,导致其社区划分结果并不理想。改进的模块度加入可调参数,避免了分辨率的限制。本文提出了基于基因算法和模拟退火算法的优化算法(Genetic Algorithm and Simulated Annealing,GASA)算法,用来提高改进的模块度的最大值。GASA算法是遗传算法和模拟退火算法的融合,该算法既具有遗传算法的全局搜索能力,又具有模拟退火算法的局部搜索能力,相比于使用单一算法优势更加明显。将GASA算法应用在实例中,以客家传统村落的社区划分为例,对客家传统村落的地理环境因素数据进行收集整理,在此基础上对数据进行数字化处理,每个村落的环境数据用12维的向量表示。复杂网络的节点代表传统村落,节点之间是否存在边,取决于节点之间环境的相似度,从而构建复杂网络。利用GASA算法,对传统村落构建的复杂网络进行社区划分,将村落划分为4个社区。传统的单视图数据较为简单,单一数据可能由于数据自身的原因,导致社区划分效果不理想。多视图数据之间可以相互补充完善,进一步提高聚类的效果,很多现实问题的解决也依赖于多视图数据,但是多视图数据的融合是一个非常复杂的过程。为了处理多视图聚类时存在的问题,我们又提出了一种新的多视图聚类算法,自动加权的半监督聚类(Auto-weighted Multi-view Semi-Supervised graph clustering,AMSS)算法,首先采用无缝集成策略将多视图数据进行集成,如拓扑结构、节点、边的属性,这些数据的集成提高了聚类效果。其次将特征属性映射到高维空间中,通过图嵌入的方式赋予每个节点一个属性函数,函数可以识别非线性特征,为每个属性分配一个权重,实现对非线性特征的选择。这样,可以将相似节点聚在一起,不相似的节点被推开。AMSS算法提出的自动加权的多视图模型,不仅实现无缝集成,还可以对这些带有属性的节点进行社区划分。在数据集上进行测试,结果表明该算法在解决多视图聚类问题时具有一定优势。
【图文】：

社区,不同参数,检测结果,算法

图 3.2 不同参数 r 值下，GASA 算法的社区检测结果 0.5，分别用 GA 算法、MA 算法、GASA 算法进行社区检值小于 0.1 时，GA 算法可以检测到真实社区；当u 的值小真实社区；当 u 的值小于 0.3 时，，GASA 算法都可以检测值增大到 0.45 开始都无法检测到真实社区，但是在 u 值小于A 算法，本文提出的 GASA 算法的社区划分效果都更好。

社区,检测结果,算法

图 3.2 不同参数 r 值下，GASA 算法的社区检测结果 0.5，分别用 GA 算法、MA 算法、GASA 算法进行社区检值小于 0.1 时，GA 算法可以检测到真实社区；当u 的值小真实社区；当 u 的值小于 0.3 时，GASA 算法都可以检测增大到 0.45 开始都无法检测到真实社区，但是在 u 值小于A 算法，本文提出的 GASA 算法的社区划分效果都更好。
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：O157.5;TP18

【参考文献】