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]	JIN Xuancheng, HONG Ge, GAO Shuo, XIA Tangbin, HU Xiaofeng, XI Lifeng. TSM-TLHS Prediction Method for Assembly Deformation of Large Curved Thin Plates in Shipbuilding [J]. Journal of Shanghai Jiao Tong University, 2025, 59(8): 1092-1102.
[2]	JIANG Yilin, ZHANG Yilong, ZHANG Fangyuan. Infrared Single Pixel Imaging Based on Generative Adversarial Network [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(6): 1114-1124.
[3]	LI Jianlin, SUN Haoyuan, ZHAO Wending, LIANG Ce, LIANG Zhonghao, YUAN Xiaodong. Power Allocation Strategy for Wind Power Hybrid Storage Systems Based on Variational Modal Decomposition-Multifuzzy Control [J]. Journal of Shanghai Jiao Tong University, 2025, 59(10): 1498-1509.
[4]	CAO Wenping, WANG Yao, ZHANG Yue, LUO Kui, HU Cungang, RUI Tao. Three-Vector Model-Free Predictive Current Control Method for Grid-Connected Inverters with Sampling Noise Compensation [J]. Journal of Shanghai Jiao Tong University, 2025, 59(10): 1523-1532.
[5]	LU Pengli^1∗ (卢鹏丽), CHEN Wei¹ (陈玮), GUO Yuhong²(郭育红), CHEN Yahong³(陈娅红). Symmetric Nonnegative Matrix Factorization for Vertex Centrality in Complex Networks [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 1037-1049.
[6]	LIU Wenqian, SHAN Liang, ZHANG Weilong, LIU Chenglin, MA Qiang. Unmanned Aerial Vehicle Path Planning Algorithm Based on Improved Informed RRT^* in Complex Environment [J]. Journal of Shanghai Jiao Tong University, 2024, 58(4): 511-524.
[7]	LI Guozhia a(李国志)，ZOU Shuizhong b*(邹水中),DING Shuacue a(丁数学). Visual Positioning of Nasal Swab Robot Based on Hierarchical Decision [J]. J Shanghai Jiaotong Univ Sci, 2023, 28(3): 323-329.
[8]	ZHANG Sheng, TANG Xiaofeng, LIU Keping, ZENG Yuanfan, CHU Chenglong, WU Zhiliang. Review on Research Status of Mars Ascent Vehicle’s Launching Technology [J]. Air & Space Defense, 2023, 6(3): 66-76.
[9]	ZHAI Weihao, GONG Minhao, LIN Mingrun, KUANG Tingyu, WEN Shanshan. Reliability Analysis Based on Active Learning Kriging Model [J]. Air & Space Defense, 2023, 6(1): 1-5.
[10]	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.
[11]	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.
[12]	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.
[13]	CHEN Tao, ZHANG Ying, HUANG Xiangsong. Adaptive Interference Waveform Design Based on Reinforcement Learning [J]. Air & Space Defense, 2021, 4(2): 59-66.
[14]	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.
[15]	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.