基于网络嵌入的稀疏子图发现算法

摘要：

针对稀疏子图发现问题中使用高维稀疏向量表示网络信息存在的时间和空间消耗大的问题,提出一种基于网络嵌入的稀疏子图发现(TGF)算法.该算法首先通过网络嵌入的方法将网络结构映射到低维空间中,得到节点的低维向量表示;然后定义向量空间中的稀疏子集发现问题,将稀疏子图发现问题转化为稀疏子集发现问题;迭代搜索局部密度最低的样本点并对其进行扩张,最终找到一个满足条件的最大稀疏子集.实验结果表明,在Synthetic_1000数据集上与TERA(Triangle and Edge Reduction Algorithm)和WK(Weight of K-hop)算法相比,TGF算法的搜索效率是TERA的1353倍,是WK算法的4倍,并且在k-line、k-triangle和k-density指标上也取得了较优的结果.

关键词：社交网络、图挖掘、网络嵌入、稀疏子图、弱社交

所属期刊栏目：40

分类号：TP39(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61672417

在线出版日期：2020-10-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：2929-2935