The characteristics of cycle-nodes-ratio and its application to network classification

被引:13
作者
Zhang, Wenjun [1 ,2 ,4 ]
Li, Wei [1 ,2 ,3 ]
Deng, Weibing [1 ,2 ]
机构
[1] Cent China Normal Univ, Key Lab Quark & Lepton Phys MOE, Wuhan 430079, Peoples R China
[2] Cent China Normal Univ, Inst Particle Phys, Wuhan 430079, Peoples R China
[3] Max Planck Inst Math Sci, Inselstr 22-26, D-04103 Leipzig, Germany
[4] Anhui Univ Chinese Med, Sch Med Informat Engn, Hefei 230012, Peoples R China
来源
COMMUNICATIONS IN NONLINEAR SCIENCE AND NUMERICAL SIMULATION | 2021年 / 99卷
基金
中国国家自然科学基金;
关键词
Cycle nodes ratio; Network classification; Giant component; Depth first search; EMERGENCE; GRAPH;
D O I
10.1016/j.cnsns.2021.105804
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Cycles, which can be found in many different kinds of networks, make the problems more intractable, especially when dealing with dynamical processes on networks. On the contrary, tree networks in which no cycle exists, are simplifications and usually allow for analyticity. There lacks a quantity, however, to tell the ratio of cycles which determines the extent of network being close to tree networks. Therefore we introduce the term Cycle Nodes Ratio (CNR) to describe the ratio of number of nodes belonging to cycles to the number of total nodes, and provide an algorithm to calculate CNR. CNR is studied in both network models and real networks. The CNR remains unchanged in different sized Erdos--Renyi (ER) networks with the same average degree, and increases with the average degree, which yields a critical turning point. The approximate analytical solutions of CNR in ER networks are given, which fits the simulations well. Furthermore, the difference between CNR and two-core ratio (TCR) is analyzed. The critical phenomenon is explored by analysing the giant component of networks. We compare the CNR in network models and real networks, and find the latter is generally smaller. Combining the coarse graining method can distinguish the CNR structure of networks with high average degree. The CNR is also applied to four different kinds of transportation networks and fungal networks, which give rise to different zones of effect. It is interesting to see that CNR is very useful in network recognition of machine learning. (c) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数:14
相关论文
共 46 条
[1]  
[Anonymous], 1961, Acta Math. Acad. Sci. Hungar., DOI DOI 10.1007/BF02066689
[2]   Classification of complex networks based on similarity of topological network features [J].
Attar, Niousha ;
Aliakbary, Sadegh .
CHAOS, 2017, 27 (09)
[3]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[4]  
Batagelj V., PAJEK DATASETS OL
[5]  
BAVELAS A, 1950, J. Acoustical Soc. Am, V22, P723, DOI DOI 10.1121/1.1906679
[6]   Number of loops of size h in growing scale-free networks -: art. no. 078701 [J].
Bianconi, G ;
Capocci, A .
PHYSICAL REVIEW LETTERS, 2003, 90 (07) :4
[7]  
Bollobas B., 2001, Random graphs, V73
[8]  
Brin S, 2012, COMPUT NETW, V56, P3825, DOI 10.1016/j.comnet.2012.10.007
[9]   Message passing on networks with loops [J].
Cantwell, George T. ;
Newman, M. E. J. .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2019, 116 (47) :23398-23403
[10]  
ERDOS P, 1960, B INT STATIST INST, V38, P343