Classification of scale-free networks.pdf

Classification of scale-free networks Kwang-Il Goh*, Eulsik Oh*, Hawoong Jeong?, Byungnam Kahng*?, and Doochul Kim* *School of Physics and Center for Theoretical Physics, Seoul National University, Seoul 151-747, Korea; and ?Department of Physics, Korea Advanced Institute of Science and Technology, Daejon 305-701, Korea Edited by Leo P. Kadanoff, University of Chicago, Chicago, IL, and approved August 7, 2002 (received for review May 20, 2002) While the emergence of a power-law degree distribution in com- plex networks is intriguing, the degree exponent is not universal. Here we show that the betweenness centrality displays a power- law distribution with an exponent
, which is robust, and use it to classify the scale-free networks. We have observed two universal- ity classes with

2.2(1) and 2.0, respectively. Real-world net- works for the former are the protein-interaction networks, the metabolic networks for eukaryotes and bacteria, and the coau- thorship network, and those for the latter one are the Internet, the World Wide Web, and the metabolic networks for Archaea. Distinct features of the mass-distance relation, generic topology of geo- desics, and resilience under attack of the two classes are identified. Various model networks also belong to either of the two classes, while their degree exponents are tunable. Emergence of a power law in the degree distribution PD(k)  k
in complex networks is an interesting self-organized phenom- enon in complex systems (1–3). Here, the degree k means the number of edges incident upon a given vertex. Such a network is called scale-free (SF; ref. 4). Real-world networks that are SF include the author-collaboration network (5) in social systems, the protein-interaction network (PIN; ref. 6), and the metabolic net- work (7) in biological systems, and the Internet (8) and World Wide Web (WWW; refs. 9 and 10) in communication systems. The power-law behavior means that most vertices are connected sparsely, while a few vertic