TY - JOUR
T1 - Underlying scale-free trees in complex networks
AU - Kim, Donghee
AU - Son, Seung-woo
AU - Ahn, Yong-Yeol
AU - Kim, Pan Jun
AU - Eom, Youngho
AU - Jeong, Hawoong
N1 - This work was supported in part by grant No. R08-2003-000-10285-0 from the Basic Research Program of KOSEF and Ministry of Science and Technology through Korean Systems Biology Research Grant (M10309020000-03B5002-00000).
PY - 2005/1
Y1 - 2005/1
N2 - We investigate the properties of two relatively different spanning trees of complex networks, so-called "communication kernel" and "response network". First, for the communication kernel, we construct spanning trees carrying a maximum total weight of edges that is given by average traffic, which is defined as edge betweenness centrality. It is found that the resulting spanning tree plays an important role in communication between vertices. We also find that the degree distribution of spanning trees shows scale-free behavior for many model and real-world networks and the degree of the spanning trees has strong correlation with their original network topology. For the response network, we launch an attack on a single vertex which can drastically change the communication pattern between vertices of networks. By using minimum spanning tree technique, we construct the response network based on the measurement of the betweenness centrality changes due to a vertex removal. We find that the degree distribution of the response network indicates the scale-free behavior as well as that of the communication kernel. Interestingly, these two minimum spanning trees from different methods not only have same scale-free behavior but overlap each other in their structures. This fact indicates that the complex network has a concrete skeleton, scale-free tree, as a basic structure.
AB - We investigate the properties of two relatively different spanning trees of complex networks, so-called "communication kernel" and "response network". First, for the communication kernel, we construct spanning trees carrying a maximum total weight of edges that is given by average traffic, which is defined as edge betweenness centrality. It is found that the resulting spanning tree plays an important role in communication between vertices. We also find that the degree distribution of spanning trees shows scale-free behavior for many model and real-world networks and the degree of the spanning trees has strong correlation with their original network topology. For the response network, we launch an attack on a single vertex which can drastically change the communication pattern between vertices of networks. By using minimum spanning tree technique, we construct the response network based on the measurement of the betweenness centrality changes due to a vertex removal. We find that the degree distribution of the response network indicates the scale-free behavior as well as that of the communication kernel. Interestingly, these two minimum spanning trees from different methods not only have same scale-free behavior but overlap each other in their structures. This fact indicates that the complex network has a concrete skeleton, scale-free tree, as a basic structure.
UR - http://www.scopus.com/inward/record.url?scp=22144455358&partnerID=8YFLogxK
U2 - 10.1143/PTPS.157.213
DO - 10.1143/PTPS.157.213
M3 - Journal article
AN - SCOPUS:22144455358
SN - 0375-9687
VL - 157
SP - 213
EP - 220
JO - Progress of Theoretical Physics Supplement
JF - Progress of Theoretical Physics Supplement
ER -