Site-bond Percolation Modeling of Real Networks: Generating Function Method

doi:10.19596/j.cnki.1001-246x.8362

Abstract

Abstract:

We propose a site-bond percolation model based on generating function method, and then apply it to four representative concrete networks to observe accuracy of its estimates. Finally, we discuss causes of the inaccuracy and give simple applications. Our site-bond percolation model could be used to anticipate the connectivity of various real networks after site and bond attack and study their entire robustness. Process procedure of the model is simple, and the accuracy of its estimates is acceptable compared with that calculated with the message passing algorithm. Meanwhile, its calculation time is much lower than that of the information passing algorithm. Therefore, it has good application potential.

Key words: complex network, site-bond percolation, generating function, phase transition

Tao FU, Long WU, Chenguang LI. Site-bond Percolation Modeling of Real Networks: Generating Function Method[J]. Chinese Journal of Computational Physics, 2022, 39(2): 212-222.

Figures/Tables 7

Fig.1 A schematic of the sum rule for connected component reachable by following a randomly chosen edge (H1(x)) (a) The network under no node or edge removal, and (b) the network after node and edge removal (The circles denote nodes and the squares denote components.)

Table 1 Structural characteristics of four real-world networks

	结点数量	密度	结点度平均值	结点度最大值	平均距离	平均簇系数
ER随机网络	10 000	0.000	4.956	15	5.934	0.001
Internet自治系统拓扑片段	10 000	0.001	5.042	1 565	3.457	0.414
美国西部诸州输电网络	4 941	0.001	2.669	19	18.989	0.080
科学家合著网络片段	10 000	0.001	9.290	178	5.007	0.550

Fig.2 Analytic estimates and simulation values of S (Solid and dashed lines denote estimates of the message passing algorithm in Ref. [17-18] and our model, respectively. Solid-circle lines are from direct numerical simulations on the same networks and averaged over 100 repetitions.) (a)-(c) results for an ER random graph; (d)-(f) results for a part of the structure of the internet at the level of autonomous systems; (g)-(i) results for the western states power grid of the United States; (j)-(l) results for a part of the scientific collaboration networks

Table 2 Site-bond percolation thresholds estimated with message passing algorithm, our model and from direct numerical simulation

	本文模型	信息传播算法	实际模拟值
ER随机网络	0.203	0.203	0.235
Internet自治系统拓扑片段	0.005	0.016	0.018
美国西部诸州输电网络	0.348	0.161	0.570
科学家合著网络片段	0.046	0.025	0.092

Fig.3 Analytic estimates and simulation values of H′0(1) (Dashed lines denote estimates of our model. Solid-circle lines are from direct numerical simulations on the same networks and averaged over 100 repetitions.) (a) results for an ER random graph; (b) results for a part of the structure of the Internet at the level of autonomous systems; (c) results for the western states power grid of the United States; (d) results for a part of the scientific collaboration networks

Fig.4 Evolution trend of the absolute value of S discrepancy, the number and the proportion of those nodes with the degree equal to or more than 3 out of the giant component (The colorless filled cylinders denote the absolute value of S discrepancy. The oblique line filled cylinders denote the number of nodes with the degree equal to or more than 3 out of the giant component. And the black filled cylinders represent the proportion of those nodes to all nodes with the degree equal to or more than 3.)

Fig.5 S estimated by the site-bond model under all combined values of Ps and Pb (a) results for an ER random graph; (b) results for a part of the structure of the Internet at the level of autonomous systems; (c) results for a part of the scientific collaboration networks

References 21

1	FILIPPO R , CLAUDIO C . Breaking of the site-bond percolation universality in networks[J]. Nature Communications, 2015, (6): 10196.
2	ZHANG N , YAO J , HUANG Z , et al. Locally conservative Galerkin numerical simulation for two-phase flow in porous media[J]. Chinese Journal of Computational Physics, 2013, 30 (5): 667- 674.
3	LIU W , YAO J , WANG J . Front tracking for moving boundary of non-Darcy seepage flow in low-permeability porous media[J]. Chinese Journal of Computational Physics, 2012, 29 (6): 823- 827.
4	WANG H , CHAI Z , GUO Z . Lattice Boltzmann simulation of gas transfusion in compact porous media[J]. Chinese Journal of Computational Physics, 2009, 26 (3): 389- 395.
5	PASTOR-SATORRAS R , VESPIGNANI A . Epidemic spreading in scale-free networks[J]. Physical Review Letters, 2001, 86 (14): 3200- 3203. DOI
6	CASTELLANO C , PASTOR-SATORRAS R . On the numerical study of percolation and epidemic critical properties in networks[J]. The European Physical Journal B, 2016, 89 (11): 243. DOI
7	ROSAS-CASALS M , VALVERDE S , SOLÉ R V . Topological vulnerability of the European power grid under errors and attacks[J]. International Journal of Bifurcation and Chaos, 2007, 17 (7): 2465- 2475. DOI
8	CHEN G , DONG Z Y , HILL D J , et al. Attack structural vulnerability of power grids: A hybrid approach based on complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389 (3): 595- 603. DOI
9	COHEN R , EREZ K , BEN-AVRAHAM D , et al. Resilience of the internet to random breakdowns[J]. Physical Review Letters, 2000, 85 (21): 4626. DOI
10	COHEN R , EREZ K , BEN-AVRAHAM D , et al. Breakdown of the Internet under intentional attack[J]. Physical Review Letters, 2001, 86 (16): 3682. DOI
11	SU Z , LI L , PENG H , et al. Robustness of interrelated traffic networks to cascading failures[J]. Scientific Reports, 2014, 4 (1): 5413.
12	WANG F , LI D , XU X , et al. Percolation properties in a traffic model[J]. Europhysics Letters, 2015, 112 (3): 38001. DOI
13	NEWMAN M E J , STROGATZ S H , WATTS D J . Random graphs with arbitrary degree distributions and their applications[J]. Physical Review E, 2001, 64 (2): 026118. DOI
14	WILF H S . Generating functionology[M]. 3rd ed London: Academic Press, 2005.
15	LEICHT E A, D'SOUZA R M. Percolation on interacting networks[EB/OL]. http://arxiv.org/abs/0907.0894.2009.
16	FU T , CHEN Y N , QIN Z , et al. Percolation on shopping and cashback electronic commerce networks[J]. Physica A, 2013, 392 (12): 2807- 2820. DOI
17	KARRER B , NEWMAN M E . Message passing approach for general epidemic models[J]. Physical Review E, 2010, 82 (1): 016101. DOI
18	RADICCHI F , CASTELLANO C . Beyond the locally treelike approximation for percolation on real networks[J]. Physical Review E, 2016, 93 (3): 030302. DOI
19	FU T , ZOU L L , LI C G . A relatively simple model for percolation properties of real networks[J]. Physics Letters A, 2017, 381 (32): 2578- 2582. DOI
20	WATTS D J , STROGATZ S H . Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393 (6684): 440- 442. DOI
21	NEWMAN M E J . The structure of scientific collaboration networks[J]. Proceedings of the National Academy of Sciences, 2001, 98 (2): 404- 409. DOI

[1]	Shaoze ZHANG, Yanli ZOU, Shuyi TAN, Haoqian LI, Xinyan LIU. Analysis of Braess Paradox in an Interconnected Power Grid Based on Complex Network Theory [J]. Chinese Journal of Computational Physics, 2022, 39(2): 233-243.
[2]	Haoqian LI, Yanli ZOU, Shaoze ZHANG, Xinyan LIU, Shuyi TAN. Robustness of Power Grids Structure and Braess Paradox Phenomenon: A Complex Network Theory Study [J]. Chinese Journal of Computational Physics, 2021, 38(4): 470-478.
[3]	LI Qiong, LIU Haifeng, ZHANG Gongmu, ZHANG Qili. Application of Simulated Annealing Method in Chemical Free Energy Model [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2019, 36(3): 259-264.
[4]	LIU Lihua, WEI Duqu, ZHANG Bo. Synchronization Control of Chaos in Complex Motor Networks with Small-world Topology Based on Dynamic Relaying [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2018, 35(6): 750-756.
[5]	WANG Yi, ZOU Yanli, HUANG Li, LI Ke. Key Nodes Identification of Power Grid Considering Local and Global Characteristics [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2018, 35(1): 119-126.
[6]	WU Haina, GONG Weijiang, YI Guangyu, WEI Guozhu. Ground States of Dimerized Spin-1 lsing Chain with Both Longitudinal and Transverse Single-Ion Anisotropies [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2015, 32(3): 374-378.
[7]	AN haigang. Linkage Fluctuation in Double Variables of Time Series Based on Complex Networks [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2014, 31(6): 742-750.
[8]	LIU Chao, SHI Yina, QIN Chengsen, LIANG Xianhong. Shock Induced α-Iron Phase Transition in DEM [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2014, 31(1): 51-58.
[9]	FAN Wenli, LIU Zhigang. An Evaluation Method for Node Importance Based on Efficiency Matrix [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2013, 30(5): 714-719.
[10]	TANG Shengxue, CHEN Li, HUANG Jiaoying. Modeling and Identification of Associated Complex Networks [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2012, 29(2): 308-316.
[11]	XIE Liqiang. Numerical Calculation of Vesicle Shapes with High Topological Genus [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2009, 26(5): 763-766.
[12]	YANG Peipei, LIU Hong, LIU Hong. Monte Carlo Simulation of Nematic Liquid Crystals [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2009, 26(4): 597-602.
[13]	ZHAO Kai, LI Qiang, XUAN Yimin. Simulation of Phase Transition with Lattice Boltzmann Method [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2008, 25(2): 151-156.
[14]	YU Hua-ping, WANG Shuang-hu. The Construction of Jet Symplectic Difference Scheme for Hamiltonian Systems via Generating Functions [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2005, 22(3): 206-216.
[15]	ZHOU Guo-xiang, WANG Ai-kun, HE Wen-chen, LI Guo-chang. A Study on the Ferroelastic Phase Transition in Cubic Systems with the Slowness-Curved-Surface [J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2005, 22(3): 217-220.