二分图及有向图上的整数稠密子图研究

20251204

信息传输、软件和信息技术服务业

本科技成果已完成从理论模型、算法体系到实验验证的系统化研究，具备良好的工程化与产业化基础。在技术成熟度方面，成果包括二分图 (α,β)-dense 子图模型、有向图整数最密子图（IDS）模型，以及 DSS++、DD+、GetIDS++、MultiCore 等高效算法。相关模型经过严格的理论证明，具有唯一性、嵌套性、近似最优性等特征；算法具备可扩展性强、复杂度低、运行稳定的优势，可支持亿级边规模图数据的实时或准实时稠密结构挖掘任务。 在工艺与性能指标方面，二分图方向的算法在多个真实大规模数据集上实现了数十倍至数百倍的运行速度提升，能够准确识别双边关系网络中的高密度结构；有向图方向的 IDS 模型在保证近似最优的前提下，将计算时间降低一个数量级以上，近似算法 MultiCore 在多数数据集中可达到接近最优解的效果，适用于高吞吐量场景的快速分析。 目前成果已形成完整的软件原型，包括模型定义库、核心算法模块、图数据处理接口及可视化分析组件，具备良好的可集成性，可嵌入到金融风控系统、社交平台分析模块、推荐系统后端、网络安全监测系统等业务流程。成果经过多轮测试验证，运行稳定，具备向企业级应用迁移的条件，处于工程实现阶段与示范应用阶段之间，可在短期内进入实际部署阶段。 综上，本成果的理论成熟度高、算法性能指标优越、软件工程基础扎实，已达到可转化、可部署的技术阶段，为进一步产业化奠定了坚实基础。

为推动本科技成果在产业环境中落地应用，需要与合作单位在技术集成、算力资源、场景数据、系统验证等方面开展协同工作。合作需求主要包括以下几方面： 数据与场景支持 合作方需提供典型业务场景的真实网络数据，如社交关系图、电商用户—商品二分图、金融交易网络或通信行为数据，以便对算法进行针对性调优和场景化验证。 计算与部署资源 需求包括服务器算力、GPU/CPU 集群或分布式计算平台，用于大规模图数据的模型训练、算法调试、系统部署与性能压测。 系统集成支持 合作方需配合进行接口对接，包括数据输入接口设计、风控系统或推荐系统后台服务的 API 集成，以及协同完成可视化展示界面的开发与嵌入。 人员配合与试运行环境 合作方需提供数据工程人员、业务分析人员和系统开发工程师，参与需求梳理、技术方案制定和输出结构解释，以便使算法结果与业务流程紧密结合。 本项目组可提供模型与算法的技术转让、软件模块交付、部署指导以及技术培训等支持，以共同推进科技成果的工程化与应用化。

可国（境）内外转让

该科技成果在信息传输、软件与信息技术服务等行业具有广泛应用前景，可产生显著的经济效益与社会效益。 在经济效益方面： （1）在金融风控与反欺诈系统中，引入高效稠密子图挖掘技术，可提升异常团伙识别能力，有效降低企业因欺诈造成的损失，提高风险控制效率； （2）在推荐系统与电商平台场景中，通过对二分图密度结构的挖掘，可提升用户匹配度和商品推荐效果，显著提高转化率与用户体验； （3）在社交平台安全治理中，可通过高密度结构识别快速定位异常群体与恶意账号，降低治理成本，提高平台安全性； （4）算法具有通用性，可作为基础模块嵌入图数据库、风控引擎及数据分析平台，产生持续的软件授权与服务收益。 在社会效益方面： 成果有助于构建更加安全、可信的网络生态环境，提高社会治理智能化水平；对反欺诈、网络安全预警、虚假信息检测等公共安全领域具有直接贡献；在科研与教育领域，该成果可作为复杂网络分析的重要技术工具，推动相关学科发展。 综上，本科技成果具有明确的商业化价值和广泛的应用场景，可在未来数年内持续创造经济收入并产生显著的社会效益。

北京市自然科学基金本科生“启研”计划

北京市科学技术委员会;中关村科技园区管理委员会

本项目围绕二分图与有向图的稠密结构建模与高效计算展开，系统解决了传统模型在表达力、复杂度与可扩展性方面的核心瓶颈，提出了 (α, β)-dense 子图模型与整数最密子图（IDS）模型，并构建了对应的高性能算法体系。研究在二分图方向建立了全新的密度分解理论，提出 DSS++、DD+ 等算法，在亿级数据上实现数十至数百倍的性能提升，并以此成果发表论文于国际数据库顶级会议 ACM SIGMOD 2025；在有向图方向提出 IDS 理论框架及高效精确算法与近线性近似算法 MultiCore，在真实数据上近似比低于 1.0005、速度提升一个数量级，在反欺诈检测中识别率提升约 15%、速度提升 126 倍，并以此方向完成第二篇高水平论文。项目整体形成了统一、系统的稠密子图理论与算法体系，在模型创新、算法突破与应用验证等方面取得重要进展，推动了复杂网络与图计算研究的发展，并在金融风控、社交网络治理与推荐系统等领域展现出显著的经济与社会价值。