基于Dijkstra算法的社交网络抽样生成

doi:10.11772/j.issn.1001-9081.2016.06.1506

计算机应用 ›› 2016, Vol. 36 ›› Issue (6): 1506-1509.DOI: 10.11772/j.issn.1001-9081.2016.06.1506

基于Dijkstra算法的社交网络抽样生成

杜景林, 侯大俊

南京信息工程大学电子与信息工程学院, 南京 210044

收稿日期:2015-11-10 修回日期:2015-12-23 出版日期:2016-06-10 发布日期:2016-06-08
通讯作者: 侯大俊
作者简介:杜景林(1974-),男,河北滦平人,副教授,博士,CCF会员,主要研究方向:网络与通信、计算机软件;侯大俊(1992-),男,江苏扬州人,硕士研究生,主要研究方向:网络与通信、数据处理。
基金资助:
国家自然科学基金资助项目(41575155)。

Sampling algorithm for social networks based on Dijkstra algorithm

DU Jinglin, HOU Dajun

School of Electronic and Information Engineering, Nanjing University of Information Science and Technology, Nanjing Jiangsu 210044, China

Received:2015-11-10 Revised:2015-12-23 Online:2016-06-10 Published:2016-06-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (41575155).

摘要/Abstract

摘要： 针对社交网络中随机抽样算法抽样结果不能很好地代表原始网络的问题,设计了一种基于Dijkstra最短路径的抽样算法。首先,利用Dijkstra算法多次抽取社交网络中节点之间的最短路径;然后,对抽取到的路径中边出现的频率进行排序,选择较高频率的边组成抽样的子图。该算法解决了随机抽样算法存在的一些问题,实现了较好的生成抽取社交网络的功能。仿真实验结果表明,与随机抽样方法相比,所提抽样算法能减少抽样误差,更好地反映原始网络。

关键词: 社交网络, 网络抽样, Dijkstra算法, 聚类系数

Abstract: Using random sampling algorithm to sample the social network can not represent the original network well. In order to solve the problem, a new algorithm based on the Dijkstra shortest path algorithm was proposed. Firstly, the Dijkstra algorithm was used to sample the shortest path between nodes in social network repeatedly. Then, the frequencies of edges in the extracted path were ordered, and the edges with the higher frequencies were selected to compose the sampling subgraph. The proposed algorithm solved some problems existing in the random sampling algorithm and achieved a good function of extraction of social network. The simulation experimental results show that the proposed sampling algorithm has less error and reflect the original network better than random sampling method.

Key words: social network, network sampling, Dijkstra algorithm, clustering coefficient

中图分类号:

TP393.02

杜景林, 侯大俊. 基于Dijkstra算法的社交网络抽样生成[J]. 计算机应用, 2016, 36(6): 1506-1509.

DU Jinglin, HOU Dajun. Sampling algorithm for social networks based on Dijkstra algorithm[J]. Journal of Computer Applications, 2016, 36(6): 1506-1509.

参考文献

[1] LESKOVEC J, FALOUTSOS C. Sampling from large graphs[C]//Proceedings of the 200612th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2006:631-636.
[2] YOON S, LEE S, YOOK S H, et al. Statistical properties of sampled networks by random walks[J]. Physical Review E, Statistical Nonlinear and Soft Matter Physics, 2007, 75(4 Pt 2): 046114.
[3] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
[4] GAUVIN W, RIBEIRO B, TOWSLEY D, et al. Measurement and gender-specific analysis of user publishing characteristics on MySpace[J]. IEEE Network, 2010, 24(5): 38-43.
[5] PAPAGELIS M, DAS G, KOUDAS N. Sampling online social networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(3): 662-676.
[6] MURAI F, RIBEIRO B, TOWSLEY D, et al. On set size distribution estimation and the characterization of large networks via sampling[J]. IEEE Journal on Selected Areas in Communications, 2012, 31(6): 1017-1025.
[7] LIU Y, PAN W S, SHAO S H, et al. The effect of feedback sampling clock jitter on the performance of direct learning digital predistortion in wideband systems[J]. IEEE Wireless Communication Letters, 2013, 2(5): 479-482.
[8] LI Q G, SHI J Q, LIU T W, et al. A probabilistic approach towards modeling email network with realistic features[C]//Proceedings of the 201423rd International Conference on Computer Communication and Networks. Piscataway, NJ: IEEE, 2014: 1-8.
[9] 骆嘉伟,梁成,宋丹,等.蛋白质相互作用网络演化模型研究进展[J].计算机应用,2013,33(3):816-820,829.(LUO J W, LIANG C, SONG D, et al. Survey on evolutionary models of protein-protein interaction network[J]. Journal of Computer Applications, 2013, 33(3): 816-820, 829.)
[10] STAFF T P O. Correction: towards a methodology for validation of centrality measures in complex networks[J]. PloS ONE, 2014, 9(5): e90283.

[1]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[2]	孙鹤立, 徐统, 何亮, 贾晓琳. 融合用户历史行为与社交关系的个性化社交事件推荐方法[J]. 计算机应用, 2021, 41(2): 324-329.
[3]	赵旭剑, 王崇伟. 基于图卷积网络的微博新闻故事线抽取方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3139-3144.
[4]	李翔锟, 贾彩燕. 融合重叠社区正则化及隐式反馈的协同过滤方法[J]. 计算机应用, 2021, 41(1): 53-59.
[5]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[6]	李春英, 汤庸, 肖政宏, 李天送. 学术社交网络中的权威学者推荐模型[J]. 计算机应用, 2020, 40(9): 2594-2599.
[7]	杨书新, 梁文, 朱凯丽. 社交网络中对立影响最大化算法[J]. 计算机应用, 2020, 40(7): 1944-1949.
[8]	易东义, 邓根强, 董超雄, 祝苗苗, 吕周平, 朱岁松. 基于图卷积神经网络的医保欺诈检测算法[J]. 计算机应用, 2020, 40(5): 1272-1277.
[9]	冯丽萍, 韩琦, 周志刚, 白增亮. 社交网络影响的不良信息扩散建模及最优控制策略[J]. 计算机应用, 2020, 40(3): 735-739.
[10]	单晓欢, 张志国, 宋宝燕, 任成林. 事件社交网中基于有向标签图及用户反馈的活动推荐方法[J]. 计算机应用, 2020, 40(2): 448-453.
[11]	孙鹤立, 何亮, 何方, 孙苗苗, 贾晓琳. 基于网络嵌入的稀疏子图发现算法[J]. 计算机应用, 2020, 40(10): 2929-2935.
[12]	何昊晨, 张丹红. 基于多维社交关系嵌入的深层图神经网络推荐方法[J]. 计算机应用, 2020, 40(10): 2795-2803.
[13]	郝志峰, 柯妍蓉, 李烁, 蔡瑞初, 温雯, 王丽娟. 基于图编码网络的社交网络节点分类方法[J]. 计算机应用, 2020, 40(1): 188-195.
[14]	李瑶, 赵云芃, 李欣芸, 刘志芬, 陈俊杰, 郭浩. 基于sparse group Lasso方法的脑功能超网络构建与特征融合分析[J]. 计算机应用, 2020, 40(1): 62-70.
[15]	张书旋, 康海燕, 闫涵. 基于Skyline计算的社交网络关系数据隐私保护[J]. 计算机应用, 2019, 39(5): 1394-1399.

基于Dijkstra算法的社交网络抽样生成

Sampling algorithm for social networks based on Dijkstra algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics