基于重叠模块度的社区离群点检测

基于Node2Vec 的重叠社区发现算法①陈　卓, 姜　鹏, 袁玺明(青岛科技大学 信息科学技术学院, 青岛 266061)通讯作者: 姜　鹏摘　要: 针对目前基于种子节点选择的社区发现算法在准确性和复杂度等方面存在的不足, 提出了一种基于Node2Vec 的重叠社区发现算法. 首先, 使用Node2Vec 算法学习到网络中每个节点的向量表示, 用以计算节点间的相似度, 其次, 利用节点影响力函数计算节点影响力并找出种子节点, 然后基于每个种子节点进行社区的扩展优化,最终挖掘出高质量的重叠社区结构. 本文选取多个真实网络进行了对比实验, 结果表明, 本文所提出的算法能够在保证良好稳定性的前提下发现高质量的社区结构.关键词: Node2Vec; 重叠社区发现; 节点影响力; 种子节点; 社区扩展引用格式: 陈卓,姜鹏,袁玺明.基于Node2Vec 的重叠社区发现算法.计算机系统应用,2020,29(11):163–167. /1003-3254/7658.htmlOverlapping Community Discovery Algorithm Based on Node2VecCHEN Zhuo, JIANG Peng, YUAN Xi-Ming(College of Information Science and Technology, Qingdao University of Science and Technology, Qingdao 266061, China)Abstract : In view of the shortcomings in accuracy and complexity of community discovery algorithm based on seed node selection, a Node2Vec overlapping community discovery algorithm is proposed. First, the vector representation of each node in the network is learned by using Node2Vec algorithm to calculate the similarity between nodes. Second, the node influence function is used to calculate the node influence and find out the seed node. Then the community extension optimization is carried out based on each seed node. Finally the high quality overlapping community structure is excavated. In this study, several real networks are selected for comparative experiments, and the results show that the proposed algorithm can find high quality community structures under the premise of ensuring sound stability.Key words : Node2Vec; overlapping community discovery; node influence; seed node; community expansion现实世界中的很多系统都可以被抽象为复杂网络,如社交网络、技术网络、生物网络, 这些网络都具有一种普遍的特性——社区结构. 在不同类型的网络中,社区有着不同的含义, 但是所有社区内部节点间的联系总是比不同社区节点间的联系密切, 准确地发现社区结构是在中观层面上理解复杂网络进而研究复杂系统的有效途径.社区发现的研究历史可以追溯到1927年, Rice 等基于投票模式的相似性发现小的政治团体中的社区[1]. 早期的研究工作大部分都围绕非重叠社区发现展开, 此类算法将复杂网络划分成若干个互不相连的社区结构且一个节点只能隶属于一个社区[2]. 然而, 现实中网络社区之间往往是相互重叠的, 硬划分的社区发现算法无法满足需求, 例如, 在社交网络中, 如果每个社区代表拥有共同兴趣爱好的用户所组成的群体, 则一个用户可以拥有诸多兴趣爱好而隶属于多个社区,计算机系统应用 ISSN 1003-3254, CODEN CSAOBNE-mail: Computer Systems & Applications,2020,29(11):163−167 [doi: 10.15888/ki.csa.007658] ©中国科学院软件研究所版权所有.Tel: +86-10-62661041① 基金项目: 国家自然科学基金(F030810); 山东省重点研发计划(2018GGX101052)Foundation item: National Natural Science Foundation of China (F030810); Key Research and Development Program of Shandong Province (2018GGX101052)收稿时间: 2020-03-12; 修改时间: 2020-04-12, 2020-04-29; 采用时间: 2020-05-10; csa 在线出版时间: 2020-10-29163显然, 重叠的社区结构更能体现出复杂网络的特性, 进而帮助我们从中观层面对复杂系统进行分析.对复杂网络中重叠社区的发现与研究也因此成为近年来新的研究热点, 而社区发现作为社区分析相关工作的前提, 对于其他领域的研究有着重要影响. 目前,重叠社区的发现结果可以被应用于情感分析、个性化推荐、实体消歧和链接预测等领域的研究.1 相关工作近年来, 学者们相继提出大量能够识别重叠社区的算法. Palla等提出一种基于最大团的派系过滤算法CPM来分析重叠的社区结构[3], 该算法易受k值影响,且以最大团为种子的方式计算复杂度较高. COPRA算法[4]对基于标签传播的非重叠社区发现算法进行改进,在标签后面附上节点对该标签的归属系数, 以便衡量该节点包含多个社区的信息比重, 在迭代更新节点标签的过程中允许一个节点同时拥有多个标签, 以发现网络中的重叠社区, 该算法每次迭代的时间复杂度接近线性但稳定度较差. 基于链路的重叠社区发现算法首先对网络的边进行聚类, 然后通过收集链路社区内的所有连接的节点进行社区划分, 代表算法为LINK 算法[5]. 在此基础上, Li等[6]提出一种基因表示模型,通过将链路社区映射成节点社区的方式, 实现对重叠节点的发现. 基于局部社区优化和扩展的方法则从局部社区出发, 基于优化函数进行扩张, 社区间的交叉部分则为重叠节点, 代表算法为LFM算法[7], 除此之外, Su等[8]提出利用随机游走策略扩展优化的方法. 文献[9]在此基础上提出基于种子节点选择的重叠社区发现算法, 首先通过定义的影响力函数选取种子节点, 然后通过吸引力函数以种子节点为核心进行扩展, 发现种子所在的局部社区结构. 其中, 基于种子节点选择和扩展的算法由于稳定性好、效率高而成为主流的社区发现算法. Wang等[10]提出一种基于结构中心性的种子选择算法, 实现了一个高覆盖率的朴实算法, 提高了社区发现质量, 但算法不能很好地适用于大规模数据集. 於志勇等提出的i-SEOCD算法能够高效地从种子节点出发进行局部扩展, 最终发现稳定的重叠社区[11], 但是该算法在计算节点相似度时只考虑了局部网络, 提高算法执行效率的同时也牺牲了算法准确性.现有基于种子节点扩展的重叠社区发现算法虽然在稳定性方面表现较好, 但在衡量两节点间关系时, 往往将两节点间是否有连边作为唯一判别标准, 而只考虑狭小作用域范围内的局部信息的做法, 虽然提升了社区发现的效率, 但忽略了网络中更大范围内节点和边因素对社区发现过程的影响, 使得算法在提升效率的同时往往以牺牲部分准确性为代价. 同时, 现有算法在基于种子节点进行社区扩展的过程中, 往往需要不断地迭代计算现有社区与未划分节点间的相似性关系,计算量大, 不适合进行大规模网络的社区发现.为了更好地解决以上问题, 本文利用Node2Vec[12]算法对网络结构进行学习, 通过控制在游走产生节点序列过程中对深度优先和广度优先的趋向, 将更大范围内的拓扑结构信息体现到节点因素中, 提出了基于Node2Vec的重叠社区发现算法, 该算法能够解决现有算法存在的以牺牲准确性来提高效率和不适合大规模数据集的问题.2 基于Node2Vec的重叠社区发现算法针对以Jaccard相似度为指标衡量节点间距离的方法所存在的局限性, 本文采用网络表示学习算法学习到网络中每个节点的向量表示, 针对传统种子节点选择方法稳定性和鲁棒性差的缺点, 提出了新的种子节点选择算法, 并以此为基础进行社区扩张和优化. 2.1 Node2Vec算法Perozzi等[13]提出了将Word2Vec的思想用于图节点表示学习的Deepwalk算法, Node2Vec在此的基础上改变了随机游走的序列生成方式, 通过半监督的方式学习p, q两个超参数的值, 控制游走对深度和广度的趋向, 其中p控制跳向前节点邻居的概率, q控制跳向前节点非邻居的概率, 如图1所示.x1x3x2tVα=1α=1/qα=1/qα=1/q图1 随机游走过程图q>1x1p>1x2x3图1中, 时, 趋向于遍历临近t节点的节点,即趋向于BFS; 时, 趋向于遍历临近t节点的或节点, 即趋向于DFS. 在确定要遍历的邻居节点之后,采用skip-gram模型进行训练进而获得节点的向量表示.u v在进行种子节点发现前, 首先利用Node2Vec算法对网络结构进行学习, 在学习到网络中每个节点的向量表示后, 对于任意节点和, 可利用算法内置的相似计算机系统应用2020 年 第 29 卷 第 11 期164sim (u ,v )A n ×n A uv u v 1−sim (u ,v )度计算工具计算其在高维空间中的相似度, 其取值范围为0~1, 通过该方式进一步计算网络中任意节点之间的相似度, 并用相似度矩阵表示整个网络中节点间的相似度信息, 其中表示节点和之间的相似度, 进而可以用来表示节点间的相异度.2.2 种子节点选择算法G =(V ,E )通常, 一个网络可以用无向图表示, 其中V 表示图中n 个节点的集合, E 表示图中m 条边的集合.在网络中, 节点u 的邻居集合N(u)定义如下:N (u )={u :v ∈V ,(u ,v )∈E }(1)节点u 对节点v 的影响力用F(u,v)表示如下:F (u ,v )=D (u )D (v )(1−sim (u ,v ))2(2)sim (u ,v )1−sim (u ,v )其中, D (u )和D (v )分别表示节点u 和v 的度, 表示u , v 节点的相似度, 可通过Node2Vec 生成的节点向量计算得到, 表示为两节点间的距离, 距离越远, u 对v 的影响力越小.节点u 的影响力值通过以下公式计算得到:F (u )=∑v ∈N (u )D (u )D (v )(1−sim (u ,v ))2(3)节点影响力的大小与其邻居节点的数量、度数以及相异度有关, 影响力越大, 节点越有机会成为种子节点.在种子节点选择算法中, 首先根据节点的向量计算所有节点的影响力值, 如果某节点的影响力值比其所有邻居节点的影响力值都大, 则将该节点加入到种子节点的集合中. 算法1中列出了种子节点选择算法的伪代码, 其中2–4行利用定义的节点影响力计算公式计算出每个几点的影响力值, 5–9行将每个节点的影响力值与其所有邻居的影响力值进行比较, 若邻居节点中没有比当前节点影响力值大的节点, 则将该节点加入到种子节点集合中.算法1. 种子节点选择算法G =(V ,E )A n ×n 输入: 无向图; 相似度矩阵.输出: 种子节点集合S.S ←∅1. u ∈V2. for do3.　利用式(3)计算F(u)4. end for ∈5. for u V do∀v ∈N (u )F (u )≥F (v )6.　if and S ←S ∪u 7. 8.　end if 9. end for 10. return S2.3 社区扩展算法ε针对现有算法在社区扩张过程中重复计算量大的问题, 本文在得到分布均匀、影响力大的种子节点之后, 充分利用前一阶段计算所得的节点相似度矩阵, 从每个种子节点出发进行社区扩展, 首先, 以集合中的每个种子节点为核心构建社区, 若节点与种子节点的相似度大于阈值, 则将该节点划入该种子节点所属的社区, 然后, 对于尚未被划分的节点, 比较其与各个种子节点的相似度, 选取与之最相似的种子节点, 加入其所在社区, 最终完成社区的划分.εε算法2中列出了社区扩展算法的伪代码, 2–4行首先将所有节点标记为false, 5–13行分别以每个种子节点为核心进行社区扩展, 并将被划分的节点标记为true,此过程中以各节点为核心的社区独立进行扩展, 能够很好地根据阈值的大小控制重叠节点的规模, 阈值越小, 发现重叠节点的几率越大, 14–19行将一轮划分结束后没有归属的节点分离出来, 20–25行则对标记为false 的节点进行处理, 选择与之相似度最高的种子节点所在的社区作为其社区归属, 最终经过两个阶段的处理, 得到最终的社区.算法2. 社区扩展算法G =(V ,E )A n ×n 输入: 无向图; 相似度矩阵; 种子集合S.输出: 社区结构C.C ←∅1. u ∈V2. for doLabel (u )=false 3.　4. end for5. for seed in S doCS ←∅,CS ←CS ∪{seed }6.　u ∈V u S 7.　for and A [seed ][u ]≥ε8. if CS ←CS ∪{U }Label (u )=true 9. ,10. end if 11.　end for C ←C ∪CS 12.　13. end for R ←∅14. 15. for node in VLabel (node )=false16.　if R ←R ∪{node }17. 18.　end if 19. end for R20. for v in 21.　for seed in SA [seed ][v ]22. CS_num = argmax 23.　end forCS ←CS ∪{v }Label (v )=true 24.　, 2.5 end for 26. return C2020 年 第 29 卷 第 11 期计算机系统应用165εεk ×n 2×k ×n k n k <<n O (n )O (n log n )通常情况下, 选择合适的阈值能够使得大部分节点经过第一阶段的处理能够划入相应的社区, 阈值越小, 需要进行第二阶段处理的节点越少, 但也会导致社区之间重叠度很高. 本文在基于种子节点进行社区扩展的过程中, 充分利用前阶段的计算结果, 将迭代更新的过程简化成了寻址过程, 完美状态下, 只需进行次计算即可完成社区检测, 最坏情况下, 则需进行次计算, 其中表示种子节点个数, 表示网络中节点的个数, 且二者间满足, 总体复杂度为,优于现有的时间复杂度为的社区扩展算法.综上, 基于Node2Vec 的重叠社区发现算法整体流程大致分为以下3个步骤:n ×n 首先, 利用NodeVec 算法对网络结构进行学习, 得到包含丰富拓扑结构信息的节点的向量表示, 基于节点向量值计算每对节点间的相似度, 用一个阶矩阵来表示网络结构中所有n 个节点间的相似度值.然后, 利用前一阶段计算得到的节点相似度, 根据定义的节点影响力公式筛选出能够独立领导社区的种子节点集合.最后, 以种子节点为核心, 分阶段进行社区扩展,首先通过比较每个种子节点与所有非种子节点间相似度与给定阈值的大小关系初步扩展社区, 然后对于未被划分的节点, 选择与之相似度最大的种子节点, 划入其所属社区, 直至所有节点都有至少一个社区归属, 重叠社区检测完毕.3 实验为验证算法的相关性能, 在多个不同规模的真实数据集上与其他经典重叠社区发现算法进行对比实验, 待比较的算法分别是CPM 、LINK 、COPRA 和LFM 算法.3.1 实验数据集分别选取不同类型不同数量级的5个真实网络数据集, 具体包括美国空手道俱乐部网络Karate [14]、海豚关系网Dolphins [15]、大学生足球联赛网络Football [16]、欧洲研究机构电子邮件网络Email-EU [17]和高能物理范畴论文引用关系网Ca-HepPh [18], 各网络规模如表1.3.2 评价指标由于社区划分没有标准的结果, 对于真实数据集,Newman 提出的模块度函数[19]被广泛认可, 但该评价标准并不能很好地适用于重叠社区, Shen 等在此基础上提出了能衡量重叠社区划分结果的重叠模块度函数[20],定义如下:EQ =12m ∑i ∑u ∈c i,v ∈c i1Q u Q v [A uv −k u k v2m](4)m A k u u Q u u 其中, 表示网络中的总边数, 为网络的邻接矩阵,为节点的度数, 表示节点所属的社区数量.表1 真实数据情况表数据集节点边Karate 3478Dolphins 62159Football 115616Email-EU 100525 571Ca-HepPh12 008118 5213.3 实验结果εεεh =0.1ε本文提出的算法在基于种子节点进行社区扩展时,社区划分结果易受阈值大小的影响, 故首先在不同数据集上在不同阈值的指引下进行社区划分, 通常情况下阈值的取值范围为0.3~0.7, 取步长进行实验,社区划分结果随阈值大小改变而变化的情况如图20.550.500.450.400.350.300.300.350.400.450.500.550.600.650.70E Q 值Karate Dolphins Football Email-EU Ca-HepPh阈值图2 重叠模块度随阈值变化图ε=0.5ε从图2可以看出, 在不同数据集上, 模块度总是在左右的位置取到峰值, 这也说明阈值对划分结果的影响趋势在所有数据值上是大致相当的.ε=0.5将本文算法与其他4个经典的重叠社区发现算法在不同规模不同类型的数据集上进行对比实验(阈值取), 结果如表2所示.在大多数数据集上, 本文算法均取得了最高的模块度值, 尤其是在Emai-EU 和Ca-HepPh 两个大规模的数据集上, 分别取得了接近0.5和0.4重叠模块度值,所发现的社区质量明显优于其他算法, 实验证明, 使用Node2Vec 算法将更大作用域范围内的网络信息映射到节点向量中的方式, 能够有效地避免范围限制所带来的准确率方面的牺牲, 提升社区发现质量, 在规模大、结构复杂的网络上, 提升效果格外显著.计算机系统应用2020 年 第 29 卷 第 11 期166表2 真实数据集对比结果表算法Karate Dolphins Football Email-EU Ca-HepPh CPM 0.1870.3620.5600.3750.292Link 0.1590.0030.0100.1130.132COPRA 0.3420.4820.4850.4030.328LFM 0.3170.3450.5720.4310.363本文算法0.4150.4840.5630.4940.3924 结论与展望本文提出了一种基于Node2Vec 的重叠社区发现算法, 首先获得网络结构的向量表示并计算节点之间的相似度值, 利用定义的影响力函数选择出种子节点,然后以每个种子节点为核心进行社区扩张. 本文选取了不同类型不同规模的真实网络数据集, 并在这些数据集上将本文算法与其他类经典重叠社区发现算法进行对比性实验, 实验结果表明, 本文算法在大部分数据集尤其是大规模数据集上表现出了明显的优势. 后续工作将提高算法的性能, 降低算法复杂度, 并将算法应用到动态社区发现研究中.参考文献Rice SA. The identification of blocs in small political bodies.American Political Science Review, 1927, 21(3): 619–627.[doi: 10.2307/1945514]1骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究新进展. 国防科技大学学报, 2011, 33(1): 47–52. [doi: 10.3969/j.issn.1001-2486.2011.01.011]2Palla G, Derényi I, Farkas I, et al . Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814–818. [doi:10.1038/nature03607]3Gregory S. Finding overlapping communities in networks by label propagation. New Journal of Physics, 2010, 12(10):103018. [doi: 10.1088/1367-2630/12/10/103018]4Ahn YY, Bagrow JP, Lehmann S. Link communities reveal multiscale complexity in networks. Nature, 2010, 466(7307):761–764. [doi: 10.1038/nature09182]5Li MM, Liu J. A link clustering based memetic algorithm for overlapping community detection. Physica A: Statistical Mechanics and its Applications, 2018, 503: 410–423. [doi:10.1016/j.physa.2018.02.133]6Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 2009, 11(3): 033015.[doi: 10.1088/1367-2630/11/3/033015]7Su YS, Wang BJ, Zhang XY. A seed-expanding method based on random walks for community detection in networks8with ambiguous community structures. Scientific Reports,2017, 7: 41830. [doi: 10.1038/srep41830]齐金山, 梁循, 王怡. 基于种子节点选择的重叠社区发现算法. 计算机应用研究, 2017, 34(12): 3534–3537, 3568. [doi:10.3969/j.issn.1001-3695.2017.12.003]9Wang XF, Liu GS, Li JH. Overlapping community detectionbased on structural centrality in complex networks. IEEEAccess, 2017, 5: 25258–25269. [doi: 10.1109/ACCESS.2017.2769484]10於志勇, 陈基杰, 郭昆, 等. 基于影响力与种子扩展的重叠社区发现. 电子学报, 2019, 47(1): 153–160. [doi: 10.3969/j.issn.0372-2112.2019.01.020]11Grover A, Leskovec J. Node2Vec: Scalable feature learningfor networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco, CA, USA. 2016. 855–864.12Perozzi B, Al-Rfou R, Skiena S. DeepWalk: Online learningof social representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA. 2014. 701–710.13Zachary WW. An information flow model for conflict andfission in small groups. Journal of Anthropological Research,1977, 33(4): 452–473. [doi: 10.1086/jar.33.4.3629752]14Lusseau D, Schneider K, Boisseau OJ, et al . The bottlenosedolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 2003, 54(4): 396–405. [doi: 10.1007/s00265-003-0651-y ]15Girvan M, Newman MEJ Newman. Community structure insocial and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002,99(12): 7821–7826. [doi: 10.1073/pnas.122653799]16Yin H, Benson AR, Leskovec J, et al . Local higher-ordergraph clustering. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax, Nova Scotia, Canada. 2017. 555–564.17Leskovec J, Kleinberg J, Faloutsos C. Graph evolution:Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 2. [doi:10.1145/1217299.1217301]18Newman MEJ, Girvan M. Finding and evaluating communitystructure in networks. Physical Review E, 2004, 69(2):026113. [doi: 10.1103/PhysRevE.69.026113]19Shen HW, Cheng XQ, Cai K, et al . Detect overlapping andhierarchical community structure in networks. Physica A:Statistical Mechanics and its Applications, 2009, 388(8):1706–1712. [doi: 10.1016/j.physa.2008.12.021]202020 年 第 29 卷 第 11 期计算机系统应用167。

基于图嵌入和多标签传播的重叠社区检测算法
高兵;宋敏;邹启杰;秦静
【期刊名称】《计算机应用研究》
【年(卷),期】2024(41)5
【摘要】为进一步优化重叠社区检测算法,提出了一种新的基于度和节点聚类系数的节点重要性定义,按照节点重要性降序更新节点,固定节点更新策略,提高社区检测的稳定性。

在此基础上,提出了一种基于图嵌入和多标签传播的重叠社区检测算法(overlapping community detection based on graph embedding and multi-label propagation algorithm,OCD-GEMPA)。

该算法结合node2vec模型对节点进行低维向量表示,构建节点之间的权重值矩阵,根据权重值计算标签归属系数,据此选择标签,避免了随机选择问题。

在真实数据集和人工合成数据集上对该算法进行实验验证。

实验结果表明,与其他重叠社区检测算法相比,OCD-GEMPA在EQ和NMI这两个指标都有明显提升,具有更好的准确性和稳定性。

【总页数】6页(P1428-1433)
【作者】高兵;宋敏;邹启杰;秦静
【作者单位】大连大学信息工程学院;大连大学大连市智慧医疗与健康重点实验室;大连大学软件学院
【正文语种】中文
【中图分类】TP391
【相关文献】
1.一种基于完全子图与标签传播的重叠社区检测算法
2.基于节点亲密度的标签传播重叠社区发现算法
3.一种基于标签传播的重叠社区发现算法
4.基于标签传播的重叠社区检测算法
5.基于标签传播与多指标的重叠社区检测算法
因版权原因，仅展示原文概要，查看原文内容请购买。

复杂网络模糊重叠社区检测研究进展肖婧;张永建;许小可【期刊名称】《复杂系统与复杂性科学》【年(卷),期】2017(014)003【摘要】模糊重叠社区检测通过扩展隶属度取值空间,实现了重叠节点与社区之间复杂且模糊隶属关系的精确化测量,不仅能够有效提升重叠社区结构检测的精确性,而且能够深度挖掘出节点和社区的重叠特性.文中首先分析了模糊重叠社区检测与传统离散重叠社区检测的关系;然后对二者的国内外相关研究现状进行阐述和分析,其中在模糊重叠社区检测方法研究中根据模糊隶属度获取方式的不同将当前相关研究分为扩展标签传播、非负矩阵分解、基于边界节点的两阶段检测、模糊聚类、模糊模块度优化五大类进行综述,重点分析了基于进化算法的模糊模块度优化方法;最后对模糊重叠社区检测研究未来的发展趋势进行了分析和展望.【总页数】22页(P8-29)【作者】肖婧;张永建;许小可【作者单位】大连民族大学信息与通信工程学院,辽宁大连116600;大连民族大学信息与通信工程学院,辽宁大连116600;大连民族大学信息与通信工程学院,辽宁大连116600;贵州省公共大数据重点实验室贵州大学,贵阳550025【正文语种】中文【中图分类】TP399【相关文献】1.采用模糊层次聚类的社会网络重叠社区检测算法 [J], 李刘强;桂小林;安健;孙雨2.复杂网络中重叠社区检测 [J], 张振宇;张珍;杨文忠;吴晓红3.复杂网络大数据中重叠社区检测算法 [J], 乔少杰;韩楠;张凯峰;邹磊;王宏志;Louis Alberto GUTIERREZ4.云计算模型下复杂网络重叠社区检测方法研究 [J], 王娅5.利用非重叠CD生成解的集成重叠社区检测 [J], 陈吉成; 陈鸿昶; 李邵梅因版权原因，仅展示原文概要，查看原文内容请购买。

离群点检测（异常检测）是找出其行为不同于预期对象的过程，这种对象称为离群点或异常。

离群点和噪声有区别，噪声是观测变量的随机误差和方差，而离群点的产生机制和其他数据的产生机制就有根本的区别。

全局离群点：通过找到其中一种合适的偏离度量方式，将离群点检测划为不同的类别；全局离群点是情景离群点的特例，因为考虑整个数据集为一个情境。

情境离群点：又称为条件离群点，即在特定条件下它可能是离群点，但是在其他条件下可能又是合理的点。

比如夏天的28℃和冬天的28℃等。

集体离群点：个体数据可能不是离群点，但是这些对象作为整体显著偏移整个数据集就成为了集体离群点。

离群点检测目前遇到的挑战•正常数据和离群点的有效建模本身就是个挑战；•离群点检测高度依赖于应用类型使得不可能开发出通用的离群点检测方法，比如针对性的相似性、距离度量机制等；•数据质量实际上往往很差，噪声充斥在数据中，影响离群点和正常点之间的差别，缺失的数据也可能“掩盖”住离群点，影响检测到有效性；•检测离群点的方法需要可解释性；离群点检测方法1. 监督方法训练可识别离群点的分类器；但是监督方法检测离群点目前遇到几个困难：1.两个类别（正常和离群）的数据量很不平衡，缺乏足够的离群点样本可能会限制所构建分类器的能力；2.许多应用中，捕获尽可能多的离群点（灵敏度和召回率）比把正常对象误当做离群点更重要。

由于与其他样本相比离群点很稀少，所以离群点检测的监督方法必须注意如何训练和如何解释分类率。

One-class model，一分类模型考虑到数据集严重不平衡的问题，构建一个仅描述正常类的分类器，不属于正常类的任何样本都被视为离群点。

比如SVM决策边界以外的都可以视为离群点。

2.无监督方法正常对象在其中一种程度上是“聚类”的，正常对象之间具有高度的相似性，但是离群点将远离正常对象的组群。

但是遇到前文所述的集体离群点时，正常数据是发散的，而离群点反而是聚类的，这种情形下更适合监督方法进行检测。

一种快速检测重叠社区的方法王一萍【摘要】在分析现实世界网络时,发现功能类似个体的自然群体是一个关键任务.在社会和生物网络中社区间的重叠是常见的,事实上,社区间的重叠密度比社区内非重叠区域重叠密度要大.现大多数检测重叠社区算法假设社区比周围区域密集,错误地将重叠部分识别为社区.而这些算法大多计算量大,不能合理地随网络大小而改变.提出了快速搜索重叠社区算法(fast search overlapping communityalgorithm,FSOCA),一种基于局部连接考虑的重叠社区识别算法.实验结果表明,FSOCA在计算时间上优于一些流行的重叠社区检测算法,且不影响质量.【期刊名称】《高师理科学刊》【年(卷),期】2018(038)007【总页数】5页(P28-31,36)【关键词】重叠社区;社会网络;局部连接;复杂网络【作者】王一萍【作者单位】齐齐哈尔大学计算机与控制工程学院,黑龙江齐齐哈尔 161006【正文语种】中文【中图分类】TP313社会网络由有限个体及它们之间链接组成．一个连接基于他们共同的兴趣、工作或犯罪伙伴关系等联系起来，这种联系出现或消失复杂性形成有意义拓扑结构．同时，网络通常是巨大的，从而阻止了应用大多数图理论算法．分析社会网络意图是新颖和可伸缩计算帮助下对大型复杂网络产生有用见解．在一社会系统中，个体倾向于与其志同道合人或交往更频繁人形成小组，比与其他人密切，导致社区形成．社区中成员是紧密相连，属于不同社区成员间交互少．此外，不同领域有共同兴趣和目的人形成重叠社区．社区的识别有许多实际应用，如电信服务提供商会采取措施留住特定社区内有重要联系的消费者．商业网站可通过增加某些社区内销售提供市场，通过小部分有影响力人，可很容易将一个信息进行传播．事实上，可以很容易做到局部发布信息传播到大量人群中，如政治观点信息、自然灾害及新媒体等通过社交网络迅速传播．网络通常由数百万节点和数十亿边组成，需快速而高效方法从大规模网络中挖掘有用信息，需要考虑到节点局部信息，算法除快速还要克服内存的限制．本文提出了基于局部连接分数计算的大型网络重叠社区搜索算法，该方法已应用于多个大型社会网络和生物网络中．将被检测到的社区与各对应网络社区进行了比较，并与一些流行重叠社区检测算法相比，FSOCA在时间和效率方面表现都良好．社区检测的问题是识别出自然存在的群体，群体中节点连接紧密，不同组节点连接稀疏．社会团体从拓扑角度说是图群，而一般说，图聚类只适用于比社会网络小的网络．图聚类是优化问题，在计算上难以解决．社会网络要求有更快的算法在大网络上能够很好地使用．文献[1]中有许多图聚类方法，探索边划分社区．另外，局部优化法通过优化描述局部拓扑结构参数的适应度函数来实现最优解．将社区检测简化为局部优化更有说服力．如已提出的定义局部适应度分数[2]，是指位于社区内节点邻接点分数．标签传播算法（LPA），而COPRA[3]修改LPA，以找到重叠社区．在SLPA中，当发送节点发送最多可能的标签时，这种方法可帮助一个节点根据收到标签概率信息决定它在每个社区强度．尽管提到的方法简单且很快，但大多是发现非重叠集群的[4]．发现重叠集群算法主要是计算上的限制，使算法不适用于大型真实网络．FSOCA是一种快速进化算法，在一些局部计算分数基础上发现重叠社区，在规模超大的社交网络扩展很好．通过增加选择多个接近社区，不仅是最好社区，而且也节省迭代．此外，该方法检测到的社区不局限于层次结构，结果不依赖节点的顺序．给定一个无向未加权图，社区检测问题是找到子图集，对于中任意节点在中比与其他有更多连接．是集合中不含节点的子图，每个是一社区．对于每个节点，和的定义其中：是含的社区集；是不含社区集．如每个恰属一个社区，则为分离社区，否则称重叠社区．本文提出了在给定图中发现重叠集群OCFS算法．每个节点与中任何社区比与任何社区有更好连接，因此，需确定与中所有社区都有很好连接，这是FSOCA工作原理．设是节点邻接点集，描述为设是在社区中邻接点（），即与节点在同一社区邻接点集合，描述为FSOCA定义关于一个节点与它所在社区的连接度．因此如一个顶点与社区中大多数节点连接，它就被认为其在社区内连通性很好．对每个节点所属每个社区对应一个社区连通性得分为确保一个节点在任何社区中至少有个邻接点，修改式（5）得社区联系得分如值非常大，那么会忽略小而密集社区；如值非常小则会发现稀疏大社区．结果表明，该算法对低值不敏感，且对= 2大小不同网络有较好一致性．算法还为每个节点关于它所在的社区定义了邻接点连通性得分，是对在社区中节点邻接点个数与所有邻接点之比此分数强调节点邻接点出现在社区中比例．须指出社区连通性分数决定了节点对其社区的归属，而邻接点连通性得分只定义节点加入新节点的兴趣社区．FSOCA的原则是社区由个体发起，并受到它们邻接点和邻接社区影响．一个节点吸引其邻近个体成为其社区一部分，那些找到足够连接个体可能会选择留下来．在新添加成员迭代过程之后，社区进一步扩展．2.3.1 初始社区最初每个节点和它至少个邻接点一起构建一个社区．因此，社区数等于度数大于或等于的节点数，这样每个节点都成为由它和它邻接点初始社区的成员，允许初始社区之间重叠．这种方法进一步实现了一个节点可参与多个社区，可以同时选择留在不止一个具有高连接度分值的社区，而离开其他的社区．设初始社区结构表示为，此外，设，被定义为的外围节点集．该算法将迭代２个阶段：离开阶段和扩展阶段．设包含这２个阶段的每个迭代被称为一个stage．另外，在stage 后得到的社区结构被表示为，很重要的是，它始终是任何社区的外围节点，这些节点要在接下来的阶段中要么离开，要么扩展．2.3.2 离开阶段在此阶段，当节点发现它在所在社区中没有足够连接时，将会离开这个社区．每个节点分配分数和，由式（6）、式（7）给出．因此，为每个节点所参与的社区结构中的任何社区，得到社区连通分数列表和邻居连通分数列表．如一个节点社区连通性分值大于一定界限分，它就被认为在对应社区中有足够连通性，称这个界限为保留界限，它是从社区连通性评分列表中计算得到的．本文采用类似于桶的方法，快速确定保留界限．对于所有社区的每一个外围节点，如果它的社区连通分数低于它的保留界限，则离开社区．移走仅有的外围节点才能确保构成一个社区核心的节点永远不会被消除．然而，少于个节点的任何社区都被认为是无关紧要的，并且被清除．对整个社区计算分数及和移走外围节点执行递归，直到没有节点离开任何社区．2.3.3 扩展阶段在离开阶段后，将继续扩展社区到其邻近节点．因此，在每个社区的外围节点集中包括每个相邻节点，如果具有条件：（1）节点还没有包含在社区中；（2）节点对加入这个社区非常感兴趣，则将此节点加入该社区中．加入一个新社区兴趣高是通过高的邻居连通性分数描述的，确保一个节点邻居连通性分数高，分数大于其加入界限．加入的计算是从邻居连通性分数列表，计算方法类似于保留界限的求法．在此之后，将包含的新添加节点，以便在下一阶段进行移走或扩展．一方面，只有外围节点扩展允许重新包含被删除的节点；另一方面，需要注意在社区中不适合的节点不会重复添加，并在离开阶段被删除，它也有助于FSOCA 的收敛．在扩展阶段之后，此阶段所获得社区结构作为输入传递到下一个阶段的离开阶段．如果在某阶段的某些特定社区的所有外围节点在离开阶段被移除，则这些社区在后面阶段不能进一步扩大，但这些社区仍为其节点连接得分列表提供帮助．在一个阶段中，当所有现有的社区中没有外围节点时FSOCA停止．2.3.4 删除重复社区重叠社区的检测算法允许网络中几乎所有节点都成为其他社区的一部分．这是因为每个初始社区都可以扩展加入新节点，而不考虑这些节点是否在其他社区中，所以在每个阶段某些社区可能会发展成为接近重复的社区．接近重复的社区对确定通过相似度量定义在每个阶段都执行删除重复社区，在把社区传递给离开阶段之前，并在每次迭代之后进行．从2种观点来看，重复删除是很重要的：（1）这防止了分数分布不受期望的倾斜；（2）删除了一些接近重复的社区，计算时间也减少了．在FSOCA中，重复删除过程将参数OVL作为输入．在2个社区被识别为接近时，设置OVL为2个社区之间允许的最大重叠阈值，当相似度测量值超过这个阈值时，删除2个社区中较小的．当OVL=1时意味着当2个社区完全相同时消除其中一个．合理的阀值设置为：，本文取OVL=0.6，并试验了不同的OVL值，观察在0.5~0.7范围内的定性条件下输出的稳定性．评估一种社区检测算法的性能可在真实和模拟网络上进行，而模拟网络没有捕捉到与真正网络社区结构相关的重要特征[5-6]．本文只在真实网络上评估FSOCA性能．为验证在大型真实网络上FSOCA性能，在3个大型真实网络上对FSOCA进行评价，网络是无向无权的．Amazon是亚马逊产品联合采购无向网络[7]．产品类别是分层嵌套，对应网络本质上组织为重叠社区结构，在同一层社区产品共享相同功能．DBLP 计算机科学协作网络，如果2名作者一起至少发表一篇论文，他们就会联系在一起．这样网络中成员之间的关系是与研究领域相关的，因此社区高度重叠很自然．Human PPIN人类蛋白质间质是由计算分析部分的结果所收集的PCDq数据集[8-10]，它提供交互网络，也提供复合物（用DBClus进行了实验验证和计算预测）．使用9 268种蛋白质32 198个相互作用网络，人类蛋白复合物数据集含1 078个复合物，构成3 759个蛋白质．只考虑有属于第一类或第二类复合体，这些是经实验验证大量蛋白质复合物．本文采用NMI（标准互信息表）评估划分社区的质量，为评价本文算法，将其与较有名的算法：MOSES，GCE，CORPA，SLPA进行对比．实验结果对比见表1．社会网络是复杂而庞大的，FSOCA通过只选择那些所有都局部连通较好的节点来快速探索社区．在整个算法中计算每个节点的社区连接和邻域连接得分，反映了真实世界的社区属性，这使得该算法适用于大小不等的真实网络．用户可以自由设置任意两个社区之间允许的最大重叠阀值，以及节点应该拥有的最小邻居数量，以确定其在任何社区中的成员．FSOCA的一个局限性是，可以通过该方法检测到的最大社区数量等于网络中节点的数量．而在社会网络中，社区的数量实际上可以是节点数量的２倍．当允许一个节点创建多个社区时，就会发生这种情况，试图在今后的工作中解决这个问题．此外，还希望扩展该方法以使用加权和/或定向网络、动态网络等．【相关文献】[1] Xie J，Kelley S，Szymanski B K．Overlapping community detection in networks：The state-of-the-art and comparative study[J]．ACM Computing Surveys，2013（4）：6521-6540[2] Chen W，Liu Z，Sun X，et al．A game-theoretic framework to identify overlapping communities in social networks[J]．Data Mining and Knowledge Discovery，2010（21）：224-240[3] Ren G，Wang X．Epidemic spreading in time-varying community networks[J]．Chaos An Interdisciplinary Journal of Nonlinear Science，2014，24（2）023116[4] Girvan M，Newman M E．Community structure in social and biologicalnetworks[J]．Proceedings of the national academy of sciences，2002，99（12）：7821-7826[5] 刘世超，朱福喜，甘琳．基于标签传播概率的重叠社区发现算法[J]．计算机学报，2016，39（4）：717-729[6] 周涛，张子柯，陈关荣，等．复杂网络研究的机遇与挑战[J]．电子科技大学学报，2014，43（1）：1-5 [7] Yang J，Leskovec J．Defining and evaluating network communities based on ground-truth[J]．Knowledge and Information Systems， 2015，42（1）：181-213 [8] 张鑫，刘秉权，王晓龙．复杂网络中社区发现方法的研究[J]．计算机工程与应用，2015，51（24）：1-7[9] 李磊，倪林．基于模块度优化的标签传播社区发现算法[J]．计算机系统应用，2016，25（9）：212-215[10] 石梦雨，周勇，邢艳．基于LeaderRank的标签传播社区发现算法[J]．计算机应用，2015，35（2）：448-451。

基于节点尺度特征的重叠社区检测算法张黎烁;高继勋【摘要】针对社会网络中重叠社区检测问题,在节点尺度特征下量化社区结构,用这些特性更易界定社区划分.利用合理假设来量化节点尺度的期望值,基于节点描述符集和谱算法建立算法模型,从而提出一种重叠社区检测算法.该方法允许节点同时属于多个社区,在社区重叠时同样可行.通过计算验证,算法对于整体边缘密度都有效.在2类网络中实验的结果表明,该算法在重叠社区检测中性能稳定、准确性高,能适用于目标特定的社区概念.【期刊名称】《河南理工大学学报（自然科学版）》【年(卷),期】2016(035)005【总页数】7页(P706-712)【关键词】重叠社区检测;社会网络;节点尺度;边缘描述符集;自我中心网【作者】张黎烁;高继勋【作者单位】河南工程学院计算机学院,河南郑州451191;河南工程学院计算机学院,河南郑州451191【正文语种】中文【中图分类】TP391现实生活中许多系统都以网络形式体现，如社会关系网络、通信网络、生物体系网络等。

为便于分析系统内部结构，网络系统可用图论相关模型表示。

用节点表示系统中的个体，边表示个体间连接关系。

系统中具有相同或相似特征节点形成的节点组可看作网络社区。

网络社区内部节点连接相对紧密，社区间连接相对稀疏。

由于不同结构社区表示不同的概念，社区检测并非是单一问题，因此,社区可表述为一个相关问题的集合[1]。

现有的社区检测算法利用已知网络信息发现社区特征。

Evans等[2]认为社区不能简单地用节点定义，而是在节点之间的连接定义时，提出了利用边聚类算法来划分网络中的边。

Palla等[3]提出了集团渗流算法(Clique Percolation Method)，把节点及边的集合称为集团。

作为集团成员，节点充当“原子”角色，从而组建社区这一“分子”。

集团提供了表示社区结构局部特征的一种方式,这些局部特征利用文献[3]中的“渗流”过程来分割社区。

集团渗流算法通过自我中心网(Egonet)得到每一个节点的近邻节点集，这个节点称为自我中心节点。

检查离群点的方法
离群点（Outlier）是指数据集中某些异常值，与其他数据值相比有明显的偏离。

检测离群点是数据分析中的重要步骤，可以帮助我们找出数据中的异常值，进而分析其原因或者在建模时将其排除。

以下是常用的几种检查离群点的方法：
1. 箱线图（Box Plot）方法：箱线图是一种可视化方法，通过绘制数据的5个统计量（最小值、最大值、中位数、第一四分位数和第三四分位数）来显示数据的分布情况。

箱线图可以直观地显示数据的离群点，将小于最小值或大于最大值一定倍数的四分位距的数据视为离群点。

2. Z-Score方法：Z-Score是一种标准化方法，可以将数据转化为标准正态分布。

通过计算每个数据点到平均值的距离与标准差的比值，将距离超过一定范围的数据视为离群点。

通常将Z-Score的阈值设定为3或4。

3. IQR方法：IQR（Interquartile Range）是四分位距，是数据集中间50%的数据的范围。

通过计算IQR的上下界，将小于下界或大于上界一定倍数的四分位距的数据视为离群点。

4. DBSCAN方法：DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种聚类方法，可以将数据集分为离群点、核心点和边界点三类。

该方法通过计算每个数据点周围的密度，将密度低于一定阈值的数据视为离群点。

检查离群点的方法因数据类型、样本大小、计算效率等方面的差
异而异，选择合适的方法需要结合具体情况进行。

离群点检测算法
1 离群点检测算法
离群点检测算法，也称为异常检测，用于识别和分析数据集中新
出现的异常和错误数据值。

它可以帮助数据分析人员分析数据之间的
异常行为并进行响应。

这是一种重要的数据挖掘技术，可以帮助分析
人员发现错误、异常数据和模式，这些数据通常是许多数据挖掘任务
中无法完成的。

离群点检测算法的核心是识别可疑的异常和不自然的数据值，其
中数据值可能比其他数据值显著不同。

它们通常是数据集中的单个离
散数据点。

通过使用离群点检测算法，分析人员可以更好地了解数据，例如，在数据中发现新数据模式，并将不正常的数据过滤掉。

离群点检测的主要步骤包括数据清理、数据可视化和离群点检测。

数据清理是消除数据集中的无用和错误数据，以便更好地了解模型的
输入和输出。

数据可视化包括绘制核密度估计图、箱形图和散点图，
以及多变量关系图，用于更好地分析数据集中的异常行为。

最后，离
群点检测算法可以通过基本离群点检测算法、算法并行算法和网络算法，找出可疑的错误或异常数据点。

离群点检测算法可以帮助分析人员发现和识别异常行为，通过此
技术，分析人员可以更好地理解数据，从而提出更有效的决策。

它是
一种重要的数据挖掘技术，运用它可以发现和过滤掉不正常的数据。

学生姓名学生学号专业班级指导教师2015-1-17实验四离群点检测（基于距离）此实验是在实验三的基础上，修改完成。

实验算法与上次相同，但增加了离群点检测。

离群点检测方法为：在聚类完成之后，计算簇中的点到各自簇心的距离。

当簇中的一点到簇心的距离大于该簇的平均距离与 1.5 倍标准差的和时，则认为该点为离群点，即阀值平均距离与 1.5 倍标准差的和。

、实验目的1. 深刻理解离群点，了解离群点检测的一般方法；2. 掌握基于距离的离群点检测算法；3. 锻炼分析问题、解决问题的思维，提高动手实践的能力、背景知识异常对象被称作离群点。

异常检测也称偏差检测和例外挖掘。

常见的异常成因：数据来源于不同的类（异常对象来自于一个与大多数数据对象源（类）不同的源（类）的思想），自然变异，以及数据测量或收集误差。

异常检测的方法：（1）基于模型的技术：首先建立一个数据模型，异常是那些同模型不能完美拟合的对象；如果模型是簇的集合，则异常是不显著属于任何簇的对象；在使用回归模型时，异常是相对远离预测值的对象；（2）基于邻近度的技术：通常可以在对象之间定义邻近性度量，异常对象是那些远离其他对象的对象；（3）基于密度的技术：仅当一个点的局部密度显著低于它的大部分近邻时才将其分类为离群点。

三、实验要求改写一种简单的半监督方法，用于离群点检测。

使用一种你熟悉的程序设计语言，如C++ 或Java，实现该方法，并在两种不同的数据集上进行讨论（1）只有一些被标记的正常对象；（2）只有一些被标记的离群点实例。

四、实验环境Win7 旗舰版+ Visual Studio 2012语言：C++五、算法描述K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。

该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。

1、算法思路K -means 算法先随机选取K 个对象作为初始的聚类中心。

专利名称：基于模块化设计的三维点云离群点检测方法和装置专利类型：发明专利
发明人：冯结青,葛林林
申请号：CN202010394671.6
申请日：20200511
公开号：CN111582391B
公开日：
20220607
专利内容由知识产权出版社提供
摘要：本发明涉及一种基于模块化设计的三维点云离群点检测方法和装置，属于计算机图形学领域。

包括：1)建立三维点云Sraw的搜索树；2)基于搜索树获取三维点云Sraw的邻近度集合；3)基于搜索树获取三维点云Sraw的可信区域集合；4)将步骤2)得到的邻近度集合与步骤3)得到的可信区域集合的数据进行融合，得到离群点集合。

采用模块化的思想，利用两种特征提取模块来提取需要的信息，并建立统一的数据处理和融合模块来对提取的信息进行处理，提高了离群点检测结果的可靠性。

申请人：浙江大学
地址：310013 浙江省杭州市西湖区余杭塘路866号
国籍：CN
代理机构：杭州天勤知识产权代理有限公司
代理人：颜果
更多信息请下载全文后查看。