异构属性网络中统计显著密集子图发现算法研究

• 作者: 李源 范晓林 孙晶 赵宇海
• 来源期刊: 小型微型计算机系统
• 关键词: 异构属性网络 密集子图 统计显著性 (k,Ψ)-核
• 年，卷（期）: 2021,（10）
• 所属期刊栏目: 计算机软件与数据库研究|Computer Software and Database Research
• 页码范围: 2203-2210
• 页数: 8页
• 分类号: TP311
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2021.10.031

摘要

密集子图体现了大图中的稠密部分,它是图中具有最高密度的子图,这使得它在事件检测,生物分析和社区发现等方面具有广泛应用和实用价值.现有的密集子图发现方法所使用的图模型描述不够详细,并且发现的密集子图缺乏统计显著性.为了解决以上问题,本文提出了异构属性网络这一新模型,然后在异构属性网络上通过非参数扫描统计和基于(k,Ψ)-核的方法发现高Steiner连通度的统计显著密集子图.首先构建异构属性网络,其包括类型、实体、关系和带有时序关系的属性信息;其次通过历史属性信息计算异构属性网络中每个实体的统计值,形成统计权重网络;然后利用非参数扫描统计方法测量统计权重网络中子图的统计显著性;最后由于此问题是NP-难的,于是提出了基于(k,Ψ)-核的局部扩展的近似统计显著密集子图发现算法.大量基于真实异构属性网络数据的实验结果证明了本文所提出算法的有效性和高效性.