Betweenness Centrality of Fractal and Non-Fractal Scale-Free Model Networks and Tests on Real Networks

Kitsak, Maksim and Havlin, Shlomo and Paul, Gerald and Riccaboni, Massimo and Pammolli, Fabio and Stanley, H. Eugene (2007): Betweenness Centrality of Fractal and Non-Fractal Scale-Free Model Networks and Tests on Real Networks. Published in: Physical Review E , Vol. 75, No. 5 (31 May 2007): 056115.

Abstract

We study the betweenness centrality of fractal and non-fractal scale-free network models as well as real networks. We show that the correlation between degree and betweenness centrality C of nodes is much weaker in fractal network models compared to non-fractal models. We also show that nodes of both fractal and non-fractal scale-free networks have power law betweenness centrality distribution P(C) ~ C^δ. We find that for non-fractal scale-free networks δ = -2, and for fractal scale-free networks δ = -2 + 1/dB, where dB is the dimension of the fractal network. We support these results by explicit calculations on four real networks: pharmaceutical firms (N = 6776), yeast (N = 1458), WWW (N = 2526), and a sample of Internet network at AS level (N = 20566), where N is the number of nodes in the largest connected component of a network. We also study the crossover phenomenon from fractal to non-fractal networks upon adding random edges to a fractal network. We show that the crossover length ℓ*, separating fractal and non-fractal regimes, scales with dimension dB of the network as p−1/dB, where p is the density of random edges added to the network. We find that the correlation between degree and betweenness centrality increases with p.

• Item Type: MPRA Paper
• Language: English
• Keywords: Interfirm networks; R&D collaborations, Pharmaceutical industry; ICT.
• Subjects: L - Industrial Organization > L6 - Industry Studies: Manufacturing > L65 - Chemicals ; Rubber ; Drugs ; Biotechnology; L - Industrial Organization > L2 - Firm Objectives, Organization, and Behavior > L25 - Firm Performance: Size, Diversification, and Scope; O - Economic Development, Innovation, Technological Change, and Growth > O3 - Innovation ; Research and Development ; Technological Change ; Intellectual Property Rights > O30 - General; E - Macroeconomics and Monetary Economics > E1 - General Aggregative Models > E17 - Forecasting and Simulation: Models and Applications; L - Industrial Organization > L6 - Industry Studies: Manufacturing > L60 - General; L - Industrial Organization > L0 - General > L00 - General; L - Industrial Organization > L6 - Industry Studies: Manufacturing > L63 - Microelectronics ; Computers ; Communications Equipment

References

Albert R., Barabasi A.L. (2002): “Statistical mechanics of complex networks”, Reviews of Modern Physics 74, 47-97.

Dorogovtsev S.N., Mendes J.F.F. (2002): Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford University Press, Oxford.

Pastor-Satorras R., Vespignani A. (2004): Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, Cambridge.

Cohen R., Havlin S. (2007): Complex Networks: Stability, Structure and Function,Cambridge University Press, Cambridge.

Erdos P., Renyi A. (1959): “On random graphs” Publ. Math. Inst. Hung. Acad. Sci. 6, 290 (1959).

Erdos P., Renyi A. (1960): “On the evolution of random graphs” Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).

Bollobas B. (2001): Random Graphs, Cambridge University Press, Cambridge.

Milgram S. (1967): “The small world problem” Psychology Today 2, 60.

Watts D.J., Strogatz S.H. (1998): “Small World”, Nature 393, 440-442.

Albert R., Jeong H., Barabasi A.L. (1999): “Diameter of the world wide web”, Nature 401, 130 (1999).

Barabasi A.L., Albert R. (1999): “Emergence of scaling in random networks”, Science 286, 509 (1999).

Faloutsos M., Faloutsos P., Faloutsos C. (1999): “On Power-law Relationships of the Internet Topology”, Computer Communication Review 29, 251-262.

Song C., Havlin S., Makse H. (2005):“Self-similarity of complex networks”, Nature 433, 392-395.

Song C., Havlin S., Makse H. (2006): “Origins of fractality in the growth of complex networks”, Nature Physics 2, 275-281.

Goh K.I., Salvi G., Kahng B., Kim D. (2006): “Skeleton and Fractal Scaling in Complex Networks”, Physical Review Letters 96, 018701.

Kim J.S., Goh K.I., Salvi G., Oh E., Kahng B., Kim D. (2007): “Fractality in complex networks: Critical and supercritical skeletons”, Physical Review E 75, 016110.

Yook S.H., Radicchi F., Meyer-Ortmanns H. (2005): “Self-similar scale-free networks and disassortativity”, Physical Review E. 72, 045105(R).

Feder J. (1988), Fractals, Plenum, New York.

Newman M.E.J. (2002): “Assortative mixing in networks”, Physical Review Letters 89, 208701.

Freeman L.C. (1979): “Centrality in social networks: Conceptual clarification”, Social Networks 1, 215-239.

Wasserman S., Faust K. (1994), Social Network Analysis, Cambridge University Press, Cambridge.

Scott J. (2000), Social Network Analysis: A Handbook, Sage Publications, London.

Newman M.E.J. (2001): “Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality”, Physical Review E. 64, 016132.

Wu Z., Braunstein L.A., Havlin S., Stanley H.E. (2006): “Transport in weighted networks: Partition into superhighways and roads”, Physical review letters 96, 148702.

Orsenigo L., Pammolli F., Riccaboni M. (2001): “Technological change and network dynamics Lessons from the pharmaceutical industry”, Research Policy, 30(3), 485.

Carmi S., Havlin S., Kirkpatrick S., Shavitt Y., Shir E. (2006): “Medusa - new model of Internet topology using k-shell decomposition”, Tech. Rep., arXiv, Jan. 2006.

Jeong H., Mason S., Barabasi A.L., Oltvai Z.N. (2001): “Lethality and centrality in protein networks”, Nature 411, 41.

Holme P., Kim B.J., Yoon C.N., Han S.K. (2002): “Attack vulnerability of complex networks”, Physical Review E 65, 056109.

Kim D.H., Noh J.D., Jeong H. (2004): “Scale-free trees: the skeletons of complex networks”, Physical Review E 70, 046126.

Goh K.I., Noh J.D., Kahng B., Kim D. (2005): “Load distribution in weighted complex networks”, Physical Review E 72, 017102.

Braunstein L.A., Wu Z., Kalisky, Chen T.Y., Sreenivasan S., Cohen R., Lopez E., Buldyrev S.V., Havlin S., Stanley H.E. (2007), “Optimal Path and Minimal Spanning Trees in Random Weighted Networks”, Journal of Bifurcation and Chaos Vol. 17, No. 7 2215–2255.

Bunde A., S. Havlin (1996), Fractals in Science, Springer, Berlin.