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

上海交通大学学报（自然版） ›› 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]. 上海交通大学学报, 2020, 54(12): 1278-1290.
[2]	陈松坤，王德禹. 基于神经网络的蒙特卡罗可靠性分析方法[J]. 上海交通大学学报（自然版）, 2018, 52(6): 687-692.
[3]	闵海根，赵祥模，徐志刚，张立成，王润民. 基于稳健特征点的立体视觉测程法[J]. 上海交通大学学报（自然版）, 2017, 51(7): 870-877.
[4]	谢逢洁. 复杂网络上博弈行为演化的合作激励[J]. 上海交通大学学报（自然版）, 2015, 49(08): 1256-1262.
[5]	郑茂，王超，黄胜. 舰载机出动回收网络鲁棒性分析[J]. 上海交通大学学报（自然版）, 2013, 47(12): 1934-1939.
[6]	王昊翔，曾珊，刘挥扬. 虚拟社交网络中节点重要度分析[J]. 上海交通大学学报（自然版）, 2013, 47(07): 1055-1059.
[7]	周炎，刘亚冰，汪小帆. 一种基于层次化社团结构的复杂网络可视化平台[J]. 上海交通大学学报（自然版）, 2010, 44(03): 332-0335.
[8]	闫妍，刘晓，庄新田. 基于复杂网络理论的供应链级联效应检测方法[J]. 上海交通大学学报（自然版）, 2010, 44(03): 0-0325.