基于节点跟随关系的社区发现算法研究

发布时间：2021-09-22 01:08

　　社区发现的目标是将网络分成若干个社区,使得同一个社区内节点间的连接比较紧密,不同社区之间节点间的连接较为稀疏。目前大多数传统的社区发现算法仅将每个节点划分到一个社区中,但在真实世界网络中,一个节点通常属于多个社区。因此,重叠社区发现在真实世界网络中具有重要意义。传统的社区发现算法通常需要网络的全局信息,但是想要获取大规模复杂网络的全局信息往往代价高昂,甚至根本无法获得。另外,在一些实际应用中,我们可能只需要给定节点所在的局部社区,而不需要整个网络的社区结构。因此,研究局部社区发现问题具有重要意义。进一步,对于一个给定的起始节点,有时我们可能希望获得规模较小的社区,有时又希望得到规模较大的社区。因此,多尺度局部社区发现同样具有研究价值。本文对重叠社区发现、局部社区发现和多尺度局部社区发现进行了相关研究,主要内容包括以下两个方面。（1）CDFR是一个有效的非重叠社区发现算法,该算法提出了NGC节点的概念。NGC节点指距离最近的且具有较大中心度的节点。本文将CDFR算法扩展到重叠社区发现,提出了一个重叠社区发现算法OCDFR。在OCDFR算法中,首先调用CDFR算法获得一个初始的非重叠的社团... 

【文章来源】：中国科学技术大学安徽省 211工程院校 985工程院校

【文章页数】：74 页

【学位级别】：硕士

【部分图文】：

图１．２重叠社区示例图??

?－，??图１．２重叠社区示例图??传统的社区发现算法通常是对整个网络进行划分，从而得到若干个社区。因??此它们往往需要网络的全局信息，比如网络中所有的节点，边信息等等。但是对??于许多大规模复杂网络来说，想要获取其全局信息往往代价很大（或根本无法获??得）。另外，在一些实际应用中，我们可能只需要获取某一给定节点所在的那个??社区，而不是整个网络的社区结构。因此，基于网络局部信息的局部社区发现有??重要的应用价值。图１．３是一个局部社区示例图。假设我们想要获取节点２所在??的局部社区，则我们只需根据节点２的邻居节点１，３，?４，?８，?１１和它们之间的??边，即能开始进行局部社区发现，从而获得节点２所在的社区。在局部社区发现??相关研究中

?０＿８＊０＿６?０．４８??我们用一个例子来说明模糊关系值的计算方法。如图２．１所示，假设节点３??是节点１的ＮＧＣ节点，图中边上的权重表示两个节点间的公共邻居交集率，??即＂ｐ（ｌ，５）?＝?０．６，＂ｐ（５，６）?＝?０．３，＂ｐ（６，３）?＝?０．８，／＾（１，２）＝０．９，心（２，３）?＝?０．５，??＆（１，４）?＝?０．８，＆（４，３）?＝?０．６。从图２．１中可以看出，节点１到节点３之间一共有??３条路径，分别是路径ｐｐ?１－５－６－３，路径ｐ２：丨－２－３和路径１４－３。表２．１展??示了在各条路径上的模糊关系值的计算过程。从表２．１中可以看出，路径以上??的模糊关系值为０．６＊０．３＊０．８＝０．１４４，路径巧上的模糊关系值为０．９＊０．５＝０．４５，路??径ｐ３上的模糊关系值为０．８＊０．６＝０．４８。因此，从节点１到节点３的模糊关系值??ｉ？（ｌ

【参考文献】：
硕士论文
[1]局部社区发现算法研究[D]. 张道福.中国科学技术大学 2018



本文编号：3402844