基于生成函数方法的现实网络座键渗流建模

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

摘要/Abstract

摘要：

基于生成函数方法针对现实网络构建座键渗流模型, 并应用于4种有代表性的具体网络, 检验其对关键渗流指标估计的精确程度, 讨论模型估计误差成因, 同时给出其简单应用。所得现实网络渗流模型可应用于估计各类现实网络承受点边打击之后的连通状态, 也可以用来评估现实网络的整体抗毁程度。该模型处理过程简单, 预测结果精度与信息传播算法的结果精度相比可以被接受, 其计算用时则远低于信息传播算法, 具备很好的应用潜力。

关键词: 复杂网络, 座键渗流, 生成函数, 相变

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

付韬, 邬龙, 李晨光. 基于生成函数方法的现实网络座键渗流建模[J]. 计算物理, 2022, 39(2): 212-222.

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.

图/表 7

图1 座键渗流模型随机抽取一条边导向的连通点聚结点数量生成函数H1(x)组成机理示意图(a)网络未经历结点和边打击；(b)网络经历了结点和边打击(圆圈代表点，直线代表边，直线连接方框代表H1(x)。)

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.)

表1 4种具体网络的基础结构指标

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

图2 座键渗流模型S估计值与实际模拟结果(虚线为本文座键渗流模型得出的估计值，实线为文献[17-18]提出的信息传播算法得出的估计值，圆点实线为实际模拟结果。模拟结果是100次点边打击模拟结果的平均值。) (a)~(c) ER随机网络；(d)~(f) Internet自治系统拓扑片段；(g)~(i) 美国西部诸州输电网络；(j)~(l) 科学家合著作网络片段

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

表2 座键渗流相变临界值(PsPb临界值)的估计值和实际模拟结果

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

图3 座键渗流模型H′0(1)估计值与实际模拟结果(虚线为本文座键渗流模型得出的估计值，圆点实线代表实际模拟结果，该模拟结果是100次点边打击模拟结果的平均值。) (a) ER随机网络；(b) Internet自治系统拓扑片段；(c) 美国西部诸州输电网络；(d)科学家合著作网络片段

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

图4 美国西部诸州输电网络S估计值误差绝对值，打击后不属于极大连通点聚的3度及以上点数量和比例的变化趋势 (无色填充圆柱为S估计值误差绝对值，斜线填充圆柱为不属于极大连通点聚的3度及以上点数量，黑色填充圆柱代表不属于极大连通点聚的3度及以上点占全部3度及以上点比例。为了便于比较，三者分别除以其自身最大值得出标准化比例。所有模拟结果是100次点边打击模拟结果的平均值。)

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.)

图5 座键渗流模型全(Ps, Pb)组合下的S估计值(a)ER随机网络；(b)Internet自治系统拓扑片段；(c)科学家合著作网络片段

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

参考文献 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]	张少泽, 邹艳丽, 谭秫毅, 李浩乾, 刘欣妍. 基于复杂网络理论的互联电网Braess悖论现象分析[J]. 计算物理, 2022, 39(2): 233-243.
[2]	李浩乾, 邹艳丽, 张少泽, 刘欣妍, 谭秫毅. 基于复杂网络的电网结构健壮性及Braess悖论现象研究[J]. 计算物理, 2021, 38(4): 470-478.
[3]	王子墨, 李凌. 超短激光打孔中快速相变的格子玻尔兹曼模拟[J]. 计算物理, 2020, 37(3): 299-306.
[4]	李琼, 刘海风, 张弓木, 张其黎. 模拟退火算法在化学自由能模型中的应用[J]. 计算物理, 2019, 36(3): 259-264.
[5]	王意, 邹艳丽, 黄李, 李可. 综合考虑局部和全局特性的电网关键节点识别[J]. 计算物理, 2018, 35(1): 119-126.
[6]	刘昌宇, 李仔武, 李栋. 含相变材料玻璃类围护结构传热系数分析[J]. 计算物理, 2016, 33(4): 427-433.
[7]	吴海娜, 公卫江, 易光宇, 魏国柱. 纵向横向晶体场中自旋为1的量子伊辛二聚化链的基态[J]. 计算物理, 2015, 32(3): 374-378.
[8]	安海岗. 基于复杂网络的时间序列双变量联动波动[J]. 计算物理, 2014, 31(6): 742-750.
[9]	刘超, 石艺娜, 秦承森, 梁仙红. α铁冲击相变的离散元方法[J]. 计算物理, 2014, 31(1): 51-58.
[10]	范文礼, 刘志刚. 一种基于效率矩阵的网络节点重要度评价算法[J]. 计算物理, 2013, 30(5): 714-719.
[11]	胡安杰, 李隆键, 曾建邦. 作用力求取方法对多相伪势模型的影响[J]. 计算物理, 2012, 29(6): 828-836.
[12]	赵元松, 梁卫华, 陈文振. 围绕变壁温水平圆柱热源接触熔化的理论分析[J]. 计算物理, 2012, 29(2): 257-262.
[13]	唐圣学, 陈丽, 黄姣英. 关联复杂网络建模及辨识研究[J]. 计算物理, 2012, 29(2): 308-316.
[14]	黄勇, 宣益民, 李强. 水平圆管内磁性潜热型功能流体对流换热特性的数值模拟[J]. 计算物理, 2012, 29(1): 87-94.
[15]	赵元松, 梁卫华, 陈文振. 圆管内自由固体相变材料定热流接触熔化[J]. 计算物理, 2011, 28(4): 529-534.