面向网络系统基于概念认知学习的最大s-缺陷团动态检测

近日，陕西师范大学联合西南大学，西安工程大学，加拿大曼尼托巴大学等团队提出了一种面向网络系统基于概念认知学习（Concept-cognitive Learning, CCL）的最大s-缺陷团识别框架，用于动态网络中的凝聚子图挖掘。该框架将FCA中的等势概念(Equiconcept)与缺陷团扩展机制相结合，建立了：(1) 最大s-缺陷团可由等势概念扩展至多s个顶点得到，保证检测完备性；(2) 设计静态算法SFDC与增量算法IFDC，支持动态网络高效更新。实验表明，该方法在静态与动态场景中通常较现有最优方法取得10倍至100倍加速，搜索空间降低1-3个数量级。该工作为动态网络中的凝聚结构发现提供了全新视角, 同时拓宽了图概念认知学习(Graph Concept-cognitive Learning, GCCL)的研究范畴。

研究背景：

在网络系统中，团结构常用于刻画紧密协作群体。然而现实网络普遍存在噪声、数据缺失与动态演化，严格团模型易遗漏真实凝聚子群。为此，允许至多s 条缺失边的s-缺陷团受到关注，但最大s-缺陷团检测具有NP难性，现有精确算法计算开销大，启发式方法参数敏感，且多面向静态网络；网络一旦更新往往需重新搜索，难以满足实时分析需求。图概念认知学习为高效、可增量维护的凝聚结构发现提供了新思路。

研究方法与过程：

针对上述问题，提出一种基于概念认知学习的最大s-缺陷团动态识别框架。该框架由输入图与图形式背景构建、等势概念提取、最大s-缺陷团搜索和结果输出四个阶段组成，如图所示。首先，将图转化为图形式背景(Graph Formal Context)，利用概念格生成算法提取等势概念，并将其作为候选团的初始搜索空间。其次，从等势概念出发，依据“最大s-缺陷团可由等势概念扩展至多s个顶点得到”的理论结论，采用BFS逐层扩展邻居顶点，动态计算缺失边数，并利用缺陷上界与规模下界双重剪枝，快速定位最大s-缺陷团。在此基础上，设计静态算法SFDC与增量算法IFDC：IFDC复用已有概念格，仅对受更新影响的子图进行增量维护，避免全局重算。

图1. 最大s-缺陷团搜索框架图

最后，在8个真实网络数据集上与先进算法进行对比，设置连续动态更新场景，从运行时间、搜索树规模、精度/召回率/F1等指标验证方法性能。实验表明，该方法通常取得10～100倍加速（如图2所示），搜索空间降低1～3个数量级。

图2. 动态网络下各算法连续更新运行时间对比

研究结论：

所提方法是一种基于概念认知学习的最大s-缺陷团识别框架，可以有效实现静态与动态网络中的最大s-缺陷团检测，特别是等势概念扩展与增量更新机制的引入发挥重要作用：(1) 理论上证明了最大s-缺陷团可由等势概念扩展至多s个顶点得到，保证了检测的完备性；(2) 设计了静态算法SFDC与增量算法IFDC，利用概念格动态更新避免冗余计算，显著提升了动态网络中的检测效率。在8个真实网络数据集上与先进算法进行实验比较，所提方法通常取得10～100倍加速，搜索空间降低1～3个数量级，尤其在高密度缺陷和动态环境下表现突出。案例研究进一步验证了该方法在真实企业协作网络中提取有意义凝聚结构的实用价值。

该论文发表在人工智能领域国际权威期刊 Information Sciences（CiteScore: 14.6，Impact Factor: 6.0，JCR Q1 TOP期刊，支持开放获取），题目为《Leveraging concept-cognitive learning to identify maximum s-defective cliques in network systems》。陕西师范大学张佳琪为第一作者，郝飞教授为通讯作者。

论文链接：https://www.sciencedirect.com/science/article/pii/S0020025526011588

引用格式：J. Zhang, F. Hao, Q. Wan, W.H. Xu, C.K.-S. Leung. Leveraging concept-cognitive learning to identify maximum s-defective cliques in network systems. Information Sciences, Volume 762, 2027, Article 124227.