网络上的中心度分布

当A是对称矩阵时，kAkis等于A.2.2随机网络特征值的最大绝对值。我们通过使用矩阵A指定的链接概率独立生成链接来定义随机网络。代理i和j之间的每条边都是使用概率Aij形成的。这些链接是独立生成的，因此网络邻接矩阵的条目是独立的随机变量。给定一个n×n的链路概率矩阵'A，我们生成一个包含n个代理的网络实例，并将A作为该网络的邻接矩阵。随机块体模型是我们的主要例子。考虑将一组n个节点划分为mgroup。在随机块模型中，两个代理之间的边的概率仅取决于它们的组，因此当代理k在组i中，代理l在组J中时，Akl=PIJ。由于网络中的嗜同性数量取决于确定组的大小和组之间链接的概率的参数，因此我们可以通过改变这些参数以不同的方式改变嗜同性。请注意，A和A都是对称矩阵。因此，这些矩阵具有特征值（以重数计算），并且这些特征值是实的。设λ，λ。。。，λnbe'A的特征值，排序为'λ'≥ |λ| ≥ ... ≥ |λn |。类似地，设λ，λ。。。，λnbe A的特征值，排序为|λ|≥ |λ| ≥ ... ≥ |λn |。我们假设所有链路形成概率均为正，因此'A是一个正矩阵，满足Perron-Frobenius定理的结论。尤其是该矩阵，附录B.2放宽了该假设。具有最大特征值λ的唯一特征向量，且该特征向量具有非负实项。最后，我们考虑由人口规模n定义1索引的随机网络序列。

对于正整数序列中的每个n，随机网络序列是由这些概率生成的网络的n×n概率矩阵'A（n）和邻接矩阵A（n）。3中心性度量我们考虑两种常见的中心性度量，我们称之为Katz-Bonacich中心性和特征向量中心性。这些中心性概念由线性方程定义，这种线性使得在随机网络上分析这些中心性度量变得容易处理。在随后的章节中，我们将讨论随机网络中代理的中心度分布如何依赖于网络形成模型中的参数。3.1 Katz Bonacich Centrality我们首先讨论网络中代理的Katz Bonacich Centrality。这个度量可以用线性代数和图论来解释。固定一个正常数φ<kAk-1、回忆kAkis等于单位向量x的normkaxk的最大值，因此该条件意味着kφAxkis相对tokxk不太大。定义2。agent i相对于常数φ的Katz-Bonacich中心性由ci（A，φ）给出，其中c（A，φ）是toc（A，φ）=φAc（A，φ）+1的解，其中1是包含所有条目1的列向量。该方程由c（A，φ）=（I）唯一求解- φA）-1=∞Xk=0φkAk1。因为（Ak）ij是从代理i到代理j的行走次数，所以此系列具有组合解释。代理人i的卡茨·博纳希奇中心性是代理人i开始的步行次数，每次步行根据其长度用折扣系数φ进行折扣。因此，φ值越大，对应的计算长度越长的连接越多，而φ值越小，对应的计算距离越短。越来越多的文献将Katz Bonacich的中心地位与gameson网络的战略和结果联系起来。

假设代理人选择一个决定结果的福利水平，当福利水平为e isui（e）=ei时，代理人的效用-ei+φnXj=1aijeij。这种函数形式意味着效用在效用水平上是二次的，并且代理人的效用和邻居的效用之间存在互补性。然后在纳什均衡下，策略e*满足感*= φAe*+ 1、卡茨-博纳希奇中心论给出了均衡策略：e*= c（A，φ）。因此，在这些博弈中，效用等于Katz-Bonacich中心性，效用是Katz-Bonacich中心性的二次函数。如果我们假设效率决定结果，而同侪效应通过效率成本表现出来，那么代理人的结果就是她的卡茨波纳奇中心性。3.2特征向量中心性特征向量中心性是一个密切相关的概念。agent i的特征向量中心性是邻接矩阵的特征向量与最大绝对值特征值的协调。更正式的定义：定义3。具有邻接矩阵的网络中代理i的特征向量中心由vi（A）给出，其中v（A）是具有最大特征值的A的特征向量，即满足kv（A）k=1的v（A）=λv（A）的解。备注1。如果第一个特征值的多重性大于1，则特征向量中心可能无法唯一定义。在这些情况下，我们的结果将不取决于惯例的选择。备注2。

因为我们必须选择归一化，不同代理的特征向量中心度之间的比率比每个代理的中心度水平更有意义。agent的特征向量中心性与邻居的特征向量中心性之和成正比：vi（A）=λ-1Xj∈Nivj（A）。换句话说，特征向量中心度是衡量一个代理有多少个邻居的一种度量，中心邻居越多，计算的结果就越多。特征向量中心性可以看作是卡茨-博纳希奇中心性的一个极限。更准确地说，当φ接近kAk时，Katz-Bonacich中心度c（A，φ）在极限内接近特征向量中心度v（A）所跨越的线-1从下面开始。为了澄清后面部分结果背后的直觉，我们描述了一个将特征向量中心性与对等效应联系起来的程式化动态模型。假设每个个体在时段0中以禀赋wi（0）开始。在每个时期t+1，每个个体的禀赋都会变为cwi（t）+Pj∈对于任何c>0的情况，Niwi（t）。这意味着代理的资源是其前一时期的资源与邻居前一时期的资源之和的线性组合。在矩阵表示法中，w（t+1）=（cI+A）w（t）。我们在第2节中假设“A”为正，这意味着Perron-Frobenius定理表明v（\'A）是唯一的。但即使“A”为正，实现矩阵A也有正概率为非正，因此我们不能排除与特征值λ相对应的多个特征向量的可能性。然后作为t→ ∞, 禀赋w（t）与v（A）成正比。禀赋不断更新的极限是特征向量中心性。该模型与Echenique和Fryer（2007）第V.A节中的力学过程非常相似。4随机网络的中心性本节描述了使用随机块模型生成的网络中代理的中心性。

在高概率情况下，根据链路概率，中心度向量将接近确定性向量。在第5节和第6节中，我们计算特定随机网络模型的确定性向量。将这些计算与本节中的理论相结合，将阐明链路概率的影响，以及网络结构的特征，如同质性的数量，对代理中心度分布的影响。在陈述这些定理之前，我们将陈述并讨论两个技术条件。定义4。我们说，如果存在δ>0使得λ（n），则随机网络序列具有非消失谱- |λ（n）|>所有n的Δλ（n）。这表示第二个特征值与远离一个特征值的第一个特征值之间的比率的绝对值。Golub和Jackson（2012）将第二个特征值称为spectralhomophily，并表明该数量衡量了网络中的同态数量。作为连接的一个简单示例，考虑一个随机块模型，其中所有组的大小相同，组内给定链接的概率等于psa，组间链接的概率为pd。在这种情况下，第二个特征值和第一个特征值之间的比率等于通常的科尔曼嗜同性指数（见Goluband-Jackson（2012）第II.C节）。因此，当没有极端同态时，谱隙是不消失的。直观地说，如果对于大的n，网络不能被分成两个子组，Golub和Jackson（2012）认为第一特征值等于1的矩阵，则条件是满足的。几乎断开连接。如果所有节点在A（n）中的度数都相同，我们可以使该声明更正式。假设第二个特征值和第一个特征值之间的比率收敛为1。Hart fiel和Meyer（1998）的解耦定理表明存在子集M（n） {1, . . .

，n}个代理∈M（n），j/∈M（n）’A（n）ijPj’A（n）ij→ 0as n→ ∞. 换句话说，M（n）与其补体之间链接的总权重增长速度比单个代理的增长速度慢。非消失的光谱间隙确保了'A和A的特征向量中心以高概率唯一定义。在极端同质的情况下，可以有多个“A”或“A”，其最大特征值对应于不同的分离群或群集合。对于非消失的谱隙，我们很有可能避免这种情况。为了说明第二个条件，我们定义 = maxiPnj=1'A（n）ij表示节点的最大预期次数。定义5。我们说随机网络序列具有足够大的特征值sifλ（n）p 日志（n）→ ∞作为n→ ∞.该技术条件的直观内容是：（1）试剂的预期度增长速度远远快于对数n，（2）试剂的预期度变化不大。为了更好地理解这种直觉，我们使用以下事实（Lev（2014））：λ（n）≥ （迷你，j’A（n）ij）XiXj’A（n）ij。（1） 如果每个代理i的链接概率在邻居j之间变化不大，则条件（1）意味着n mini，j'A（n）ij的增长速度比log n快。如果条件（2）保持不变，则PIPj'A（n）ij相对于n、 将这两个非正式的界限结合起来，可以得出更一般的结论，即使某些链接的概率为零或极小，序列也可以具有较大的特征值。在这些情况下，方程（1）不会给出有用的特征值下界。λ（n）> 日志（n）。我们将在示例2中看到，如果一个代理的期望度比其他代理高得多，那么随机网络序列如何无法具有大而小的特征值。这种情况排除了非常稀疏的网络。如果大多数或所有代理都只有很少的链接，那么中心性将对是否形成特定链接非常敏感。

因此，不可能以高概率表征中心性。在实践中，这种情况可能会在网络中失效，因为网络中的链接是为亲密关系等强连接保留的。在第5.1节和第5.2节中，我们研究了随机块网络序列，其中每个组在总人口中的比例随着n的增长保持不变，所有链接概率Pijalso保持不变。很容易看出这些序列有足够大的特征值。在这些条件下，我们可以刻画特征向量中心性：定理1。假设A（n）是一个具有非消失谱且具有足够大特征值的随机网络序列。允许 > 0.对于n个非常大的，概率至少为1-  矩阵A（n）具有唯一的最大特征值λ（n），且特征向量中心度v（A（n））满足ykv（A（n））- v（(R)A（n））k<.该定理指出，在大型网络中，所有代理的特征向量中心度都接近其期望值，这些期望值可以从链接的概率计算出来。值得注意的是，代理的特征向量中心性与其期望值之间的距离是一致有界的（跨代理）。结果符合大数定律，该定理给出了一些关于边界为何成立的直觉。根据大数定律，对于n个足够大的组，大多数组之间的链接数量大约是预期的。这表明它们的特征向量中心度也将接近它们的预期值，尽管实际屋顶需要更实质性的随机图论。关键工具是Chung和Radcliffe（2011）的结果，该结果限制了矩阵a（n）的范数-以及A（n）和A（n）的特征值之间的差异。

我们证明，当特征值足够大时，其结果表明，对于n大，矩阵normkA（n）-\'A（n）kis较小，差异|λ（n）- λ（n）|比λ（n）小。给定这些界限，我们可以证明A（n）和A（n）（视为线性算子onRn）将特征向量中心度v（A（n））映射到附近的向量。特别地，v（A（n））在A（n）下的图像具有接近λ（n）的范数。因为我们在下面限制了“A”的光谱间隙，所以当单位向量接近第一特征向量v（\'A（n））时，“A（n）”下的单位向量的图像只有接近第一特征值的范数。接下来，我们陈述了Katz-Bonacich中心性的类似结果。定理2。假设A（n）是一个具有足够大特征值的随机网络序列。假设φ（n）是一系列常数，使得lim supnφ（n）λ（n）<1。允许 > 0.对于n个非常大的，概率至少为1- Katz-bonacichcentrality满足ykc（A（n），φ（n））的向量- c（(R)A（n），φ（n））k<√n、 该陈述本质上与定理1相同，特征向量中心性现在被Katz-Bonacich中心性所取代。因此，这个结果表明，大型网络中所有网络的Katz-Bonacich中心度都接近其预期值，并且这些预期值也仅与“A”相关。Katz-Bonacich中心度具有正常的(√n） 虽然特征向量中心度定义为范数1，因此还有一个额外的因子√定理2中的n。证明在矩阵范数kA（n）上使用相同的界-(R)A（n）k。然后，想法是将相关的卡茨-博纳西奇中心性表示为矩阵幂的和，并将这些矩阵幂之间的差异限定为kA（n）-\'A（n）k.示例和模拟：最简单的非平凡示例是Erd"os-R'enyi图，对于所有i、j和n，A（n）ij=p。该序列具有非消失的光谱间隙和较大的特征值。

对于任何 > 0，定理1表示kV（A（n））-√n1k<对于n大的高概率，定理2暗示了合适的φ（n），即kc（A（n），φ（n））-1.- φ（n）np1k<√n的概率很高。我们模拟了100个这样的随机网络，其中p=且φ（n）=2λ（n）。当n=500时，kv（A（n））的平均值-v（(R)A（n））kis 0.0773和kc（A（n），φ（n））的平均值-c（(R)A（n），φ（n））kis 1.757。当n=1000时，平均值分别为0.0548和1.744。扩展：在附录B中，我们提供了定理1和定理2的几个扩展。第B.1小节通过将伯努利随机变量Aijj替换为均匀随机变量，允许非整数边权重。第B.2小节允许聚类，如果两个代理i和j都连接到一个公共邻居k，则这两个代理i和j连接的倾向增加，在此设置中使用边权重。我们给出了在三角形和二元体上放置附加权重的网络的两个定理的版本。由于许多现实世界的社会和经济网络表现出比独立形成链接所暗示的更多的集群，这种修改有助于适应许多应用程序。反例：我们现在给出两个反例，说明这两个定理需要一个不消失的光谱间隙和足够大的特征值。在FirstExample中，A（n）的特征值表现良好，但特征向量中心度不连续地依赖于已实现的网络。示例1。假设A（n）ij=如果i，j≤nor i，j>nand'A（n）ij=n-3否则。网络分为两组，同一组中的两个代理以概率连接，而不同组中的两个代理以很小的概率连接。简单计算表明λ（n）λ（n）→ 1，这样光谱间隙就消失了。然后概率收敛到n→ ∞, agents1，2。

，bnc均为0，而其余代理的特征向量中心度为正。概率也收敛到n→ ∞, Agent的特征向量中心bnc+1，bnc+2，n均为0，而其余代理的特征向量中心为正。另一方面，vi（(R)A（n））=√对于所有i，sokv（A（n））- v（(R)A（n））k不能以高概率消失。两组之间很有可能没有边，当出现这种情况时，特征向量中心性可以对应于网络的两个相应组件中的任何一个。请注意，该示例并不取决于A（n）或A（n）的最大特征值的多重性，而仅取决于这些矩阵的前两个特征值是否接近。我们在上文中观察到，如果（1）代理度的增长速度远远快于log n，并且（2）任何一小群代理都没有太多的链接，则随机网络序列具有足够大的特征值。当所有主体的度都有界时，很容易构造反例。下一个例子显示，如果链接过于集中，即使度快速增长，定理也会失败。示例2。假设‘A（n）ij=如果i=1或j=1，’A（n）ij=log nnotherwise。序列没有足够大的特征值：最大特征值λ（n）以最大速率增长√2n，最大期望度数为 = （n）- 1） /2，soλ（n）p 日志（n）→ 0、设φ（n）=φ√φ<1时为2N。根据大数定律，在nlarge概率很高的情况下，agent 1的阶数约为n/2，而所有其他agent的阶数约为ylog n。