用有限差分法重构复杂网络的拓扑性质

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Reconstructing topological properties of complex networks using the
  fitness model》
---
作者：
Giulio Cimini, Tiziano Squartini, Nicol\\`o Musmeci, Michelangelo
  Puliga, Andrea Gabrielli, Diego Garlaschelli, Stefano Battiston, Guido
  Caldarelli
---
最新提交年份：
2014
---
英文摘要：
  A major problem in the study of complex socioeconomic systems is represented by privacy issues$-$that can put severe limitations on the amount of accessible information, forcing to build models on the basis of incomplete knowledge. In this paper we investigate a novel method to reconstruct global topological properties of a complex network starting from limited information. This method uses the knowledge of an intrinsic property of the nodes (indicated as fitness), and the number of connections of only a limited subset of nodes, in order to generate an ensemble of exponential random graphs that are representative of the real systems and that can be used to estimate its topological properties. Here we focus in particular on reconstructing the most basic properties that are commonly used to describe a network: density of links, assortativity, clustering. We test the method on both benchmark synthetic networks and real economic and financial systems, finding a remarkable robustness with respect to the number of nodes used for calibration. The method thus represents a valuable tool for gaining insights on privacy-protected systems.
---
中文摘要：
复杂社会经济系统研究中的一个主要问题是隐私问题$-$，它会严重限制可访问信息的数量，迫使人们在不完整知识的基础上建立模型。本文研究了一种从有限信息出发重构复杂网络全局拓扑性质的新方法。该方法利用节点的内在属性（表示为适应度）的知识，以及仅有限的节点子集的连接数，以生成代表真实系统的指数随机图集合，并可用于估计其拓扑属性。在这里，我们特别关注于重建通常用于描述网络的最基本属性：链接密度、分类、聚类。我们在基准合成网络和实际经济及金融系统上测试了该方法，发现该方法对用于校准的节点数量具有显著的鲁棒性。因此，该方法是了解隐私保护系统的一个有价值的工具。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Social and Information Networks        社会和信息网络
分类描述：Covers the design, analysis, and modeling of social and information networks, including their applications for on-line information access, communication, and interaction, and their roles as datasets in the exploration of questions in these and other domains, including connections to the social and biological sciences. Analysis and modeling of such networks includes topics in ACM Subject classes F.2, G.2, G.3, H.2, and I.2; applications in computing include topics in H.3, H.4, and H.5; and applications at the interface of computing and other disciplines include topics in J.1--J.7. Papers on computer communication systems and network protocols (e.g. TCP/IP) are generally a closer fit to the Networking and Internet Architecture (cs.NI) category.
涵盖社会和信息网络的设计、分析和建模，包括它们在联机信息访问、通信和交互方面的应用，以及它们作为数据集在这些领域和其他领域的问题探索中的作用，包括与社会和生物科学的联系。这类网络的分析和建模包括ACM学科类F.2、G.2、G.3、H.2和I.2的主题；计算应用包括H.3、H.4和H.5中的主题；计算和其他学科接口的应用程序包括J.1-J.7中的主题。关于计算机通信系统和网络协议（例如TCP/IP）的论文通常更适合网络和因特网体系结构（CS.NI）类别。
--
一级分类：Physics        物理学
二级分类：Physics and Society        物理学与社会
分类描述：Structure, dynamics and collective behavior of societies and groups (human or otherwise). Quantitative analysis of social networks and other complex networks. Physics and engineering of infrastructure and systems of broad societal impact (e.g., energy grids, transportation networks).
社会和团体（人类或其他）的结构、动态和集体行为。社会网络和其他复杂网络的定量分析。具有广泛社会影响的基础设施和系统（如能源网、运输网络）的物理和工程。
--
一级分类：Quantitative Finance        数量金融学
二级分类：General Finance        一般财务
分类描述：Development of general quantitative methodologies with applications in finance
通用定量方法的发展及其在金融中的应用
--

---
PDF下载：
--> Reconstructing_topological_properties_of_complex_networks_using_the_fitness_model.pdf (203.02 KB)

2022-5-7 00:32:37 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：有限差分法 有限差分 复杂网络 差分法 Applications

使用适应性模型重建复杂网络的拓扑性质朱利奥·西米尼、蒂齐亚诺·斯夸蒂尼、尼科尔·穆斯梅奇、米开朗基罗·普利加、安德里亚·加布里埃利1,3、迭戈·加拉舍利、斯特凡诺·巴蒂斯顿、吉多·卡尔达雷利复杂系统研究所（ISC-CNR）UoS“萨皮恩扎”罗马大学（意大利）国王学院、伦敦（英国）IMT高等研究所，卢卡（意大利）莱顿大学洛伦兹理论物理研究所（荷兰）苏黎世大学银行与金融系（瑞士）摘要复杂社会经济系统研究中的一个主要问题是隐私问题，它会严重限制可访问信息的数量，强迫在不完全知识的基础上建立模型。本文研究了一种从有限信息出发重构复杂网络全局拓扑性质的新方法。该方法利用节点的固有属性（表示为fifight）和节点的有限子集的连接数的知识，以生成代表真实系统的指数随机图集合，并可用于估计其拓扑属性。在这里，我们特别关注于重建通常用于描述BEA网络的最基本属性：链接密度、分类性、聚类性。我们在基准网络和实际经济及金融系统上测试了该方法，发现该方法对用于校准的节点数量具有显著的鲁棒性。

因此，该方法是了解隐私保护系统的一个有价值的工具。1简介当可用信息有限时，网络统计特性的重建是复杂网络领域中一个尚未解决的突出问题[1,2]。FirstExample是金融网络的例子，其系统性风险估计基于机构之间的相互依赖[3,4]——然而，由于存在机密性问题，监管机构能够收集的关于相互风险敞口的信息非常有限[5]。其他例子包括soc-ialnetworks，对于这些网络，由于隐私保护或无法对整个系统进行采样，信息可能不可用。网络重建通常通过最大熵（ME）算法[6,7,8]进行，该算法根据最大均匀性原则获得链路权重；然而，这些算法的强大局限性在于假设网络是完全连通的（因此，它们被称为“密集重建方法”），而实际网络的连通性分布在很大程度上是异质的。更明确的方法，如“解析重建”算法[2]允许获得具有任意异质性的网络，但仍然无法为这种异质性设定合适的值。最近，为了克服这些问题，人们提出了一种新的自举（BS）方法[9,10]。BS方法使用系统上的有限信息，根据指数随机图（ERG）模型生成网络集合[11]——然而，定义它的拉格朗日乘数被替换为属性，即与网络拓扑相关的已知固有节点特定属性[12]。然后在ERG诱导系综内对网络拓扑性质进行估计。

该方法建立在之前的结果[13]的基础上，该结果表明，在世界贸易网（见下文）的特定情况下，如果将非拓扑属性（国内生产总值）的知识与链接总数的知识相结合，可以非常准确地推断网络的拓扑属性。这个过程可以在一个最大似然框架中重新表述[14]。当网络的度序列（即，每个节点的连接数）仅为部分已知时，BS方法使用这些初步obs来提供有效的重构过程。虽然过去的工作[2,6,7,8,9]主要是利用网络上可用的有限信息来估计特定的高阶属性，如系统风险，但在本文中，我们使用BS方法来重建通常用于描述网络的基本属性：链路密度、假设性、聚类（见第3节）。通过关注这些之前未经测试的属性，我们能够扩大用BS方法正确估计的数量篮子。

为了验证我们的方法，我们研究了其准确性如何取决于可用信息的节点子集的大小；我们的案例研究包括通过能力模型[12]生成的合成网络，以及网络系统的真实实例：1）世界贸易网（WTW），[15]，即节点为国家的网络，链接代表它们之间的贸易量，2）e-mid（e-mid）银行间货币市场的银行间贷款网络[16]。2方法我们从简要描述ERG模型和能力模型开始，BS方法就是基于这两个模型建立的。ERG模型是最常见的网络生成框架[11,17,18]之一，它包含一个集合Ohm 除了网络性质{hCai]集合的集合平均外，最大随机的网络Ohm}—将d解释为某些特定值{c*a} 。概率分布rOhm 然后可以通过一组控制参数s{θa}来定义，即与约束{C]相关的拉格朗日乘数集*a} 。ERG模型的一个特殊但广泛使用的例子被称为配置模型（CM）[11]，它是通过指定平均度序列{k]获得的*i} Ni=网络的1。在这种情况下，每个节点i由与其次数ki相关的拉格朗日乘数θi识别。

副定义xi≡ E-θii、 任意两个节点i和j连接的整体概率读取[11]：pij=xixj1+xixj（1），以便xiquantifie节点i与其他节点s创建链接的能力（由其度ki引起）[19]。另一方面，适应性模型[12]假设网络拓扑由与网络的每个节点相关的内在非拓扑属性（称为适应性）确定，并在过去成功地用于对几个经验经济网络进行建模[20,16,13]。BS方法[9]结合了这两种网络生成模型，工作如下。我们从给定网络G（由N个节点组成）的拓扑结构的不完全信息开始：我们假设知道度序列{k*i} 我∈如果只有节点的子集I（I |=n<n）和内在的非拓扑性质{yi}I∈Vfor所有将成为我们公司的节点（见下文）。利用这些信息，我们希望找到在网络G上计算的拓扑属性X的值X（G）的最可能估计值，与上述约束条件兼容。该方法基于两个重要假设：1。网络Gis被解释为来自ERG诱导的集合Ohm. 然后，我们预计数量X（G）在hXi范围内变化很大Ohm± σOhm十、 hXi在哪里Ohm和σOhmX分别代表集合中估计的X e属性的范围和标准偏差Ohm.2.假设非拓扑性{yi}通过一个通用（未知）参数z:xi与deg ree诱导的指数分布乘法器{xi}成正比≡√zyii、 因此，等式（1）变为：pij=zyiyj1+zyiyj。（2） 由于这两个假设，我们可以将计算X（G）的问题转化为选择最佳ERG系综的问题Ohm 与G上的约束相容，在我们只知道部分信息的情况下，G最适合提取真实网络的Gfrom。

例如，国家国内生产总值（GDP）在对WTW建模时表现良好，公式（1）准确地描述了WTW拓扑结构-θi∝ 日志（GDPi）[13]。在任何情况下，第二个假设（或任何其他关系yi=f（xi））可以在已知度的节点子集I上进行适当测试。3拓扑特性如引言中所述，在测试BS方法时，我们将重点关注拓扑特性（在前面的讨论中，每个都显示了X的作用），它们通常被认为是描述网络的最重要因素。为了确定这些特性，我们使用了邻接矩阵的形式，如果节点i和j是连接的，则ij=1，否则aij=0。

我们考虑：o链路密度（或连接度）：D:=Pi<jaijN（N）- 1） /2=2LN（N- 1） （4）网络中实际链路数与最大兼容链路数与节点数N的比值平均平均最近邻度数：knn:=Piknn，式中knn，i:=Pj（6=i）aijkki=Pj（6=i）Pk（6=i，j）aijajkPj（6=i）aij（5），即每个节点的邻居度数的算术平均值，在所有节点上取平均值平均聚集系数：c:=picin，其中ci:=Pj（6=i）Pk（6=i，j）aijaikajkPj（6=i）Pk（6=i，j）aijaik（6），即每个节点邻域中观察到的链路数与最大可能的链路数之间的比率，所有节点上的平均数d[21]平均富俱乐部系数：φ=XkP（k）φ（k），其中φ（k）=ψ- D1- Dandψ（k）=2E>kN>k（N>k）- 1） （7）P（k）表示阶数等于k和φ（k）的节点的分数时，e>k=Pi:ki>kPj:kj>kaijedges之间的比率实际上连接了N>k=PiΘhPjaij- 度数大于k且最大可能数N>k（N>k）的节点- 1） /2这样的边（或者，换言之，子图的链接密度仅由度大于k的节点组成）[22]。4数据集为了验证我们的BS方法，我们使用了两个实际经济系统的实例。第一个是世界贸易网[15]，即一个网络，其节点代表世界各国，并将它们之间的贸易量联系起来：因此，wijis是i国对j国的出口总额。第二个是所谓的e-mid银行间货币市场的银行间贷款网[16]。

在这种情况下，节点代表银行，银行i和j之间的连接线代表来自银行的贷款金额。对于WTW，我们使用2000年的贸易量数据。0001 0,01 0,11 10 100 100000,01 0,11 10X图1：WTW（左面板）和e-mid（右面板）的节点能力{yi vs指数拉格朗日乘数{xi的散点图。这些数据集特别适合我们的研究，因为节点{yi}可以自然地与WTW的国家GDP和银行的总风险敞口（即贷款总额）相一致。因此，在这两种情况下，每个节点的能力与其总强度相一致：yi≡ si=Pjwij。然后将这些网络的二元无向版本（我们想重新构造）构建为aij=Θ[wij+wji]。5测试BS方法在进行结果之前，我们注意到BS方法存在两种不同类型的错误。第一个原因是用于校准ERG模型的可用信息有限：因为我们只知道节点子集I的阶数，所以我们只能通过HEQ获得ERG集合最佳z的估计值。(3). 第二个错误来自这样的假设，即节点{yi}与度诱导的拉格朗日乘子{xi}成正比。图1显示了两个经验网络的{yi}和{xi}之间的关系。事实上，存在与线性的偏差，这将与适应性模型的完美再利用相对应。注意，观察到WTW具有更好的相关性：因此，我们可以预期BS方法在这种情况下工作得更好。因此，BS方法在重建两个案例研究网络的拓扑属性方面的有效性的定量评估分两步进行，如下所示。在合成网络上进行测试。

为了评估由于学位序列可用信息有限而产生的错误，我们首先对通过能力模型生成的合成网络进行基准测试。这意味着我们通过求解等式（3）来评估ERG系综的“真实”z，其中所有节点都包含在I中（即，假设知道整个度序列），然后绘制一个网络GfromOhm（z） 通过数字生成它。(2). Gis现在是通过BS方法重建的网络（即，使用部分信息），对于e-mid，我们考虑每月汇总的贷款快照（正如其他工作[16]中所做的那样），因为在较短的时间范围内链接的高波动性。下面，我们将报告1999年2月的快照结果。我们还对其他月度快照进行了相同的分析，并发现了类似的结果。X的值是在Gitself（即X（G））和整个系综上计算的Ohm（z） 作为hXiOhm（z） 。推理包括以下操作步骤：o选择一个值n<n（已知度的节点数）；o建立一个随机选取n个节点中M=100个子集{Iα}Mα=1的集对于每个子集Iα，使用Iα中的度序列从等式（3）中计算zα，并使用它构建插入码Ohm（zα）；o使用等式（2）中的连接概率来计算系综上属性X的值Ohm（zα）as Xα=hXiOhm（zα）；o计算子集{Iα}:rX上性质X的相对均方根误差（rRMSE）≡VuUtmxα=1XαX- 1.（8） 在rRMSE表达式中，Xdenotes属性X的参考值，可以是X（G）（在G上测量的X的值），也可以是hXiOhm（z） （整个集合的X值）Ohm（z） ）。