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

doi:10.11772/j.issn.1001-9081.2020020207

计算机应用 ›› 2020, Vol. 40 ›› Issue (10): 2929-2935.DOI: 10.11772/j.issn.1001-9081.2020020207

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

孙鹤立^1,2, 何亮¹, 何方¹, 孙苗苗¹, 贾晓琳¹

1. 西安交通大学计算机科学与技术学院, 西安 710049;
2. 西安交通大学新闻与新媒体学院, 西安 710049

收稿日期:2020-02-28 修回日期:2020-04-26 出版日期:2020-10-10 发布日期:2020-05-21
通讯作者: 贾晓琳
作者简介:孙鹤立(1983-),女,辽宁铁岭人,副教授,博士生导师,博士,主要研究方向:大规模图数据挖掘、复杂网络分析、社会网络分析、道路网络、移动数据挖掘;何亮(1975-),男,陕西西安人,讲师,博士,主要研究方向:数据挖掘、软件工程;何方(1994-),男,湖北黄冈人,硕士,主要研究方向:图数据挖掘、复杂网络分析;孙苗苗(1995-),女,河南驻马店人,硕士研究生,主要研究方向:图数据挖掘、复杂网络分析;贾晓琳(1963-),女,陕西西安人,高级工程师,博士,主要研究方向:数据挖掘、软件工程。
基金资助:
国家自然科学基金资助项目（61672417）。

Network embedding based tenuous subgraph finding

SUN Heli^1,2, HE Liang¹, HE Fang¹, SUN Miaomiao¹, JIA Xiaolin¹

1. School of Computer Science and Technology, Xi'an Jiaotong University, Xi'an Shaanxi 710049, China;
2. School of Journalism and New Media, Xi'an Jiaotong University, Xi'an Shaanxi 710049, China

Received:2020-02-28 Revised:2020-04-26 Online:2020-10-10 Published:2020-05-21
Supported by:
This work is partially supported by theFoundation:National Natural Science Foundation of China (61672417).

摘要/Abstract

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

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

Abstract: 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

Key words: social network, graph mining, network embedding, tenuous subgraph, weak social interation

中图分类号:

TP39

孙鹤立, 何亮, 何方, 孙苗苗, 贾晓琳. 基于网络嵌入的稀疏子图发现算法[J]. 计算机应用, 2020, 40(10): 2929-2935.

SUN Heli, HE Liang, HE Fang, SUN Miaomiao, JIA Xiaolin. Network embedding based tenuous subgraph finding[J]. Journal of Computer Applications, 2020, 40(10): 2929-2935.

参考文献

[1] GILBERT J M,HILLS S,RIFE M L. Substance abuse treatment:group therapy. Treatment Improvement Protocol (TIP) Series 41[J]. Substance Abuse and Mental Health Services Administration, 2005,190(4):80-80.
[2] SHEN C Y,HUANG L H,YANG D N,et al. On finding socially tenuous groups for online social networks[C]//Proceedings of the 23rd ACM SIGKDD Conference on Knowledge and Data Mining. New York:ACM,2017:415-424.
[3] HSU B Y,LAN Y F,SHEN C Y. On automatic formation of Effective therapy groups in social networks[J]. IEEE Transactions on Computational Social Systems,2018,5(3):713-726.
[4] LI W. Finding tenuous groups in social networks[C]//Proceedings of the 2018 IEEE International Conference on Data Mining Workshops. Piscataway:IEEE,2018:284-291.
[5] 齐金山, 梁循, 李志宇, 等. 大规模复杂信息网络表示学习:概念、方法与挑战[J]. 计算机学报,2018,41(10):2394-2420.(QI J S,LIANG X,LI Z Y,et al. Representation learning of large-scale complex information network:concepts,methods and challenges[J]. Chinese Journal of Computers,2018,41(10):2394-2420.)
[6] 涂存超, 杨成, 刘知远, 等. 网络表示学习综述[J]. 中国科学:信息科学,2017,47(8):980-996.(TU C C,YANG C,LIU Z Y,et al. Network representation learning:an overview[J]. SCIENTIA SINICA Informationis,2017,47(8):980-996.)
[7] CAI H,ZHENG V W,CHANG K C C. A comprehensive survey of graph embedding:problems, techniques and applications[J]. IEEE Transactions on Knowledge and Data Engineering,2018,30(9):1616-1637.
[8] PEROZZI B,AI-RFOU R,SKIENA S. DeepWalk:online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York:ACM,2014:701-710.
[9] GROVER A,LESKOVEC J. Node2vec:scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York:ACM,2016:855-864.
[10] TANG J,QU M,WANG M,et al. LINE:large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. Republic and Canton of Geneva, CHE:International World Wide Web Conferences Steering Committee,2015:1067-1077.
[11] YANG C, LIU Z, ZHAO D, et al. Network representation learning with rich text information[C]//Proceeding of the 24th International Joint Conference on Artificial Intelligence. Palo Alto,CA:AAAI Press,2015:2111-2117.
[12] WANG D,CUI P,ZHU W. Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York:ACM,2016:1225-1234.
[13] CAO S,LU W,XU Q. Deep neural networks for learning graph representations[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence. Palo Alto,CA:AAAI Press,2016:1145-1152.
[14] BOURLARD H, KAMP Y. Auto-association by multilayer perceptrons and singular value decomposition[J]. Biological Cybernetics,1988,59(4/5):291-294.
[15] LAI S,LIU K,HE S,et al. How to generate a good word embedding[J]. IEEE Intelligent Systems,2016,31(6):5-14.
[16] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E,Statistical, Nonlinear, and Soft Matter Physics,2008,78(4 Pt 2):No. 046110.

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

Network embedding based tenuous subgraph finding

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[2]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[3]	樊玮, 王慧敏, 邢艳. 基于自编码器的多视图属性网络表示学习模型[J]. 计算机应用, 2021, 41(4): 1064-1070.
[4]	孙鹤立, 徐统, 何亮, 贾晓琳. 融合用户历史行为与社交关系的个性化社交事件推荐方法[J]. 计算机应用, 2021, 41(2): 324-329.
[5]	李翔锟, 贾彩燕. 融合重叠社区正则化及隐式反馈的协同过滤方法[J]. 计算机应用, 2021, 41(1): 53-59.
[6]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[7]	李春英, 汤庸, 肖政宏, 李天送. 学术社交网络中的权威学者推荐模型[J]. 计算机应用, 2020, 40(9): 2594-2599.
[8]	杨书新, 梁文, 朱凯丽. 社交网络中对立影响最大化算法[J]. 计算机应用, 2020, 40(7): 1944-1949.
[9]	易东义, 邓根强, 董超雄, 祝苗苗, 吕周平, 朱岁松. 基于图卷积神经网络的医保欺诈检测算法[J]. 计算机应用, 2020, 40(5): 1272-1277.
[10]	冯丽萍, 韩琦, 周志刚, 白增亮. 社交网络影响的不良信息扩散建模及最优控制策略[J]. 计算机应用, 2020, 40(3): 735-739.
[11]	单晓欢, 张志国, 宋宝燕, 任成林. 事件社交网中基于有向标签图及用户反馈的活动推荐方法[J]. 计算机应用, 2020, 40(2): 448-453.
[12]	何昊晨, 张丹红. 基于多维社交关系嵌入的深层图神经网络推荐方法[J]. 计算机应用, 2020, 40(10): 2795-2803.
[13]	郝志峰, 柯妍蓉, 李烁, 蔡瑞初, 温雯, 王丽娟. 基于图编码网络的社交网络节点分类方法[J]. 计算机应用, 2020, 40(1): 188-195.
[14]	杨燕琳, 冶忠林, 赵海兴, 孟磊. 基于高阶近似的链路预测算法[J]. 计算机应用, 2019, 39(8): 2366-2373.
[15]	张书旋, 康海燕, 闫涵. 基于Skyline计算的社交网络关系数据隐私保护[J]. 计算机应用, 2019, 39(5): 1394-1399.