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

作者：孙鹤立; 何亮; 何方; 孙苗苗; 贾晓琳^*

来源：计算机应用, 2020, 40(10): 2929-2935.

• 社交网络
• 图挖掘
• 网络嵌入
• 稀疏子图
• 弱社交

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

• 单位
  西安交通大学