抽样对复杂网络生长机制的影响

上海交通大学学报（自然版） ›› 2013, Vol. 47 ›› Issue (03): 479-483.

抽样对复杂网络生长机制的影响

杨波，陈影

（杭州电子科技大学管理学院，杭州 310018）

收稿日期:2012-03-16 出版日期:2013-03-28 发布日期:2013-03-28
基金资助:
国家自然科学基金资助项目（70872028）；教育部人文社科研究青年基金资助项目（09YJCZH029）

Effect of Sampling on Growth Mechanisms of Complex Networks

YANG Bo, CHEN Ying

(Management School, Hangzhou Dianzi University, Hangzhou 310018, China)

Received:2012-03-16 Online:2013-03-28 Published:2013-03-28

摘要/Abstract

摘要： 运用基于机器学习理论开发的网络机制辨识方法，对不同抽样方案得到的抽样网络生长机制进行识别，将结果与完全网络比较,以分析抽样对网络机制的影响.研究表明，不同抽样方案对网络生长机制具有不可忽视的影响.在抽样绩效方面，中枢链式抽样具有较好的网络机制保持能力；而对比网络结构特征与网络机制，中枢抽样和链式抽样对网络机制的影响更显著.此外，各抽样方案对网络机制的影响随网络类型的不同有一定差异，这表明在实践中有必要根据网络类型选择恰当的抽样方法.

关键词: 系统科学, 复杂网络, 抽样, 网络生长机制

Abstract: The problem of whether the topological structure of network can be kept well when data is collected incompletely is concerned. The current focus on the effect of sampling on macro statistical properties has been extended to consideration of its effect on micro network mechanisms. A mechanism-inferring method of networks exploited from machine learning theory was used to identify the mechanisms of sampled networks obtained by different sampling methods. The results were compared with the original networks to analyze the impact of sampling on network mechanisms. It is found that different sampling methods have a nontrivial influence on growth mechanisms of networks. In conclusion, the hub-chain sampling strategy can keep mechanisms better than others. Meanwhile, hub sampling and chain sampling have more remarkable influences on network mechanisms than their effects on structural properties. In addition, there are some differences in the effects of sampling for different types of networks, which means in practice we should select suitable sampling method according to the research object of network to improve the accuracy of network building more effectively.

Key words: system science, complex networks, sampling, growth mechanism of network

中图分类号:

N 94

杨波, 陈影. 抽样对复杂网络生长机制的影响 [J]. 上海交通大学学报（自然版）, 2013, 47(03): 479-483.

YANG Bo, CHEN Ying. Effect of Sampling on Growth Mechanisms of Complex Networks[J]. Journal of Shanghai Jiaotong University, 2013, 47(03): 479-483.

参考文献

［1］Newman M E J. The structure and function of complex networks［J］. SIAM Review, 2003, 45(2):167256.
［2］Newman M E J. The physics of networks［J］. Physics Today, 2008, 61(11): 3338.
［3］Barabási A L. Scalefree networks: A decade and beyond［J］. Science, 2009, 325(5939): 412413.
［4］Han J D, Dupuy D, Bertin N, et al. Effect of sampling on topology predictions of proteinprotein interaction networks［J］. Nature Biotechnology, 2005, 23(7): 839844.
［5］Stumpf M P, Wiuf C, May R M. Subnets of scalefree networks are not scalefree: Sampling properties of networks［J］. Proceedings of the National Academy of Sciences, USA, 2005, 102(12): 42214224.
［6］Lee S H, Kim P, Jeong H. Statistical properties of sampled networks［J］. Physical Review E, 2006, 73(1): 016102.
［7］杨波，段文奇，陈忠. 抽样对复杂网络多重结构特征的影响［J］.上海交通大学学报，2007，41（12）：19791984.
YANG Bo, DUAN Wenqi, CHEN Zhong. Effect of sampling on multiple structural properties of complex networks［J］. Journal of Shanghai Jiaotong University, 2007, 41(12): 19791984.
［8］Yoon S, Lee S, Yook S H, et al. Statistical properties of sampled network by random walks［J］ . Physical Review E, 2007, 75(4): 046114.
［9］Newman M E J. Egocentered networks and the ripple effect［J］. Social Networks, 2003, 25(1): 8395.
［10］Airoldi E M, Bai X, Carley K M. Network sampling and classification: An investigation of network model representations［J］. Decision Support Systems, 2011, 51(3):506518.
［11］Middendorf M, Ziv E, Wiggins C H. Inferring network mechanisms: the Drosophila melanogaster protein interaction network［J］. Proceedings of the National Academy of Sciences, USA, 2005, 102(9): 31923197.

［12］Barabási A L, Albert R. Emergence of scaling in random networks［J］. Science, 1999, 286(10): 509512.
［13］Watts D J, Strogatz S H. Collective dynamics of smallworld networks［J］. Nature, 1998, 393(6684): 440–442.
［14］Vázquez A, Flammini A, Maritan A, et al. Modeling of protein interaction networks［J］. Complexus, 2003, 1(1): 3844.
［15］Vázquez A. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations［J］. Physical Review E, 2003, 67(5): 056104.
［16］Yang B, Chen X R. Method for quickly inferring the mechanisms of complex social networks based on the census of subgraph concentrations［J］. Journal of Systems Science and Complexity, 2009, 22(2):252259.

[1]	倪宇, 徐亚周, 罗祎喆, 虞梦昕, 金钊, 冯朔, 石育澄, 徐明亮. 基于复杂网络理论的多航天器作战体系效能评估方法[J]. 空天防御, 2026, 9(1): 132-144.
[2]	张辰微, 王颖, 李亚平, 张凯锋. 基于带权重介数的综合能源系统脆弱环节防护优化模型[J]. 上海交通大学学报, 2025, 59(7): 923-937.
[3]	. 基于非抽样双树-复小波变换与模糊聚类的声呐图像去噪技术[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 998-1008.
[4]	梁皓澜, 刘东奇, 曾祥君, 张琼, 张涛, 王锐. 针对电力高级量测体系的分布式拒绝服务攻击动态建模与最优防御策略[J]. 上海交通大学学报, 2025, 59(11): 1660-1674.
[5]	李建林, 孙浩元, 赵文鼎, 梁策, 梁忠豪, 袁晓冬. 基于变分模态分解-多模糊控制的风电混储系统功率分配策略[J]. 上海交通大学学报, 2025, 59(10): 1498-1509.
[6]	卢鹏丽1, 陈玮1, 郭育红2, 陈娅红3. 复杂网络中对称非负矩阵分解的节点中心性算法[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 1037-1049.
[7]	范宏, 何杰, 田书欣. 变步长仿真与改进熵权法联动的综合能源系统鲁棒性评估方法[J]. 上海交通大学学报, 2024, 58(1): 59-68.
[8]	苏泓嘉, 罗宇成, 刘飞. 装备体系效能评估及支撑技术综述[J]. 空天防御, 2023, 6(3): 29-38.
[9]	翟玮昊, 龚敏浩, 林名润, 匡婷玉, 文珊珊. 基于主动学习的Kriging模型的可靠性分析[J]. 空天防御, 2023, 6(1): 1-5.
[10]	方佳, 陆志强. 考虑设备故障的鲁棒调度计划模板的建模优化[J]. 上海交通大学学报, 2020, 54(12): 1278-1290.
[11]	陈松坤，王德禹. 基于神经网络的蒙特卡罗可靠性分析方法[J]. 上海交通大学学报, 2018, 52(6): 687-692.
[12]	闵海根，赵祥模，徐志刚，张立成，王润民. 基于稳健特征点的立体视觉测程法[J]. 上海交通大学学报, 2017, 51(7): 870-877.
[13]	谢逢洁. 复杂网络上博弈行为演化的合作激励[J]. 上海交通大学学报（自然版）, 2015, 49(08): 1256-1262.
[14]	郑茂，王超，黄胜. 舰载机出动回收网络鲁棒性分析[J]. 上海交通大学学报（自然版）, 2013, 47(12): 1934-1939.
[15]	王昊翔，曾珊，刘挥扬. 虚拟社交网络中节点重要度分析[J]. 上海交通大学学报（自然版）, 2013, 47(07): 1055-1059.