文摘
计算网络的鲁棒性,即。,the capacity of a network holding its main functionality when a proportion of its nodes/edges are damaged, is useful in many real applications. The Monte Carlo numerical simulation is the commonly used method to compute network robustness. However, it has a very high computational cost, especially for large networks. Here, we propose a methodology such that the robustness of large real-world social networks can be predicted using machine learning models, which are pretrained using existing datasets. We demonstrate this approach by simulating two effective node attack strategies, i.e., the recalculated degree (RD) and initial betweenness (IB) node attack strategies, and predicting network robustness by using two machine learning models, multiple linear regression (MLR) and the random forest (RF) algorithm. We use the classic network robustness metric<我>R我>作为模型反应和8网络结构指标(NSI)作为预测变量和大型数据集训练的48个真实的社交网络,节点的最大数量是265000。我们发现射频模型可以预测网络的鲁棒性与均方误差(RMSE)为0.03,比30%高模型。在结果中,我们发现RD策略效果比IB攻击现实世界的社交网络。此外,高表明,最重要的因素来预测网络的鲁棒性是无标度指数<我>α我>和平均节点度<<我>k我>>。相反,RF表明assortativity程度<我>一个我>,全球亲密,平均节点度<<我>k我>>是最重要的因素。这项研究表明,机器学习模型可以是一个有前途的方法来推断社交网络的鲁棒性。
1。介绍
社交网络的研究从复杂性科学的角度吸引了很多最近的兴趣(<一个href="#B1">1一个>]。特别是研究的动态过程,发生在这些复杂网络可以有各种各样的应用程序。例如,网络鲁棒性的研究,即,“network robustness” is the capacity of a network to hold its functionality when a proportion of nodes/edges are removed, can help attack a network efficiently, or inversely design a more robust network structure in practice [<一个href="#B2">2一个>- - - - - -<一个href="#B7">7一个>]。另一方面,研究流行过程,发生在网络可以用来传播新闻(<一个href="#B8">8一个>- - - - - -<一个href="#B12">12一个>),优化疫苗接种策略<一个href="#B13">13一个>- - - - - -<一个href="#B15">15一个>),或者定义一个更好的社会距离规则(<一个href="#B16">16一个>- - - - - -<一个href="#B19">19一个>]。
除了一些简单的模型网络分析模型可以开发(<一个href="#B20">20.一个>- - - - - -<一个href="#B24">24一个>),大多数的研究依赖于计算机模拟。例如,网络的鲁棒性,研究节点/边删除蒙特卡罗模拟通常采用。在这样一个过程中,节点/边使用电脑模拟顺序从网络中删除。“鲁棒性”指标然后记录删除过程的每一步。最常用的鲁棒性度量是最大的连接组件(LCC)的网络(<一个href="#B25">25一个>]。
要删除选中节点/边的方式叫做删除策略或攻击策略。人能攻击策略分为两类型进行分类,初步和重新计算攻击策略。首次攻击策略,节点/边被删除节点/边排名提前去除模拟计算。重新计算攻击策略相比,每个节点/边切除后的排名更新(<一个href="#B4">4一个>]。
删除节点的攻击策略,节点排名通常是计算使用节点中心度等措施(<一个href="#B26">26一个>,<一个href="#B27">27一个>,亲密<一个href="#B4">4一个>,中间状态(<一个href="#B7">7一个>,<一个href="#B30">30.一个>]。发现,社交网络,重新计算介数节点攻击策略(RB)是,平均而言,最有效的节点攻击策略拆除网络(<一个href="#B2">2一个>,<一个href="#B7">7一个>,<一个href="#B28">28一个>,<一个href="#B29">29日一个>]。其他有效的策略重新计算程度(RD)和最初的中间性(IB) [<一个href="#B7">7一个>,<一个href="#B28">28一个>,<一个href="#B30">30.一个>]。
因为顺序删除过程的本质,节点删除模拟计算昂贵,特别是对于重新计算策略。例如,模拟使用RD攻击策略的时间复杂度<我>O我>(<我>N我>×<我>E我>),<我>N我>节点和数量吗<我>E我>是网络的边的数量。原因是节点删除过程有一个<我>N我>一步,每一步,一定程度排名计算一次尺度<我>E我>。然而,对于RB,整个网络的计算计算中间状态是非常昂贵的,由于网络的节点介数的定义(<一个href="#B31">31日一个>,<一个href="#B32">32一个>]。已知最有效的算法计算网络中间性Brandes算法(<一个href="#B33">33一个>),时间复杂度为O (<我>N我>×<我>E我>)。结果,整个节点删除过程使用IB和RB攻击策略的时间复杂度O (<我>N我>×<我>E我>)和O (<我>N我>2分别×E)。尽管IB攻击策略相同的时间复杂度RD攻击策略,RB的时间复杂度要高得多。例子,在图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig1/" target="_blank">1一个>,我们现在总模拟时间tIB, tRD相应的攻击策略IB和RD,分别为我们所有的研究社交网络(48网络看部分<一个href="#sec2">2一个>)。此外,我们目前的攻击策略的总模拟时间民国RB 4网络(插入图)作为一个例子,作为产品的函数<我>N我>×<我>E我>。我们发现了一个很好的线性关系<我>t我>IB和<我>t我>理查德·道金斯和<我>N我>×<我>E我>对所有网络正如预期的那样,和民国高出两个数量级<我>t我>IB和<我>t我>理查德·道金斯网络等<我>N我>×<我>E我>。
仿真时间可以为社交网络的情况下成为一个问题,因为他们的规模非常大。事实上,据我们所知,大多数的研究动态过程在社交网络上,使用一个RB攻击策略只考虑小型少于100000节点的真实社交网络(<一个href="#B7">7一个>,<一个href="#B28">28一个>,<一个href="#B30">30.一个>]。对于非常大的社交网络,RB节点攻击策略可以采取一个不切实际的时间。因此,RB不适合大型社交网络平均电脑站。另一种可能性是使用betweenness-based攻击策略只有一个中间状态的计算,即最初的中间性攻击策略IB,连同其他重新计算策略使用另一个节点的中心度规,计算代价高昂。结果,在这工作,我们考虑两个候选人攻击策略打破大真实的社交网络,IB和RD攻击策略。除了比较研究不同网络节点之间的攻击策略,其他作品关注网络鲁棒性和网络结构指标之间的关系(NSIs)。艾耶et al。<一个href="#B4">4一个>]研究了网络的鲁棒性作为节点聚类系数的函数(或节点传递性)。研究模型与可调网络聚类系数表明,较高的网络聚类系数更强劲,与节点的最重要的影响程度和节点介数攻击(<一个href="#B4">4一个>]。阮和董里<一个href="#B34">34一个>]研究Facebook社交网络和发现那些网络与更高的模块化<我>问我>删除节点的鲁棒性较低。模块性指标<我>问我>介绍了纽曼和Girvan [<一个href="#B35">35一个>措施如何向社区网络优惠,(即。,一个community or module in a network is a well-connected group of nodes that have sparser connections with nodes outside the group). In [<一个href="#B29">29日一个>],作者实证分析的模块化无标度模型和现实世界的社交网络影响他们的鲁棒性和不同的节点的相对有效性攻击策略。上述研究分析网络鲁棒性和单一NSI之间的关系。
另一方面,机器学习(ML)是一种技术,在过去的十年中,一个巨大的突破打最先进的结果在许多预测应用程序(<一个href="#B36">36一个>]。它最初解决技术问题在计算机视觉和自然语言处理<一个href="#B37">37一个>- - - - - -<一个href="#B39">39一个>),然后扩展到许多其他领域,如医疗、金融、制造、能源、和环境。毫升模型的关键特征是能够智能地学习输入和输出之间的非线性关系没有明确知道他们。
在这工作,因为这样的网络鲁棒性和NSIs之间的复杂关系,我们采用机器学习的方法来学习这样的复杂性。我们的主要贡献是毫升的应用模型来预测真实社交网络的鲁棒性和可接受的错误。我们开发毫升模型来预测网络鲁棒性两个主要攻击策略下,IB和RD攻击策略,独立。我们还实现了三种流行的ML模型、变量线性回归,multiple-variable线性回归和随机森林模型。毫升等我们的结果表明,一个数据驱动的方法可以是一个有效的方法来研究网络的复杂性。
我们的工作包括三个步骤:(1)收集一个真实网络数据集和计算NSIs;(2)运行蒙特卡罗节点攻击模拟估计网络的鲁棒性;(3)构建和评估模型,从他们的NSIs预测网络的鲁棒性。本文的组织结构如下:在部分<一个href="#sec2">2一个>,我们描述数据集的48个现实世界的社交网络。节<一个href="#sec3">3一个>,我们描述了网络的健壮性蒙特卡罗模拟方法和三个毫升模型预测网络的鲁棒性,即。、简单、多元线性回归(分别单反和高钙)和随机森林(RF)模型。部分<一个href="#sec4">4一个>介绍了主要结果,最后,我们将讨论和结论部分<一个href="#sec5">5一个>。
2。现实世界的社交网络数据集和鲁棒性估计
真实社交网络下载来自两个来源:斯坦福大型网络数据集收集(<一个href="https://snap.stanford.edu/data/" target="_blank">https://snap.stanford.edu/data/一个>社交网络)和网络存储库(<一个href="https://networkrepository.com/soc.php" target="_blank">https://networkrepository.com/soc.php一个>)。我们选择48社交网络的节点数(N)等五个数量级。最小的网络是“抽动user-user网络流在葡萄牙的玩家”<我>N我>= 1914,最大的网络“电子邮件网络从欧盟研究机构”<我>N我>= 265216。然而,网络最大的边数(<我>E我>)是“BlogCatalog社会博客”<我>E我>= 4186390。在这项研究中使用的社交网络是未加权(即。,we do not take into account edge weights) and undirected (we do not consider edge directionality).
表<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab1/" target="_blank">1一个>总结了48个真实的社交网络和他们的NSIs。除了N和<我>E我>我们也计算以下NSIs:(我)网络密度<<我>k我>>平均节点度,即。,the average number of edges per node.(2)安装scaled-free指数(<我>α我>):我们假设所有社交网络度分布遵循幂律<我>P我>(<我>k我>)∼<我>k我>−<我>α我>在哪里<我>k我>节点度。力量指数的值<我>α我>使用普通最小平方方法安装。从这个配件,我们也提取拟合的方差<我>α我>,用<我>α我>2。(3)Assortativity (<我>一个我>):assortativity系数程度之间的皮尔逊相关系数对链接节点(<一个href="#B40">40一个>),这在−1和1之间变化。正值表示优先连接节点之间的相似度,而负值表明节点连接不同程度有更多的变化。(iv)模块化(<我>问我>):模块化指标<我>问我>计算如何划分子网的网络模块(或社区): 在哪里<我>E我>边的数量,<我>一个我>ij我>邻接矩阵的元素是一个行吗<我>我我>和列<我>j我>,<我>k我>我我>的程度<我>我我>,<我>k我>j我>的程度<我>j我>,<我>c我>我我>模块(或社区)吗<我>我我>,<我>c我>j我>的<我>j我>,走过去<我>我我>和<我>j我>双节点,<我>δ我>(<我>x我>,<我>y我>1)如果<我>x我>=<我>y我>否则和0 (<一个href="#B13">13一个>]。(v)全局聚类系数(<我>C我>):全球聚类系数(<我>C我>)是基于节点的三胞胎。三联体是三个节点所连接的两个(开放三联体)或3(封闭的三联体)无向边。全局聚类系数是封闭的三胞胎的数量(或3<我>x我>三角形,因为三角形由三个重叠的三胞胎,每个集中在三个节点)里的一个三胞胎的总数(开启和关闭)。公式如下: 在哪里<我>λ我>关闭是三胞胎和关闭的数量吗<我>λ我>总在网络三胞胎的总数。全球网络聚类系数代表了总体概率相邻节点相互连接,从而使更紧密相连的模块(<一个href="#B41">41一个>]。(vi)平均亲密(Cl)是所有网络节点的平均的亲密,亲密(或亲密中心)的计算节点的倒数之间的最短路径长度之和的节点和其他节点图(<一个href="#B42">42一个>,<一个href="#B43">43一个>]: 在哪里<我>N我>节点和数量吗<我>d我>(<我>我我>,<我>j我>)是节点之间的最短路径的长度<我>我我>和<我>j我>。
2.1。网络鲁棒性蒙特卡罗模拟
对于每个网络,我们使用蒙特卡罗模拟运行两个节点删除过程。节点连续中移除后最初的中间性的排名(IB)和重新计算程度的排名(RD)。的关系,例如,节点与平等的中间性或程度得分,我们随机删除其中的一个。每个节点删除后,我们计算网络健壮性测量和相对大小最大的连接组件LCC,一起积累比例的节点删除<我>问我>。最后,我们获得两条曲线LCC (<我>问我>)对应于两个节点删除流程,IB和RD。整个模拟重复10次,最后曲线LCC (<我>问我>)的平均结果。
此外,我们计算一个值定义为网络的鲁棒性(<我>R我>),由Bellingeri et al。<一个href="#B44">44一个>),而规范化的LCC曲线下面的面积在清除过程中,<我>R我>= 。R我>因此可以两个理论之间的极端, (绝对脆弱的网络) (绝对强大的网络)。我们表示RRD和肋骨网络鲁棒性对RD和IB节点攻击策略,分别。
总之,我们收集48个真实的社交网络,然后我们计算9 NSIs为每个网络作为输入。同时,我们运行蒙特卡罗模拟和获取两个指标所代表的鲁棒性,RRD和肋骨。越高,网络更健壮。这两个指标是每个网络的输出和将使用毫升预测模型。
3所示。机器学习方法
本节介绍了单反的细节,高钙,射频模型。
3.1。简单线性回归模型(SLR)
线性回归是最简单的预测模型。网络之间的单反相机模型的鲁棒性<我>R我>和一个NSI<我>x我>由线性方程表示: 在哪里<我>一个我>0是拦截和<我>一个我>1斜率是。在(<一个href="#EEq4">4一个>),一个普通的最小二乘法(OLS)申请估计系数通过最小化一个适当的损失函数(<一个href="#B45">45一个>,<一个href="#B46">46一个>]。一旦OLS的过程,也称拟合过程,被执行时,我们可以使用(1)预测的鲁棒性<我>R我>一个新的网络对于一个给定的指标<我>x我>。此外,我们得出一个统计数据<我>t我>以及从零假设H0的OLS过程:<我>一个我>1= 0。拒绝H0意味着之间存在显著的线性关系<我>R我>和NSI<我>x我>。
我们运行单反模型适合所有NSIs列在表中<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab1/" target="_blank">1一个>不包括<我>E我>因为它可以表达的另外两个NSIs:<我>E我>=<我>N我><<我>k我>> / 2。
3.2。多元线性回归模型
看不到多元线性回归(MLR)是一个扩展的单反多维变量<我>x我>= (<我>x我>1,<我>x我>2、…<我>x我>n我>),<我>x我>1,<我>x我>2、…<我>x我>n我>NSIs。网络鲁棒性之间的线性方程<我>R我>和NSIs如下: 在哪里<我>一个我>我我>系数从OLS方法获得。
3.3。随机森林模型
随机森林(RF)属于毫升模型的集合类,表明它总量预测的合奏毫升基础模型,在这里,决策树回归(DTR)模型。我们简要描述DTR在接下来的部分。
DTR开始与树的根包含所有样品(48网络在我们的例子中)。然后它分裂成两个不同的节点通过选择样本的某个变量的值高于或低于某一阈值。图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig2/" target="_blank">2(一个)一个>代表一个数据集的基本决策树图。根节点包含48网络分裂成两个其他节点通过考虑是否变量(NSI)在我们的例子中无标度指数<我>α我>高于或低于2.5。
(一)
(b)
DTR选择变量,其分裂值是基于信息理论,具体考虑熵的概念。熵是一个度量不确定性的一个节点。DTR分裂节点通过最大化信息增益,即加权区别两个结果节点的总熵和熵的初始节点。DTR先后分裂,直到达到停止条件,例如,如果当前节点的大小小于20。最后的节点也被称为一个叶子节点。在图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig2/" target="_blank">2(一个)一个>第一次分裂后,根,左子节点成为一个叶节点,而右子节点继续分裂成两个叶节点。
一旦最终DTR,它可以用来预测新样本的值如下。新样品将分为一个叶子,和其预测价值将所有样本的平均值,分为相同的叶子。
最后,RF模型创建多个决策树的随机数据,通常几百,平均结果从所有树木输出一个新的结果常常会导致强烈的预测(<一个href="#B47">47一个>,<一个href="#B48">48一个>]。
决策树可以适合非线性的数据集,因为它可以把同样的NSI很多次了。然而,决策树是容易过度拟合,即。,我t我s too sensitive to the training data while failing to predict new coming (testing) data. In order to address this problem, a random forest (RF) model is obtained by creating multiple randomly drawn decision trees from data, usually several hundred. The final regression prediction will be the average prediction of all the decision trees [<一个href="#B47">47一个>- - - - - -<一个href="#B49">49一个>)(在这项工作中,我们实现一个射频300 dtr)。使用射频,”功能重要性”等级的测量可以派生NSI [<一个href="#B50">50一个>]。
3.4。数据准备、验证和绩效评估
所有NSIs可以从网络计算的数据,因此,我们的数据集不包含缺失值。我们也排除<我>E我>正如上面提到的,因为冗余。其他8 NSIs规范化,避免巨大差异指标的范围: 在哪里NSI的价值吗<我>我我>观察(网络)<我>j我>和和的均值和标准差NSI吗<我>我我>,分别。
在第一步中,我们使用整个数据集构建毫升模型和模型之间的比较结果和两个目标变量。然而,由于许多毫升模型过度拟合问题,新数据模型的性能并不总是一致的,在训练的步骤中,我们需要在第二步验证模型。我们选择的分析验证<一个href="#B51">51一个>]。通过这种方式,我们训练的每个模型48次以上:每一次整个数据集包括一个观察是用来训练模型,然后,该模型用于预测的目标价值剩余的(合作)观察和重复每48个同意的观察。综合评价结果的平均所有48回归。
指出,单反的模型中,我们只考虑回归系数来分析鲁棒性指标对每个NSI的依赖。然而,对于高钙和射频模型,我们使用四种常见分析鲁棒性指标的预测评价指标回归问题,均方根误差(RMSE)和确定系数(也叫解释方差比,<我>R我>2)为分析指标和频率分布和残余的qq阴谋错误图形指标。
RMSE是根号的平方的总和观察和预测数据点之间的区别。RMSE有相同的单位作为目标特性和模型通常被认为是错误。较低的权值代表优越的预测结果。RMSE提供的公式 在哪里<我>n我>是观察,的数量<我>R我>j我>表示经验(模拟)网络健壮性和<我>R我>预测,<我>j我>鲁棒性的预测价值的观察<我>j我>。
R我>2用于表示一般回归模型的预测性能。<我>R我>2是1 -剩余方差的比值和原始方差。的公式<我>R我>2是由 在哪里<我>n我>是观察,的数量<我>R我>j我>是模拟的鲁棒性,<我>R我>预测,<我>j我>表示观测的预测值<我>j我>,是平均的仿真的鲁棒性。<我>R我>20之间的不同(模型没有预测能力)和1(模型正确预测所有的值)。
剩余误差, ,只是一个错误之间的经验(模拟)的预测价值网络的鲁棒性和鲁棒性。的分布直方图预计将接近原点。此外,最重要的一个线性回归模型的假设是残余错误是独立的,因此,这些错误将正态分布。
分析了网络使用的“制图工具”图书馆<我>Python我>。所有数据准备、模型建立和评价是用写的<我>Python我>代码。数值模拟是一个PC的硬件以19 - 10850英特尔处理器和32 GB RAM。
4所示。结果
4.1。网络鲁棒性的函数NSIs和单反t检验
每个网络的鲁棒性仿真肋骨和RRD表表示<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab2/" target="_blank">2一个>。总的来说,我们发现RRD略小于肋对大多数网络(43 48网络),平均分别为0.148和0.173。它表明RD策略更有功效比IB攻击现实世界的社交网络。最大的和稀疏网络,Email-EuAll (<我>N我>= 265216和<<我>k我>≥1.58),具有最小的鲁棒性与一个平等的肋骨和RRD 0.001。相比之下,gemsec_deezer_HR网络<我>N我>= 54575和<<我>k我>≥9.12,具有最强的鲁棒性的肋骨和RRD 0.375和0.338,分别。
在图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig3/" target="_blank">3一个>,我们把RRD和肋骨8独立NSIs的函数,我们发现RRD和肋骨的行为同样在所有情况下。单反揭示一些重要的之间的关系<我>R我>和NSIs(图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig3/" target="_blank">3一个>和表<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab3/" target="_blank">3一个>)。例如,在图3(一个),我们可以看到,RRD和肋骨稍微减少网络的大小<我>N我>。这个线性鲁棒性RRD和肋骨之间的依赖<我>N我>测试通过使用单反相机模型,我们发现它是统计学意义,置信水平为95% (值< 0.05,表<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab3/" target="_blank">3一个>)。
(一)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
有趣的是,RRD和肋骨不统计线性依赖于网络密度<<我>k我>>,发现以前在<一个href="#B4">4一个>,<一个href="#B52">52一个>)(图3 (b)和表<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab3/" target="_blank">3一个>)。这种对比观察表明,网络健壮性还取决于其他NSIs和网络密度无法预测以往整个网络的鲁棒性。
除了<我>N我>唯一的其他NSI显示显著的线性关系是模块化<我>问我>(图3 (f))在RRD的情况下。
然而,在图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig3/" target="_blank">3一个>,我们还观察到一些非线性依赖关系。例如,在图3 (e),我们表明,网络健壮性随assortativity系数时<我>一个我>> 0。然而,它也减少了更快的时候<我>一个我>接近0时,增加<我>一个我>< 0。
同样,在图3中(g),我们发现RRD和肋骨之间的关系和全球聚类系数C遵循一个倒u形的模式。我们运行了一个两行统计检验(<一个href="#B53">53一个>),发现两行(或折线)回归明显比一个单行的测试。断点被发现<我>C我>= 0.115。RRD和肋骨线性增加C(显著性水平为95%)断点和线性减少与C(显著性水平为95%)。一个可能的解释是,如果网络稀疏,更多的三胞胎帮助增加网络的连通性,从而提高其鲁棒性。然而,超过一定值(当<我>C我>= 0.115),更多的三胞胎可能表示中心或中心节点的存在,这很可能是故意的目标节点删除RD和IB等策略,从而降低网络的鲁棒性。
4.2。机器学习的预测网络的鲁棒性
前一节的结果表明,社交网络的鲁棒性取决于多个NSIs高度复杂,多维、非线性的方式。提高模型预测,在这一节中,我们使用两个多个变量毫升模型,高钙和射频,预测网络的鲁棒性。
多元线性回归的结果高如表所示<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab4/" target="_blank">4一个>。我们发现两个<我>R我>IB和<我>R我>理查德·道金斯有一个积极的整体线性回归系数对吗<我>α我>,<我>问我>,<我>Cl我>,<<我>k我>>和负总体线性回归系数有关<我>α我>2,<我>一个我>,<我>C我>,<我>N我>。此外,高钙的结果表明<我>α我>,<我>α我>2,<<我>k我>>是最显著的系数。一个积极的线性回归系数的平均节点度<<我>k我>>时表明,网络更健壮<我>k我>是较高的,而所有其他NSIs是固定的。这个结果同意先前的结果证明密集的网络可能抗攻击(<一个href="#B4">4一个>,<一个href="#B52">52一个>]。然而,高钙之间的不同的结果和单反建议<之间有很强的相关性<我>k我>>和其他NSIs。此外,高钙模型预测<我>R我>IB比<我>R我>理查德·道金斯,<我>R我>2系数58.04%到51.76%。然而,RMSE小<我>R我>理查德·道金斯值为0.0657,相比0.0709肋(这是因为肋骨的标准差比高<我>R我>理查德·道金斯,如表所示<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab2/" target="_blank">2一个>(底下一行))。
由于非线性的发现在前面的小节中,我们预计使用射频模型回归结果将得到改善。表<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab5/" target="_blank">5一个>代表了射频模型的回归结果。我们发现<我>R我>2增加到92.24%和91.88%<我>R我>IB和<我>R我>理查德·道金斯分别回归。有趣的是,RF模型预测<我>R我>理查德·道金斯大致一样<我>R我>理查德·道金斯,而高预测<我>R我>IB比<我>R我>理查德·道金斯,这表明<我>R我>理查德·道金斯可能比肋与NSIs遵循一个更强的非线性关系。此外,RMSE改进的<我>R我>IB和<我>R我>理查德·道金斯,其值分别为0.0272和0.0241。有趣的是,该功能重要性排名在表<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab5/" target="_blank">5一个>与一个射频模型表明,assortativity,全球亲密<我>C我>和节点数量<我>N我>NSIs是最重要。这个结果同意探索观察如图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig3/" target="_blank">3一个>正如上面所讨论的。
在图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig4/" target="_blank">4一个>,我们比较网络的鲁棒性<我>R我>IB和<我>R我>理查德·道金斯预测的值由高钙和射频使用散点图。散点图表明,射频数据明显比高,实际预测的数据点在哪里靠近对角线<我>y我>=<我>x我>。同时,高钙回归,我们仍然发现非线性实际值和预测值之间的依赖关系。事实上,高钙模型无法捕捉的固有非线性依赖实际数据。我们也分析了残余的上述回归错误使用频率直方图和QQ-plot,发现他们遵循正态分布相对较好(数字<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig5/" target="_blank">5一个>- - - - - -<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig8/" target="_blank">8一个>)。
(一)
(b)
(一)
(b)
(一)
(b)
(一)
(b)
(一)
(b)
最后,我们运行分析回归模型高钙和射频为了避免过度拟合。结果总结表<一个href="//www.newsama.com/journals/complexity/2022/3616163/tab6/" target="_blank">6一个>散点图如图<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig9/" target="_blank">9一个>。我们发现准确的预测结果是低于上述“样本”训练较低的均方根高钙和射频模型。我们得到一个RMSE的0.0812和0.0760<我>R我>IB和<我>R我>理查德·道金斯分别预测使用高钙和RMSE的0.0733和0.0636<我>R我>IB和<我>R我>理查德·道金斯分别预测使用射频。尽管回归结果不太有效,因为我们预测单一独立于其余的样品样品用于培训(构建毫升模型),剩余错误仍然适合一个正态分布直方图和QQ-plots(数据所示<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig10/" target="_blank">10一个>- - - - - -<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig13/" target="_blank">13一个>)。
(一)
(b)
(一)
(b)
(一)
(b)
(一)
(b)
(一)
(b)
5。讨论和结论
在这项工作中,我们分析了48个现实世界的社交网络的鲁棒性和节点数量等五个数量级,从1914年到265216年。使用蒙特卡罗模拟,我们有两种常用的节点攻击策略运行,IB和RD策略,其计算时间是在我们的硬件功能。我们发现相应的仿真时间,<我>t我>IB和<我>t我>理查德·道金斯,尺度线性的产品网络的节点数和边数,也就是说,<我>N我>×<我>E我>。我们还发现,这两个攻击策略IB和RD独特的鲁棒性度量相似的疗效评估<我>R我>与RD略优于IB(平均水平<我>R我>理查德·道金斯是略小于平均<我>R我>IB)。它表明,在这项研究中,使用的社交网络采访策略是最有效的策略来拆除(分解)网络,无论是计算成本和分解效率。
了解社交网络的结构决定了其鲁棒性,我们调查指标之间的关系<我>R我>和一组网络结构指标(NSIs)的文学。简单线性回归(SLR)之间<我>R我>NSIs显示低善良的拟合,整体是不能够产生显著的预测模型。单反的低善将表明,网络健壮性取决于NSIs以非线性的方式。
提高拟合,我们开发了两个机器学习模型预测两个鲁棒性指标<我>R我>理查德·道金斯和<我>R我>理查德·道金斯从8 NSIs的结合,多元线性回归(高),(RF)和随机森林模型。后者的一个选择,因为它可以处理非线性数据,是建立在基础模型的集合,决策树分类器。我们发现明显的随机森林模型可以预测网络的鲁棒性优于多元线性回归模型。在混凝土中,射频模式预测网络鲁棒性的RMSE 0.0272和0.0241<我>R我>IB和<我>R我>理查德·道金斯,分别。这个结果是令人鼓舞的预测的真实社交网络的鲁棒性,虽然错误(约16%<我>R我>IB,RMSE比平均为0.0272<我>R我>IB是0.173,<我>R我>理查德·道金斯,RMSE比平均为0.0241<我>R我>理查德·道金斯0.148)。与此同时,分析评价时,RMSE增加到0.0733和0.0636<我>R我>IB和<我>R我>理查德·道金斯分别大约三分之一的平均值。
最后,高表明,最重要的因素来预测肋指数<我>α我>和平均节点度<<我>k我>>,<我>R我>IB和<我>R我>理查德·道金斯。特别是,一个更高的价值<我>α我>与高<我>R我>IB和<我>R我>理查德·道金斯。高指数的绝对值<我>α我>表示一个网络中心节点较少(高度连接节点)(<一个href="#B35">35一个>]。因此,RD和IB攻击策略无法找到大型枢纽节点的删除可能瓦解网络更快,导致更高的值<我>R我>理查德·道金斯和<我>R我>IB。此外,高表明<<我>k我>>是正相关的降低<我>R我>IB和<我>R我>IB。这最后的结果同意以前的结果,证明网络边缘密度较高的可能更耐攻击(<一个href="#B4">4一个>,<一个href="#B52">52一个>]。另一方面,它证实了单反,专注于单一NSI可能无法预测真实社交网络的鲁棒性。
我们的工作表明,ML模型可以用来预测网络的鲁棒性与可接受的结果。因此,缓解需要运行一个完整的蒙特卡罗模拟网络上只有近似健壮性是必要的。与此同时,更多的网络数据集将改善毫升模型的准确性。这个工作也有助于理解现实世界的社交网络的鲁棒性之间的关系和其结构指标。最后,我们证明,使用数据驱动的方法预测的结果非线性和复杂的动态过程,如网络的鲁棒性,是一个适当的方法<一个href="#B54">54一个>- - - - - -<一个href="#B60">60一个>]。
附录
直方图和QQ-plot残余误差的回归给出了数据<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig5/" target="_blank">5一个>- - - - - -<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig8/" target="_blank">8一个>和数字<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig10/" target="_blank">10一个>- - - - - -<一个href="//www.newsama.com/journals/complexity/2022/3616163/fig13/" target="_blank">13一个>。
缩写
| 理查德·道金斯: | 重新计算度节点攻击策略 |
| IB: | 最初的中间性节点攻击策略 |
| RB: | 重新计算介数节点攻击策略 |
| t我>IB: | IB仿真总时间攻击策略 |
| t我>理查德·道金斯: | 路仿真总时间攻击策略 |
| t我>RB: | RB仿真总时间攻击策略 |
| 单反: | 简单线性回归模型 |
| 高: | 多元线性回归模型 |
| 射频: | 随机森林模型 |
| DTR: | 决策树回归模型 |
| NSI: | 网络结构指标 |
| RMSE: | 均方误差 |
| R我>2: | 确定系数(也叫解释方差比率) |
| 一个我>0: | 拦截系数单反 |
| 一个我>1: | 斜率系数单反 |
| OLS: | 普通最小二乘法 |
| : | 误差之间的经验(模拟)的预测价值网络的鲁棒性和鲁棒性 |
| α我>: | 安装无标度指数 |
| k我>: | 节点度 |
| <<我>k我>>: | 平均节点度 |
| 一个我>: | 学位assortativity |
| Cl我>: | 全球亲密 |
| C我>: | 全局聚类系数 |
| 低成本航空: | 最大连接组件 |
| N我>: | 的节点数量 |
| E我>: | 边数 |
| 问我>: | 模块化的指标 |
| α我>2: | 拟合方差<我>α我> |
| 问我>: | 积累比例的节点删除 |
| R我>: | 网络鲁棒性 |
| R我>理查德·道金斯: | 网络鲁棒性对RD节点攻击策略 |
| R我>IB: | 网络鲁棒性对IB节点攻击策略。 |
数据可用性
所有48个真实的社交网络从斯坦福下载大型网络数据集收集(<一个href="https://snap.stanford.edu/data/" target="_blank">https://snap.stanford.edu/data/一个>社交网络)和网络存储库(<一个href="https://networkrepository.com/soc.php" target="_blank">https://networkrepository.com/soc.php一个>)。
的利益冲突
作者宣称没有利益冲突。
作者的贡献
QN构思分析。NKKN,水马力,TTL和TMN执行模拟。QN NKKN, FS,风湿性关节炎,MB, DC写道。
确认
这项工作是由越南科学技术部(大多数)Vietnam-Italy科技合作项目2021 - 2023年期间,越南胡志明市国立大学(VNU-HCM),越南胡志明市,在格兰特B2017-42-01号。这项研究是由意大利外交部的资助以及国际合作。这个项目获得资金从欧洲研究委员会(ERC)在欧盟的地平线2020研究和创新计划(批准的协议。(816313))。作者非常感谢范·朗大学越南,为本研究提供的预算。
引用
-
美国莱曼和y y。安,“复杂的传播现象在社会系统中,“<我>计算社会科学)我>施普林格国际出版,柏林,德国,2018年。
视图: 谷歌学术搜索一个> -
m . Bellingeri d Cassi, s . Vincenzi”效率的攻击策略在复杂的模型和实际的网络,”<我>自然史答:统计力学及其应用我>卷,414年,第180 - 174页,2014年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
m . Bellingeri d . Bevacqua f . Scotognella et al .,“真正的社交网络链路和节点删除:复习一下,”<我>前沿生理学我>,8卷,p。228年,2020年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
s .艾耶t Killingback、b .他和z . Wang攻击鲁棒性和复杂网络的中心,“<我>《公共科学图书馆•综合》我>,8卷,不。4篇文章ID e59613 2013。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
k .阮阮,”股票互关联网络的弹性随机故障和蓄意攻击,”<我>研究计算智能我>卷,760年,第561 - 553页,2018年。
视图: 谷歌学术搜索一个> -
我们美国,x的太阳,d·冯·m·Zanin和s . Havlin network-dismantling方法的比较分析,“<我>科学报告我>,8卷,不。1,文章ID 13513, 2018。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
r . Pastor-Satorras c可以见到效果,p . Van Mieghem和a . Vespignani”在复杂网络流行过程,”<我>现代物理学的评论我>,卷87,不。3、925 - 979年,2015页。
视图: 谷歌学术搜索一个> -
c . Stegehuis r·范德Hofstad和j·s·h·范·Leeuwaarden“流行病蔓延在复杂网络社区结构”,<我>科学报告我>》第六卷,没有。1,文章ID 29748, 2016。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
l . c . Li王,金黄色的太阳,c .夏”识别基于分类的有影响力的传播者的邻居在现实世界的复杂网络,”<我>应用数学和计算我>,C, 320卷,第523 - 512页,2018年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
李c . j . Wang, c .夏”改善中心指标来描述节点在复杂网络传播能力,”<我>应用数学和计算我>卷,334年,第400 - 388页,2018年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
l·k·盖洛f . Liljeros p . Argyrakis a .由美国Havlin,“改善免疫策略,”<我>物理评论E我>,卷75,不。6日1 - 4,2007页。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
j . Hadidjojo和s . a .畅”等于图分区在估计感染流行网络是一种有效的缓解措施,”<我>《公共科学图书馆•综合》我>》第六卷,没有。7篇文章ID e22124 2011。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
m·a·阿马拉尔m . Md奥利维拉和m . a . Javarone”与自主检疫spidemiological模型策略由进化vame动力,”<我>混乱,孤波和分形我>文章ID 110616卷,143年,2021年。
视图: 谷歌学术搜索一个> -
h . Amini和a . Minca“流行病传播和qquilibrium geterogeneous网络社会距离,”<我>直流发电机的游戏:我>,12卷,不。1,第287 - 258页,2022。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
m . Bellingeri d . Bevacqua f . Scotognella r . Alfieri和d . Cassi”链接删除策略的比较分析在实际复杂加权网络,”<我>科学报告我>,10卷,第3915 - 3911页,2020 b。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
m . Bellingeri m . Turchetto d Bevacqua et al .,“建模社会距离的后果在流行病传播复杂的社会网络:从链接删除分析冠- 2预防,”<我>前沿生理学我>ID 681343条,卷。9日,2021年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
D . Achlioptas r . m . D’索萨,j·斯宾塞,“爆炸性的渗透在随机网络,”<我>科学我>,卷323,不。5920年,第1455 - 1453页,2009年。
视图: 谷歌学术搜索一个> -
g .董j .风扇l . m . Shekhtman et al .,“网络社区结构的弹性行为,好像在外部领域,“<我>美国国家科学院院刊》上我>,卷115,不。27日,6911 - 6915年,2018页。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
y太阳,c . Liu C.-X。张,Z.-K。张“流行加权复杂网络上的传播,”<我>物理信我>,卷378,不。7 - 8,635 - 640年,2014页。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
a . Majdandzic b . Podobnik s . v . Buldyrev d . y . Kenett s Havlin h·尤金·斯坦利,“自发的复苏动力网络”<我>自然物理我>,10卷,不。1、品种马非常,2014页。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
施s .我们x, x的太阳,和m . Zanin“现实世界的网络社区检测提高网络拆除”,<我>IEEE访问我>,8卷,第111965 - 111954页,2020年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
r·阿尔伯特·h·宋,A.-L。巴斯”直径的全球网络。”<我>自然我>卷,401年,第131 - 130页,1999年。
视图: 谷歌学术搜索一个> -
r·科恩,k . Erez d·本·亚和美国Havlin,“弹性网络的随机故障。”<我>物理评论快报我>,卷85,不。21日,第4628 - 4626页,2000年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
问:阮,t . v . Vu h . d . Dinh et al .,“模块化影响无标度模型的鲁棒性和现实世界的社交网络在中间性和mba节点攻击,”<我>:Netw Sci我>》第六卷,没有。1,p。82、2021 b。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
太阳x, v . Gollnick,我们美国“全球机场网络鲁棒性分析指标:一个全面的研究,“<我>中国航空杂志我>,30卷,不。2、500 - 512年,2017页。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
问:阮:k . k .阮d . Cassi和m . Bellingeri”新的中间性中心节点攻击策略对于现实世界的复杂加权网络,”<我>复杂性我>文章ID 1677445卷,2021年,页1卷,2021。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
美国沃瑟曼和k·浮士德,<我>社会网络分析:方法和应用我>英国剑桥,剑桥大学出版社,1994年。
-
问:阮和t . Trang勒”,Facebook的页面的结构和鲁棒性的网络,”<我>学报》2019年第十届会议网络建模和分析(Marami 2019)我>2019年11月,法国第戎。
视图: 谷歌学术搜索一个> -
Shalev-Shwartz和s . Ben-David<我>了解机器学习:从理论算法我>英国剑桥,剑桥大学出版社,2014年。
-
k . x张,他任美国,j .太阳,“深残余学习图像识别,”<我>学报2016年IEEE计算机视觉与模式识别会议(CVPR)我>NV,页770 - 778年,美国,2016年6月。
视图: 谷歌学术搜索一个> -
k . x张,他任美国,j .太阳,“身份映射深陷残余网络”<我>计算机视觉——2016年大会我>,j·m·n·s . Leibe和m·威林。,vol. 9908B, pp. 630–645, Springer International Publishing, Cham, 2016.
视图: 谷歌学术搜索一个> -
m·e·j·纽曼,“流行病传播网络,”<我>物理评论E -统计物理、等离子体、液体,和相关的跨学科主题我>,卷66,不。1,文章ID 016128, 2002。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
d . s .卡拉威·m·e·j·纽曼,s . h .“d·j·瓦,“网络鲁棒性和脆弱性:渗流在随机图,“<我>物理评论快报我>,卷85,不。25日,第5471 - 5468页,2000年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
美国沃瑟曼和k·浮士德,<我>社会网络分析:一个手册我>、鼠尾草、钙、美国,2000年。
-
m . Bellingeri d . Bevacqua f . Scotognella, d . Cassi”链接权重的异质性可能减少现实世界复杂加权网络的鲁棒性,”<我>科学报告我>,9卷,不。1,文章ID 10692, 2019。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
答:美国不“古典线性回归”,<我>计量经济学理论我>美国纽约,约翰威利& Sons, 1964。
视图: 谷歌学术搜索一个> -
f . Hayashi<我>计量经济学我>美国新泽西,普林斯顿大学出版社,2000年。
-
l . Breiman j·弗里德曼,c . j .石头和r . a . Olshen<我>分类和回归树我>,CRC出版社,佛罗里达州博卡拉顿,1984。
-
j·汉、m . Kamber和j .贝聿铭<我>数据挖掘:概念和技术我>摩根kaufmann伯灵顿,马萨诸塞州,美国,2006年。
-
r .膝、j . m . Poggi和c . Tuleau-Malot“变量选择使用随机森林,”<我>模式识别的字母我>没有,卷。31日。14日,第2236 - 2225页,2010年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
g .詹姆斯d·威滕、t . Hastie和r . Tibshirani<我>介绍统计学习:应用R我>美国纽约,施普林格,2013年。
-
r·h·琼斯和b A Molitoris”统计方法确定两条线的断点,”<我>分析生物化学我>,卷141,不。1,第290 - 287页,1984年8月15日。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
r·阿尔伯特·h·宋,A.-L。Barabási”,错误的攻击宽容和复杂的网络,“<我>自然我>,卷406,不。6794年,第382 - 378页,2000年。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
p .河中沙洲,b . j . Kim c n . Yoon和s . k .汉“复杂网络攻击的弱点,”<我>物理评论一个我>,卷65,不。5、文章ID 056109, 2002。
视图: 出版商的网站一个> | 谷歌学术搜索一个> -
y太阳,c . Liu C.-X。张,Z.-K。张“流行加权复杂网络上的传播,”<我>物理信我>,卷378,不。7 - 8,635 - 640年,2014页。
视图: 谷歌学术搜索一个>