Effect of Sampling on Growth Mechanisms of Complex Networks

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

CLC Number:

N 94

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

References

［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]	OUYANG Xuyu, CHANG Haichao, LIU Zuyuan, FENG Baiwei, ZHAN Chengsheng, CHENG Xide. Application of Adaptive Sampling Method in Hull Form Optimization [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 937-943.
[2]	LIU Yuntao, LU Manjun, ZHANG Wenxu, HU Jianbo. Realization of False Target Jamming Signal Based on Zedboard Hardware Platform [J]. Air & Space Defense, 2022, 5(4): 76-81.
[3]	LI Tongde, YAN Huaicheng, ZHOU Ge, FAN Sha, HONG Gu. Distributed Fusion Estimation of Asynchronous Multi-Rate Multi-Sensor Network System in Navigation Guidance [J]. Air & Space Defense, 2021, 4(3): 92-98.
[4]	CHEN Tao, ZHANG Ying, HUANG Xiangsong. Adaptive Interference Waveform Design Based on Reinforcement Learning [J]. Air & Space Defense, 2021, 4(2): 59-.
[5]	XIA Li, ZOU Zaojian, YUAN Shuai, ZENG Zhihua. Uncertainty Quantification for CFD Simulation of Stochastic Drag Flow Based on Non-Intrusive Polynomial Chaos Method [J]. Journal of Shanghai Jiaotong University, 2020, 54(6): 584-591.
[6]	FANG Jia, LU Zhiqiang. Modeling and Optimization of Robust Scheduling Template Considering Equipment Failure [J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1278-1290.
[7]	WANG Song,LIU Mingxing,ZHAO Zihong,WANG Shun. A New Type of Analog Signal Isolation Technology Applied to Nuclear Reactor Safety Level DCS [J]. Journal of Shanghai Jiaotong University, 2019, 53(Sup.1): 93-97.
[8]	ZOU Xinyao,GAO Zhan,HUANG Zhen,ZHU Lei. Effects of Main Carbon Chain Length on Soot Formation and Evolution in Laminar Diffusion Flames of Fatty Acid Methyl Esters [J]. Journal of Shanghai Jiaotong University, 2019, 53(11): 1276-1284.
[9]	LONG Zhou, CHEN Songkun, WANG Deyu. Reliability-Based Design Optimization of Ship Structures Based on SMOTE Algorithm [J]. Journal of Shanghai Jiao Tong University, 2019, 53(1): 26-34.
[10]	KONG Dan-ya, MA Zhe, WANG Yin, ZHAI Gang-jun. Analysis of Sampling Rate and Ground Contact Posture of Two-Dimension Gravity Sampling Device [J]. Ocean Engineering Equipment and Technology, 2018, 5(增刊): 172-176.
[11]	LIU Bin (刘彬), LIU Tingzhang (刘廷章), MENG Fanqin (孟凡芹). Research on Morlet Wavelet Based Lamb Wave Spatial Sampling Signal Optimization Method [J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(Sup. 1): 62-69.
[12]	CHEN Songkun,WANG Deyu. An Improved Monte Carlo Reliability Analysis Method Based on Neural Network [J]. Journal of Shanghai Jiaotong University, 2018, 52(6): 687-692.
[13]	WANG Zhiwen,LI Xuan,ZHU Chaoqun. A Optimal Guaranteed Cost Control of Networked Multi-Rate System [J]. Journal of Shanghai Jiaotong University, 2018, 52(1): 120-126.
[14]	JI Shaobo,ZHAO Shengjin,CHENG Yong,WANG Yang,ZHAO Xiuliang,LI Xinhai. A Method for Transform of Pressure Signal from Time Domain to Angle Domain Based on Internal Clock Sampling [J]. Journal of Shanghai Jiaotong University, 2017, 51(1): 57-.
[15]	ZHANG Honga* (张红), HU Changzhenb (胡昌振), WANG Xiaojuna (王小军). Brittleness Analysis and Important Nodes Discovery in Large Time-Evolving Complex Networks [J]. Journal of shanghai Jiaotong University (Science), 2017, 22(1): 50-054.