具有可分离异构连接的高效网络结构

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Efficient Network Structures with Separable Heterogeneous Connection
  Costs》
---
作者：
Babak Heydari, Mohsen Mosleh, Kia Dalili
---
最新提交年份：
2015
---
英文摘要：
  We introduce a heterogeneous connection model for network formation to capture the effect of cost heterogeneity on the structure of efficient networks. In the proposed model, connection costs are assumed to be separable, which means the total connection cost for each agent is uniquely proportional to its degree. For these sets of networks, we provide the analytical solution for the efficient network and discuss stability impli- cations. We show that the efficient network exhibits a core-periphery structure, and for a given density, we find a lower bound for clustering coefficient of the efficient network.
---
中文摘要：
我们引入了一个网络形成的异质连接模型，以捕捉成本异质性对高效网络结构的影响。在所提出的模型中，连接成本被假定为可分离的，这意味着每个代理的总连接成本与其程度成唯一比例。对于这些网络集，我们提供了有效网络的解析解，并讨论了稳定性的含义。我们证明了有效网络具有核心-外围结构，并且对于给定的密度，我们找到了有效网络的聚类系数的下界。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--
一级分类：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).
社会和团体（人类或其他）的结构、动态和集体行为。社会网络和其他复杂网络的定量分析。具有广泛社会影响的基础设施和系统（如能源网、运输网络）的物理和工程。
--

---
PDF下载：
--> Efficient_Network_Structures_with_Separable_Heterogeneous_Connection_Costs.pdf (331.05 KB)

2022-5-8 03:55:57 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：网络结构 Applications Quantitative Architecture proportional

有效的网络结构，具有可分离的共生连接成本*Babak Heydaria+，Mohsen Mosleha，Kia Dallibaschool of Systems and Enterprises，Stevens Institute of Technology，Hoboken，NJ 07030bFacebook Inc，纽约，NY 10003，2018Abstracts我们介绍了一种网络形成的异质连接模型，以验证成本异质性对高效网络结构的影响。在所提出的模型中，连接成本被假定为可分离的，这意味着每个代理的总连接成本与其程度成唯一比例。对于这些网络集，我们提供了有效网络作为连接成本和效益函数的解析解。我们表明，有效网络呈现出核心-外围结构。此外，对于给定的链路密度，我们找到了有效网络聚类系数的下界，并将其与Erd"os-R"enyi随机网络的聚类系数进行了比较。关键词：复杂网络、连接模型、高效网络、基于距离的性能、核心-外围、成对稳定性JEL分类号：D85*这是以下文章的预印本：B.Heydari、M.Mosleh和K.Dalli，《具有可分离异构连接成本的高效网络结构》，经济通讯杂志，第134卷，2015年9月第8285页。，最终版本已在doi:10.1016/j.econlet上发布。2015.06.014.+地址：美国新泽西州霍博肯城堡点露台1号，邮编：07030，电子邮件：babak。heydari@stevens.edu，网址：http://web.stevens.edu/cens/1引言网络形成模型正越来越多地应用于各种经济环境和其他多智能体系统中。这些模型通常研究效率、网络社会福利和稳定性的结构条件，这是个体形成、保持或切断联系的激励措施（Jackson et al。

(2008)).我们基于Jackson和Wolinsky（1996）提出的连接模型构建了我们的模型，在该模型中，代理可以从直接和间接连接中受益，但只能为其直接连接付费。间接连接的好处通常会随着距离的增加而减少。Jackson和Wolinsky（1996）证明，对于同质情况，有效网络只能采用三种形式中的一种：完整图、星形图或空图，具体取决于连接成本和效益。已经提出了几种模型来将异质性引入连接模型（例如，见Galeotti et al.（2006）；杰克逊和罗杰斯（2005）；波斯茨（2010）；Vandenbossche和Demuynck（2013年）；重点主要放在稳定的条件上，很少提到效率。为具有异构成本的高效网络寻找通用分析解决方案可能很难，例如Carayol和Roux（2009）。在这里，我们专注于为一个特定的成本异质性模型找到有效的网络，我们称之为可分离连接成本模型，其中每个连接的节点成本份额是异质的，但固定且独立于它们连接的对象。这是由网络驱动的，在网络中，异构代理都被赋予了一些资源（时间、能量、带宽等），并且为每个节点建立和维护连接所需的总资源可以近似地与其程度成正比。我们进一步假设同质效益随距离衰减。在这些假设下，我们为有效连接性结构提供了精确的分析解决方案，showJackson和Wolinsky（1996）基于成对稳定性或双边链路形成的概念开发了他们的模型，其中链路是在两个代理的“相互同意”下形成的。

还有另一种来自巴拉和戈亚尔（1997）的文学作品；Goyal（1993）研究了单边和不合作的链接形成，其中代理单方面决定与另一个代理建立链接。这种网络最多有一个连接部件，呈现核心-外围结构，直径不超过两个。我们进一步给出了集群系数的下界，并讨论了集群网络的成对稳定性。2模型对于一组有限的代理N={1，…，b}，设b:{1，…，N- 1} → R表示一个代理从与其他代理的（直接或间接）连接中获得的收益，作为它们之间距离的函数。继Jackson和Wolinsky（1996）之后，图g中每个节点的（基于距离的）效用函数ui（g）和图的总效用U（g）如下所示：ui（g）=Xj6=i:j∈Nn-1i（g）b（dij（g））-Xj6=i:j∈Ni（g）cijU（g）=nXi=1ui（g）（1），其中Ni（g）是i链接到的节点集，Nki（g）是路径连接到i的节点集，距离不大于k。dij（g）是i和j之间的距离，cijis是节点i连接到j所支付的成本，b是节点i从与网络中另一个节点的连接中获得的收益。对于任意整数k，我们假设b（k）>b（k+1）>0≥ 1.让完整图GN表示大小为2的N的所有子集的集合。网络效率，如果U（~g）≥ U（g）代表所有g gN，这表示g=arg maxgPni=1ui（g）。假设前面介绍的可分离成本模型，方程式1中i和j之间的连接成本可以写成cij=ci，cji=cj。然后，我们引入一个连接成本向量C，在不丧失一般性的情况下重命名节点，使C<C<。。。

<cn。k2#核心n#m外围1图1：具有可分离异构连接模型的高效网络结构。连通分量具有广义星形结构。n是网络中的节点数，m是连接组件中的节点数，k是核心（完整子图）中的节点数。节点根据其成本（即成本）进行排序≤ C≤ · · · ≤ 中国。2.1有效结构在可分离连接代价下，在引理1中，我们确定了连接组件的有效结构。然后在建议1中，我们确定了有效网络的一般结构。引理1如果具有可分离代价模型的有效网络是连通的，那么它具有具有以下特征的“广义星形”结构：（a）所有节点都连接到节点1（连接代价最小的节点）。（b） 节点i和j（i，j 6=1）是连接的b（1）- b（2）>5（ci+cj）。证据设N表示所连接网络中的节点。如果存在nodesM={v，…，vm}（M）的子集 N） 如果没有连接到节点1，我们表明网络不有效。因为N是连接的，所以存在一组链接，L={L，…，lm}，其中li与vi相邻。假设li连接vito wi（定义为wi6=1）。现在，如果我们删除alllis并将所有vis连接到节点1，我们已经通过mc降低了网络的总连接成本-mPk=1cvk<0。现在，为了解决好处，请注意我们没有改变链接的数量；因此，直接收益保持不变。此外，新网络的直径为2。对于连通网络N（m6）的任意子集M={v，··，vm}≡ N），我们可以证明在N中有链接L={L，····，lm}，使得vis与li相邻。因此，每一个不是1的距离都被限制在2，使得总收益大于原始网络的收益。

这导致总利用率的提高，表明原来的网络效率不高。此外，在确定有效网络中的最大距离不大于2后，每个节点i和j（i，j 6=1）都连接到iif b（1）- b（2）>5（ci+cj）。命题1确定了高效网络的结构，并表明高效网络是一系列解决方案。连接模型中的命题1，对于一组有限的代理，N={1，…，N}，如果cij=ciforall i，j∈ N，ci在哪里∈ C={C，C，…，cn}并假设，C<C<···<cn，有效网络的结构如下：设m为1和n之间的最大整数，即2b（1）+2（m- 2） b（2）>（cm+c）。如果我>m，那么我是孤立的。如果我≤ m、 那么在i和1之间只有一个链接；i和j之间也有一个联系（1<i，j≤ m） i ff b（1）- b（2）>5（ci+cj）。证据首先，我们证明在高效网络中最多有一个连接组件。接下来，我们找到每个节点位于连通组件中的条件，根据引理1，该组件具有广义星形结构。假设有效网络有多个（例如两个）连接组件，其中（mi，`i）分别是连接组件中节点和链路的数量。根据引理1，每个连通分量都有一个广义的星型结构。每种成分的总收益为B=2`B（1）+（m- 1) - 2`）b（2）和b=2`b（1）+（m（m）-1)-分别为2`）b（2）。假设h和hare节点分别在分量1和分量2中具有最小代价，且不损失通用性ch<ch。

如果我们断开所有连接到h的链接，将它们直接连接到h，总成本将降低（ch）-ch）每个链接。这也导致了总收益B=（`+`）B（1）+（（m+m）（m+m）-1)-2（`+`）b（2），严格大于（b+b）。为了确定高效网络中哪些节点属于连接组件GC，我们定义了节点i、Ai、2b（1）+2（k- 2） b（2）- C- 其中k是连接组件GC中的节点数。我们证明了我在GCi工作≥ 首先，Ai>0是我进入GC的充分条件。这是因为，根据引理1，将i连接到节点1会增加总效用，精确地说是Ai，因为GCI的直径最多为2。如果Ai<0，那么我将被隔离，所以Ai≥ 0也是必要条件。这是因为我不能只连接到1，因为Ai<0，所以我连接的唯一方法是有多个链接。从引理1来看，要使i与j6=1有联系，我们必须使ci+cj<2b（1）- 2b（2）。但是：ci+cj>c+ci>2b（1）+2（k- 2） b（2）>2b（1）- 2b（2），我们使用cj>cand Ai<0这一事实，因此我也不能有多个连接，因此我将被隔离。注意，Ai>0也意味着所有j<i的Aj>0，因为cj<ci，所以所有低成本节点也将位于GC中，因此Ai<0的最小i提供了高效网络中连接组件的大小。图1.2.2具有异构可分离成本模型的高效网络的典型结构如图1.2.2具有可分离成本模型的网络特征所示。2.1核心-外围结构我们表明，高效网络具有核心-外围结构，这是一种在各种社会和经济网络中被广泛观察到的结构（例如，参见Zhang et al.（2014）；Rombach等人（2014年）。

我们采用了Bramoull’e（2007）的正式定义，该定义指出，当代理可以被划分为两个集合时，图g具有核心-外围结构，即核心C和外围P，这样所有的伙伴关系都在核心内形成，而外围内没有形成伙伴关系。对于一个有效网络，让k是2到n之间的最大整数，这样b（1）- b（2）>5（ck-1+ck）。有效网络可以划分为一个集合C={1，…，k}，它形成一个完整的子图，而集合P={k+1，…，n}，它只能与完整的子图连接。国际单项体育联合会（1）- b（2）>（ck-1+ck）然后是k和k- 1是连接的，每个节点i，j（i，j）之间也有一个链接≤ k和ci，cj≤ ck），形成一个完整的子图。同样，我们可以证明，对于每一个∈ P，它连接到节点j，cj≤ CKJ和J6∈ P.2.2.2聚类系数具有同质成本模型的类效率网络，其聚类系数为一（完整图）或零（星形结构或空图），具有异质成本的效率网络的聚类系数覆盖范围很广。为了找到下限，我们在给定链路密度和各种连接成本值的情况下，找到所有有效网络的最小全局聚类系数。为此，我们构建了一个网络，该网络不会破坏上一节中提供的效率条件，同时生成给定密度下的最小可能三角形数，如下所示：从一个空图开始，节点k=1，我们只按顺序建立从节点k到每个节点i>k的链接。我们对k=1重复这个过程，p+1，直到链接总数达到`。p是最大的整数，`=Ppk=1（n- k） +J，其中J是p+1轮不完全迭代中的剩余链接数（J<n-p+1）。

在第k次迭代中，连接的三联体的总数增加了N-K+2（k）-1） （n）-（k）+J+2Jp。该等式中的第一项是因为节点k将作为一个具有（n）的本地中心-k） 提供新链接的用户N-K新三胞胎。第二项是第k轮中形成的新三角形产生的额外三元组，因为有（k-1） （n）-k） 三角形在k中形成，加上3个三元组，其中一个已经在以前的迭代中计算过了。剩余的两个术语遵循与剩余链路（J）类似的逻辑。类似地，在第k次迭代中形成的三角形总数增加（k）- 1） （n）- k） +pJ。因此，对于给定数量的链路（`），我们有：Cmineff（g，`）=3×三角形数节点的连接三元组数=3×{Ppk=1（k- 1） （n）- k） +pJ}Ppk=1{N-K+ 2（k）- 1） （n）- k） }+J+ 2Jp（2）与具有相同链路密度的Erd"os-R"enyi（ER）随机网络相比，一些代数表明，当节点数大于10且链路密度大于4（2n）时，高效异构网络的聚类系数超过ER网络的聚类系数-5） n（n）-1). 对于足够大的网络，条件简化为链路密度大于n。3结论异构但可分离的连接成本涵盖了实际网络的重要类别。我们证明了这种网络的有效结构可以精确求解，并且直径不大于2；我们还讨论了此类网络的及物性和核心-外围性质。尽管收益仍然被认为是同质的，但只要保持可分性假设，即：。

成本和直接收益项一起出现在所有分析中，成本项可以通过将其嵌入节点的固定成本中来捕获直接收益的异质性。我们主要关注具有可分离连接成本模型的网络的效率概念。进一步的研究可以调查所提出模型的稳定性，并找到稳定和高效结构重合的条件。此外，也存在可分离成本假设不成立的情况，例如，当链路成本是两个节点的相似程度的函数时。这些情况通常很难处理，可以使用近似方法，如Jackson和Rogers（2005）中讨论的岛屿模型。确认这项工作得到了DARPA合同NNA11AB35C的支持。作者非常感谢彼得·卢德洛（Stevens）和佩德拉姆·海达里（UCSD）的深刻评论。参考文献巴拉，V.和戈亚尔，S.（1997）。通信网络中的自组织。技术报告，计量经济研究所研究论文。Bramoull\'e，Y.（2007）。反协调和社会互动。《游戏与经济行为》，58（1）：30-49。Carayol，N.和Roux，P.（2009）。知识流动与网络地理：小世界形成的星形模型。经济行为与组织杂志，71（2）：414-427。Galeotti，A.，Goyal，S.，和Kamphorst，J.（2006）。由异质玩家组成的网络。《游戏与经济行为》，54（2）：353-372。Goyal，S.（1993年）。可持续的通讯网络。鹿特丹伊拉斯谟大学计量经济研究所。杰克逊，M.O.等人（2008年）。社会和经济网络，第3卷。普林斯顿大学普林斯顿大学。杰克逊，M.O.和罗杰斯，B.W.（2005）。小世界的经济学。欧洲经济协会杂志，3（2-3）：617-627。杰克逊，M.O.和沃林斯基，A.（1996）。