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

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

Network embedding based tenuous subgraph finding

Concerning the high time and space complexity caused by using high-dimensional tenuous vectors to represent network information in tenuous subgraph finding problem, a Tenuous subGraph Finding (TGF) algorithm based on network embedding was proposed. Firstly, the network structure was mapped to the low-dimensional space by the network embedding method in order to obtain the low-dimensional vector representation of nodes. Then, the tenuous subset finding problem in the vector space was defined, and the tenuous subgraph finding problem was transformed into the tenuous subset finding problem. Finally, the sample points with lowest local density were searched iteratively and expanded to figure out the largest tenuous subset satisfying the given conditions. Experimental results on Synthetic_1000 dataset show that, the search efficiency of TGF algorithm is 1 353 times that of Triangle and Edge Reduction Algorithm (TERA) and 4 times of that Weight of K-hop (WK) algorithm, and it achieves better results in k-line, k-triangle and k-density indexes