Construction and Applications of Null Models for Unweighted Networks

被引：0
作者：
Xu X.-K. [1 ,2 ]
Cui W.-K. [1 ]
Cui L.-Y. [1 ]
Xiao J. [1 ]
Shang K.-K. [3 ]
机构：
[1] College of Information and Communication Engineering, Dalian Minzu University, Dalian, 116600, Liaoning
[2] Guizhou Provincial Key Laboratory of Public Big Data, Guizhou University, Guiyang
[3] Computational Communication Collaboratory School of Journalism and Communication, Nanjing University, Nanjing
来源：
Dianzi Keji Daxue Xuebao/Journal of the University of Electronic Science and Technology of China | 2019年 / 48卷 / 01期
关键词：
Configuration model; Null model; Random disconnect-rewiring; Unweighted network;
D O I：
10.3969/j.issn.1001-0548.2019.01.020
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The static unweighted network, whose null models have been studied widely and thoroughly, is the most common type of complex networks at present. In this study, we classify an unweighted network into two types of networks: undirected network and directed network. We study the construction and applications of null models for the two kinds of networks, especially the null models of unweighted undirected network are emphasized. Firstly, we illustrate the definitions of null models from low to high orders for unweighted undirected network according to the theory of random graph series. And then we describe the constructing process and related applications for 1 k-3 k null models by using ER random graph, configuration model, edge swapping, and so on. For the edge swapping algorithm, which is the most important mode for constructing null models, we introduce non-tendentious random edge swapping, tendentious assortative or dis-assortative edge swapping, and local edge swapping for detecting whether the rich-club properties exist in a network. Moreover, the high order null models are firstly extended to analyze meso-scale network features such as community detection. Finally, we analyze 1 k null models of directed network and tried to detect four types of in-out degree assortativities. In this study, we find that null models can not only provide an accurate baseline for real-life networks, but also qualitatively and quantitatively describe non-trivial properties of empirical complex networks. © 2019, Editorial Board of Journal of the University of Electronic Science and Technology of China. All right reserved.
引用
收藏
页码：122 / 141
页数：19
相关论文
共 56 条
  • [1] Gjoka M., Kurant M., Markopoulou A., 2.5K-graphs: from sampling to generation, IEEE INFOCOM, pp. 1968-1976, (2013)
  • [2] Mahadevan P., Hubble C., Krioukov D.V., Et al., Orbis: Rescaling degree correlations to generate annotated internet topologies, ACM Special Interest Group on Data Communication, 37, 4, pp. 325-336, (2007)
  • [3] Mahadevan P., Krioukov D.V., Fall K.R., Et al., Systematic topology analysis and generation using degree correlations, ACM Special Interest Group on Data Communication, 36, 4, pp. 135-146, (2006)
  • [4] Orsini C., Dankulov M.M., Et al., Quantifying randomness in real networks, Nature Communications, 6, (2015)
  • [5] Bollobas B., Random Graphs, (2001)
  • [6] Newman M.E.J., The structure and function of complex networks, SIAM Review, 45, 2, pp. 167-256, (2003)
  • [7] Barabasi A., Albert R., Statistical mechanics of complex networks, Reviews of Modern Physics, 74, 1, pp. 47-97, (2002)
  • [8] Molloy M., Reed B., The size of the giant component of a random graph with a given degree sequence, Combinatorics, Probability and Computing, 7, 3, pp. 295-305, (1998)
  • [9] Shang K.-K., Xu X.-K., Construction and application for null models of complex networks based on randomized algorithms, Journal of University of Electronic Science and Technology of China, 43, 1, pp. 7-20, (2014)
  • [10] Shang K.-K., The study of null model construction and user behavior prediction for online social networks, (2013)
123456