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

Network embedding based tenuous subgraph finding

作　　者：孙鹤立[1,2] 何亮[1] 何方[1] 孙苗苗 贾晓琳[1] SUN Heli;HE Liang;HE Fang;SUN Miaomiao;JIA Xiaolin(School of Computer Science and Technology,Xi’an Jiaotong University,Xi’an Shaanxi 710049,China;School of Journalism and New Media,Xi’an Jiaotong University,Xi’an Shaanxi 710049,China)

机构地区：[1]西安交通大学计算机科学与技术学院,西安710049 [2]西安交通大学新闻与新媒体学院,西安710049

出　　处：《计算机应用》2020年第10期2929-2935,共7页journal of Computer Applications

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

摘　　要：针对稀疏子图发现问题中使用高维稀疏向量表示网络信息存在的时间和空间消耗大的问题,提出一种基于网络嵌入的稀疏子图发现(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指标上也取得了较优的结果。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 1353 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。

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

分 类 号：TP39[自动化与计算机技术—计算机应用技术]