Multifractal analysis of complex networks

doi:10.1088/1674-1056/21/8/080504

Abstract Complex networks have recently attracted much attention in diverse areas of science and technology. Many networks such as the WWW and biological networks are known to display spatial heterogeneity which can be characterized by their fractal dimensions. Multifractal analysis is a useful way to systematically describe the spatial heterogeneity of both theoretical and experimental fractal patterns. In this paper, we introduce a new box covering algorithm for multifractal analysis of complex networks. This algorithm is used to calculate the generalized fractal dimensions D_q of some theoretical networks, namely scale-free networks, small world networks, and random networks, and one kind of real networks, namely protein-protein interaction networks of different species. Our numerical results indicate the existence of multifractality in scale-free networks and protein-protein interaction networks, while the multifractal behavior is not clear-cut for small world networks and random networks. The possible variation of D_q due to changes in the parameters of the theoretical network models is also discussed.

Keywords: complex networks multifractality box covering algorithm

Received: 02 February 2012
Revised: 01 March 2012
Accepted manuscript online:

PACS:	05.45.Df	(Fractals)
	47.53.+n	(Fractals in fluid dynamics)
	89.75.Hc	(Networks and genealogical trees)

Fund: Project supported by the Australian Research Council (Grant No. DP0559807), the National Natural Science Foundation of China (Grant No. 11071282), the Science Fund for Changjiang Scholars and Innovative Research Team in University (PCSIRT) (Grant No. IRT1179), the Program for New Century Excellent Talents in University (Grant No. NCET-08-06867), the Research Foundation of the Education Department of Hunan Province of China (Grant No. 11A122), the Natural Science Foundation of Hunan Province of China (Grant No. 10JJ7001), the Science and Technology Planning Project of Hunan Province of China (Grant No. 2011FJ2011), the Lotus Scholars Program of Hunan Province of China, the Aid Program for Science and Technology Innovative Research Team in Higher Education Institutions of Hunan Province of China, and a China Scholarship Council-Queensland University of Technology Joint Scholarship.

Corresponding Authors: Yu Zu-Guo
E-mail: yuzg@hotmail.com

Cite this article:

Wang Dan-Ling (王丹龄), Yu Zu-Guo (喻祖国), Anh V Multifractal analysis of complex networks 2012 Chin. Phys. B 21 080504

[1]	Song C, Havlin S and Makse H A 2005 Nature 433 392
[2]	Lee C Y and Jung S 2006 Phys. Rev. E 73 066102
[3]	Guo L and Cai X 2009 Chin. Phys. Lett. 26 088901
[4]	Erdös P and Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[5]	Milgram S 1967 Psychol. Today 2 60
[6]	Albert R, Jeong H and Barabasi A L 1999 Nature 401 130
[7]	Albert R and Barabasi A L 2002 Rev. Mod. Phys. 74 47
[8]	Faloutsos M, Faloutsos P and Faloutsos C 1999 Comput. Commun. Rev. 29 251
[9]	Mandelbrot B B 1983 The Fractal Geometry of Nature (New York: Academic Press)
[10]	Feder J 1988 Fractals (New York: Plenum)
[11]	Falconer K 1997 Techniques in Fractal Geometry (New York: Wiley)
[12]	Eguiluz V M, Hernandez-Garcia E, Piro O and Klemm K 2003 Phys. Rev. E 68 055102(R)
[13]	Song C, Gallos L K, Havlin S and Makse H A 2007 J. Stat. Mech.: Theor. Exp. 3 P03006
[14]	Kim J S, Goh K I, Salvi G, Oh E, Kahng B and Kim D 2007 Phys. Rev. E 75 016110
[15]	Zhou W X, Jiang Z Q and Sornette D 2007 Physica A 375 741
[16]	Gao L, Hu Y and Di Z 2008 Phys. Rev. E 78 046109
[17]	Shanker O 2007 Mod. Phys. Lett. B 21 321
[18]	Rozenfeld H D and Makse H A 2009 Chem. Eng. Sci. 64 4572
[19]	Rozenfeld H D, Song C and Makse H A 2010 Phys. Rev. Lett. 104 025701
[20]	Liu J X and Kong X M 2010 Acta Phys. Sin. 59 2244 (in Chinese)
[21]	Grassberger P and Procaccia I 1983 Phys. Rev. Lett. 50 346
[22]	Halsey T C, Jensen M H, Kadanoff L P, Procaccia I and Shraiman B I 1986 Phys. Rev. A 33 1141
[23]	Canessa E 2000 J. Phys. A: Math. Gen. 33 3637
[24]	Anh V V, Tieng Q M and Tse Y K 2000 Int. Trans. Oper. Res. 7 349
[25]	Yu Z G, Anh V and Lau K S 2001 Physica A 301 351
[26]	Yu Z G, Anh V and Lau K S 2001 Phys. Rev. E 64 31903
[27]	Yu Z G, Anh V and Wang B 2001 Phys. Rev. E 63 11903
[28]	Anh V, Lau K S and Yu Z G 2002 Phys. Rev. E 66 031910
[29]	Yu Z G, Anh V and Lau K S 2003 Phys. Rev. E 68 021913
[30]	Yu Z G, Anh V and Lau K S 2004 J. Theor. Biol. 226 341
[31]	Zhou L Q, Yu Z G, Deng J Q, Anh V and Long S C 2005 J. Theor. Biol. 232 559
[32]	Yu Z G, Anh V, Lau K S and Zhou L Q 2006 Phys. Rev. E 73 031920
[33]	Yu Z G, Xiao Q J, Shi L, Yu J W and Anh V 2010 Chin. Phys. B 19 068701
[34]	Zhu S M, Yu Z G and Anh V 2011 Chin. Phys. B 20 010505
[35]	Han J J and Fu W J 2010 Chin. Phys. B 19 010205
[36]	Kantelhardt J W, Koscielny-Bunde E, Rybski D, Braun P, Bunde A and Havlin S 2006 J. Geophys. Res. 111 D01106
[37]	Veneziano D, Langousis A and Furcolo P 2006 Water Resour. Res. 42 W06D15
[38]	Venugopal V, Roux S G, Foufoula-Georgiou E and Arneodo A 2006 Water Resour. Res. 42 W06D14
[39]	Yu Z G, Anh V, Wanliss J A and Watson S M 2007 Chaos, Solitons and Fractals 31 736
[40]	Zang B J and Shang P J 2007 Chin. Phys. 16 565
[41]	Yu Z G, Anh V and Eastes R 2009 J. Geophys. Res. 114 A 05214
[42]	Yu Z G, Anh V, Wang Y, Mao D and Wanliss J 2010 J. Geophys. Res. 115 A 10219
[43]	Polla G, Lovasz L and Vicsek T 2010 Proc. Natl. Acad. Sci. USA 107 7640
[44]	Dijkstra E W 1959 Numerische Mathematik 1 269
[45]	Newman M E J 2003 SIAM Rev. 45 167
[46]	Barabsi A L and Albert R 1999 Science 286 509
[47]	Newman M E J and Watts D J 1999 Phys. Lett. A 263 341
[48]	Watts D J and Strogatz S H 1998 Nature 393 440
[49]	Opheusden J H H, Bos M T A and van der Kaaden G 1996 Physica A 227 183
[50]	Smith T G and Lange G D 1998 Fractal in Biology and Medicine eds. Nonnenmacher T F, Losa G A and Weibel E R (Basel: Birkhäuser)
[51]	Fernández E, Bolea J A, Ortega G and Louis E 1999 J. Neurosci. Methods 89 151
[52]	Cytoscape software: http://cytoscapeweb.cytoscape.org/
[53]	BioGRID: http://thebiogrid.org/download.php
[54]	DIP: http://dip.doe-mbi.ucla.edu/dip/Download.cgi
[55]	Lee E, Jung H, Radivojac P, Kim J W and Lee D 2009 BMC Bioinformatics 10 (Suppl. 2) S2

[1]	Analysis of cut vertex in the control of complex networks Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Chin. Phys. B, 2023, 32(2): 028902.
[2]	Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Chin. Phys. B, 2023, 32(1): 018903.
[3]	Characteristics of vapor based on complex networks in China Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Chin. Phys. B, 2022, 31(4): 049201.
[4]	Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Chin. Phys. B, 2022, 31(2): 020503.
[5]	Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Chin. Phys. B, 2022, 31(10): 100504.
[6]	LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). Chin. Phys. B, 2021, 30(8): 088901.
[7]	Complex network perspective on modelling chaotic systems via machine learning Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Chin. Phys. B, 2021, 30(6): 060506.
[8]	Exploring individuals' effective preventive measures against epidemics through reinforcement learning Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni (倪顺江), and Shi-Fei Shen(申世飞). Chin. Phys. B, 2021, 30(4): 048901.
[9]	Influential nodes identification in complex networks based on global and local information Yuan-Zhi Yang(杨远志), Min Hu(胡敏), Tai-Yu Huang(黄泰愚). Chin. Phys. B, 2020, 29(8): 088903.
[10]	Identifying influential spreaders in complex networks based on entropy weight method and gravity law Xiao-Li Yan(闫小丽), Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni(倪顺江). Chin. Phys. B, 2020, 29(4): 048902.
[11]	Modeling and analysis of the ocean dynamic with Gaussian complex network Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇)†, Christian B\"ohm, and Xueen Chen(陈学恩). Chin. Phys. B, 2020, 29(10): 108901.
[12]	Pyramid scheme model for consumption rebate frauds Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[13]	Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms Shi-Zhao Zhu(朱世钊), Yu-Qing Wang(王玉青), Bing-Hong Wang(汪秉宏). Chin. Phys. B, 2019, 28(10): 108901.
[14]	Coordinated chaos control of urban expressway based on synchronization of complex networks Ming-bao Pang(庞明宝), Yu-man Huang(黄玉满). Chin. Phys. B, 2018, 27(11): 118902.
[15]	Detecting overlapping communities based on vital nodes in complex networks Xingyuan Wang(王兴元), Yu Wang(王宇), Xiaomeng Qin(秦小蒙), Rui Li(李睿), Justine Eustace. Chin. Phys. B, 2018, 27(10): 100504.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Online attention

Altmetric

6 tweeters

Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.

View more on Altmetrics

Metrics
Related Articles