ACM通信
贡献的文章
网络中的权力理论
来源:iStockPhoto.com
“网络”由一群演员和一组将演员组合在一起的二元关系组成。网络在现实世界中无处不在。自然、社会、信息和技术是由表面上不同的网络支持的，而实际上这些网络有着惊人数量的有趣结构属性。
关键的见解
网络在数学中被建模为“图”，参与者被表示为点(也被称为节点或顶点)，关系被描述为连接成对点的线(也被称为边或弧)。在本文中，我们关注无向图，其中的边没有特定的方向。网络上一个有意义的问题是:哪些是最中心(重要)的节点?人们提出了许多措施来解决这个问题。其中，“特征向量中心性(eigenvector centrality)”(本文简称中心性)指出，如果一个行动者与中心行动者有联系，那么该行动者就是中心的。这个循环定义由一个优雅的递归方程得到
在哪里x是一个矢量，包含了寻求的中心，一个是一个编码网络的矩阵，是一个正常数。在一个网络中，被一条边绑在一起的两个演员被称为邻居。(1)式提出了中心性的两个重要性质:行动者的中心性与其邻居的数量和邻居的中心性直接相关。中心角色是那些有许多联系的人，或者，对于同等数量的联系，中心角色是那些与其他中心角色有联系的人。这个有趣的定义在不同的背景下被反复发现。本文从计量经济学、社会计量学、文献计量学、网络信息检索和网络科学四个方面对其进行了研究;看到Franceschet12历史概览。
然而，在某些情况下，中心——连接到中心的质量——在预测网络中的“权力”轨迹方面的效用有限。2，8，11以交换网络为例，网络中的关系涉及到有价值的物品的转移，如信息、时间、金钱或精力。如果一种关系中的交换促进了另一种关系中的交换，那么这种交换关系就是积极的;如果一种关系中的交换抑制了另一种关系中的交换，那么这种交换关系就是消极的。7在“负交换网络”中，权力来自于与那些几乎没有选择的人联系在一起。与那些有许多可能性的人连接会降低一个人的力量。例如，想想一个以时间为交换价值的社交网络。想象一下，每个演员都有一个有限的时间来听别人说话，每个演员把自己的时间分配给相邻的演员。在一种关系中交换时间，显然排除了在其他关系中交换同一时间。哪些演员最受关注?它们是连接到许多邻居的节点，几乎没有选择，因为它们几乎从所有邻居那里获得全部注意力。另一方面，与拥有许多选择的邻居联系在一起的行动者很少获得考虑，因为他们的邻居大多忙于与他人相处。
在本文中，我们提出了一个网络环境下的权力理论。我们从这个论点开始:如果一个演员和一个无权无势的演员联系在一起，他就是有权力的。我们通过这个等式来实现这个循环命题
在哪里x是寻求的能量向量，一个是矩阵编码网络，和x÷这个向量的元素是它们的倒数吗x．公式(2)表述了权力的两个重要性质:行动者的权力与其邻居的数量直接相关，与邻居的权力呈负相关。第一个属性似乎是合理的;一个演员拥有的纽带越多，他就越强大。第二个性质表征功率;在相同数量的关系中，与没有权力的其他人联系在一起的演员是有权力的。另一方面，与有权力的人捆绑在一起的演员是没有权力的。
中心角色是那些有许多联系的人，或者，对于同等数量的联系，中心角色是那些与其他中心角色有联系的人。
利用组合矩阵理论中的著名结果，研究了方程(2)解的存在唯一性。通过对表示网络的矩阵进行扰动，研究了在不存在解的情况下如何恢复解。我们正式地将引入的权力概念与替代概念联系起来，并在欧洲天然气管网中对它们进行经验比较。
激励的例子
从1962年开始，理查德·爱默生对权力依赖关系进行了开创性的研究11声称权力是社会关系的一种属性，而不是人的一种属性:“X拥有权力”是无意义的，除非我们指明“凌驾于谁”。权力隐含在他人的依赖中，而行动者A对行动者B的依赖与行动者A在由B中介的目标上的动机投入成正比，与A在A-B关系之外获得这些目标的可能性成反比。这种关系之外的目标的可获得性指的是实现目标的其他途径，最明显的是通过其他社会关系。11这种类型的关系权力相对于网络结构而言是内生的，这意味着它是节点在网络中的位置的函数。网络结构之外的外生因素(如诱惑或魅力)可能会加入到内源性力量中来完成画面。
我们从交换网络理论中通常使用的一些小型原型例子开始，以非正式地说明权力的概念，有时也将其与交叉的中心性概念区分开来。10考虑双节点路径
这种情况是完全对称的，一个合理的预测是，两个行动者拥有相同的权力。采用三节点路径
多少改变。直觉上，B是强大的，而A和C不是。事实上，A和C除了B之外都没有其他选择(都依赖于B)，而B可以通过选择另一个来排除其中一个。一个四节点路径
行动者B和C拥有权力，而A和D要么依赖于B，要么依赖于C。然而，这里B的权力要小于三节点路径;在这两种情况下，A都依赖于B，但在三节点路径中，C也依赖于B，而在四节点路径中，C有一个备选节点d，因此，在四节点路径中，节点B相对于三节点路径而言，没有那么强大，因为它的邻居更强大。最后是五节点路径
很有趣，因为它区分了权力和中心。所有传统的中心度量(特征向量、贴近度、间隔)都声称C是中心。然而，B和D是相当强大的。同样，这是因为他们与弱的合作伙伴(A和C或E和C)谈判，而C与强的一方(B和D)讨价还价。这个例子有助于说明权力的另一个微妙方面。注意，在五节点路径和四节点路径中，B被局部相似的节点(A和C)包围;例如，他们在两条路径上都有相同的度。然而，C在五节点路径上的威力要比在四节点路径上的要小得多;因此，我们可以预期在五节点路径上B的幂比在四节点路径上要大。只有当权力的概念超越节点的局部邻域时，这种分离才可能，比如说，权力是递归定义的。
作为一个更大、更现实的例子，请考虑图1，描绘了欧洲的天然气管网。节点是欧洲国家(国家代码根据ISO 3166-1)，如果天然气管道穿越两国边界，两国之间会有一个无向边界。有关数据已从国际能源署网页(http://www.iea.org)．原始数据对应于一个有向的加权多重图，边缘权重对应于管道的最大流量。我们对网络进行了简化和对称，以一致的方式映射边缘的权值。
这是一个负交换网络，因为与一个国家交换天然气排除了与其他国家交换同样的天然气。从直觉上看，强大的国家是那些与其他国家联系紧密、无法交换天然气的国家。假设国家B与国家A和国家C相连，且B是它们的唯一连接，或美国广播公司．A国和C国只能从B国出售或购买天然气，而B国可以在A国和C国之间进行选择。合理地说，B国的议价能力更强，这使得B国在天然气谈判中可以获得更高的收入或更少的费用。
权力理论
让G是一个无向的加权图。这个图G可以包含从节点到自身的“循环”或边。的边缘G都被标注为正权重。让一个的邻接矩阵G；也就是说,一个我,我是边()的权值我,我)，如果该边存在且一个我,我= 0。因此,一个是一个方形的，对称的，非负矩阵。循环在G对应的主对角线上的元素一个．
“中心性问题”是这样的:找一个向量x有正的项
这里> 0是常数。这意味着x我＝j一个我,我xj，即节点的中心性与其相邻节点中心性加权和成正比。这就是谷歌最初的网页排名算法PageRank背后的主要思想。PageRank根据超链接到网页的页面的重要性来确定网页的重要性。除了Web信息检索之外，本论文还成功地应用于不同的环境，包括文献计量学、社会计量学和计量经济学。12
我们定义“幂问题”如下:找到一个向量x有正的项
其中，我们用x÷这个向量的元素是那些的倒数x．这意味着x我＝j一个我,我/xj；即一个节点的幂等于其邻居的幂倒数的加权和。注意,如果x＝斧头÷然后,设置
，我们有y＝唉÷；因此，在功率方程中不需要有比例常数。这种权力的概念与负交换网络有关。2，8在这些网络中，当一种价值在行动者之间沿着一种关系交换时，它就会被消耗掉，而不能沿着另一种关系交换。因此，重要的参与者是那些与许多参与者接触，但交换可能性很少的人。
最后，“平衡问题”如下:找到一个对角矩阵D正的主对角线
是双重随机;也就是，所有的行和列年代总和为1。平衡问题是一个基本问题，据说在20世纪30年代首次被用于计算交通流量4从那时起，它被应用在许多不同的环境中。14
原来，功率问题与平衡问题密切相关。给定一个向量x,让Dx是对角矩阵，它的对角元素与x．因此，我们得到了以下结果。
定理1。向量x是幂问题的一个解当且仅当对角矩阵Dx÷是平衡问题的解决方案吗．
证明。如果爸爸是双随机的吗戴德＝e而且eT爸爸＝eT,在那里e是一个全是1s的向量。实际上,自一个而且D是对称的吗戴德＝eeT爸爸＝eT．如果向量x没有零项，那么Dx是可逆的,Dx1＝Dx÷．我们有
解的存在性与唯一性。我们在定理1中建立的平衡问题和幂问题之间的联系使我们可以利用已经建立的矩阵平衡理论来研究幂问题(方程4)的解。
回想一下正方形的“对角线”n×n矩阵是一个序列n位于矩阵不同行和列上的元素。排列矩阵是一个方阵n×n矩阵的每一行和每列都有一个元素等于1，而其他元素都等于0。每个对角线明显对应于一个置换矩阵，其中对角线元素的位置对应于置换矩阵的单位元素的位置。特别是单位矩阵我是一个排列矩阵，对角线是一个与我叫做主对角线一个．如果对角线的所有元素都大于0，对角线就是正的。一个矩阵一个如果它包含正对角线，则被称为有“支持”，如果包含正对角线，则被称为有“完全支持”一个0和的所有正元素一个位于正对角线上。完全支持显然意味着支持。
一个矩阵是“不可分解(不可约的)”，如果它不可能找到一个排列矩阵P这样
在哪里X而且Z都是方阵，0是0的矩阵;否则一个“可分解(可约)。”如果一个矩阵不能找到置换矩阵，那么这个矩阵就是“完全不可分解的”P而且问这样
在哪里X而且Z都是方阵;否则,一个是“可分解的部分”。显然，矩阵(完全不可分解)也是不可约的。它还认为完全不可分解意味着完全支持。5此外，二部图的邻接矩阵从来不是完全不可分解的，而非二部图的邻接矩阵是完全不可分解的，当且仅当它具有完全支持且不可约。9我们说一个图有支持度，有完全支持度，不可约，和完全不可分解，如果对应的邻接矩阵有这些性质。
刚才概述的组合概念相当简洁。幸运的是，它们中的大多数在图论中有一个简单的解释。我们知道邻接矩阵的不可约性对应于图的连通性。此外，给定一个无向图G，让我们定义一个“跨越循环林”G的生成子图G其连接的组件为单边或环，包括长度为1的环。邻接矩阵中的对角线与图中的生成循环林之间存在对应关系是很容易实现的。因此，当且仅当一个图包含一个生成循环林时，它具有支持度;当且仅当每个边都包含在一个生成循环林中时，它具有全部支持度。文中给出了四个例子图2．
定理2。设A是一个对称的非负方阵。DAD形式的双随机矩阵S存在的充要条件是A有总支撑，其中D是一个主对角线为正的对角线矩阵。如果S存在，那么它是唯一的。如果A是完全不可分解的，那么矩阵D是唯一的．
由此可见，功率问题x＝斧头÷对一类图有一个完全支持的解决方案。此外，如果图是完全不可分解的，那么解也是唯一的。
扰动(恢复解)。邻接矩阵缺乏完全支持的图的幂问题是什么?对于这样的图，幂问题没有解。但是，通过适当的扰动图的邻接矩阵，可以重新得到解。研究了邻接矩阵上的两个摄动一个
- 对角微扰：
＝一个+我,在那里> 0为阻尼参数，我是单位矩阵。 - 完整的摄动：
＝一个+E,在那里> 0为阻尼参数，E是一个全1的矩阵。
矩阵明明是完全不可分解的，有全部的支持，而且是不可约的。因此，一个全摄动矩阵的幂问题(以及中心问题)有一个唯一的解。另一方面，矩阵总支持。事实上,如果一个我,我> 0,我＝j，然后是主对角线一个k, k1kn是正面的，包含一个我,我．如果我j，然后是对角线一个我,我，一个k, k1kn而且k我,我是正面的，包含一个我,我．因此，对角摄动矩阵的幂问题有一个解。此外，解是唯一的，如果一个是不可约的，因为已知对于对称矩阵一个它认为,一个是否不可约当且仅当一个+我完全不可分的。6有趣的是，对角扰动除了提供了方法的收敛性外，还有助于在模型中加入外源动力。方法中设置一个正值我对角线的第Th个位置，就是这个节点我具有最小的功率，或不是一个功能的节点在网络中的位置。因此，我们可以利用邻接矩阵的对角线来分配节点，这些节点可能具有不同的外生能量输入级别。
直观上，对角扰动比完全对角扰动的侵入性更小;前者只修改对角线上的元素，后者涉及所有矩阵元素。但是，相对于所产生的能量，这种扰动的侵入性有多大呢?为了研究这个问题，我们计算了原始和扰动功率解之间的相关性。一个简单而直观的衡量两个排名之间的相关性的规模n是肯德尔等级相关系数吗k，这是和式对的分数之间的差c(谐和对的个数除以n（n1)/2)和不一致对的d在两个排名中:k＝cd．系数范围为1 ~ 1，负值为负相关，正值为正相关，接近0值为独立性。我们使用了以下网络数据集:海豚之间的社交网络，马德里火车爆炸恐怖分子网络，爵士音乐家的社交网络，空手道俱乐部成员之间的友谊网络，网络科学领域的学者合作网络，以及小说中人物的共同出现网络安娜卡列尼娜Lev Tolstoj。
本实验的主要结果如下(见图3):只要阻尼参数很小，对角扰动和全扰动对原始功率的影响都不明显;对角扰动时的功率比完全扰动时的功率更接近原始功率;阻尼参数越大，扰动解对原始解的坚守程度越低。
计算能力。由于平衡问题和功率问题之间已经建立了一定的关系，因此我们可以用已知的方法来求解前者。求解式(4)最简单的方法是建立迭代法
被称为SinkhornKnopp方法(SKM)。17如果我们将x0＝e，所有1s的向量，然后是第一次迭代x1＝Ae；也就是说,x1（我) =j一个我,我是学位d我的我．第二次迭代x2＝一个（Ae）÷；也就是说,x2（我) =j一个我,我/d我的邻域的次数倒数的和是我．
如果一个，那么SKM收敛，或者更精确地说，该方法的偶和奇迭代收敛于差一个乘常数的功率向量。该算法的收敛是线性的，其收敛速度取决于平衡矩阵的次特征值年代＝爸爸(定理2)。17然而，在某些情况下，收敛会非常缓慢。骑士和鲁伊斯14提出了一种基于牛顿方法(NM)的快速算法，我们现在根据我们的设置和符号描述。为了求解(4)式，我们应用NM来寻找函数的零点f：nn定义为f（x) =x斧头÷．这一点不难验证
在哪里我,我．= 1,如果我＝j而且我,我= 0。我们把这些偏导数放在雅可比矩阵中f结果是
的平方在哪里x是有意进入。形式上，NM应用于方程f（x) = 0变为
为了精确地应用NM，需要在每一步求解一个线性系统，但这将是太昂贵了。然而，用迭代法得到的系统的近似解是充分的，引起了内迭代。当需要平衡的矩阵是对称和稀疏的时候，这种方法很有吸引力，这是真实网络中的幂问题的情况。14
我们通过实验评估了真实社会网络中权力计算的复杂性;事实上，为了处理完全支持的图，我们在前三个网络中使用了最大的双连接组件。我们同时使用SKM和NM。我们考虑了对原始矩阵和扰动矩阵的计算。我们以幂法(PM)中心性计算的复杂度为基准。复杂度表示为矩阵向量乘积运算的总次数。如果矩阵是稀疏的(所有被测试网络都是如此)，则这种操作在图的节点数量上具有线性复杂度。主要的实证结果总结如下(见表1): SKM在原始矩阵上的速度显著慢于PM，对角扰动对其速度没有显著影响;完全摄动显著提高了SKM算法的速度，因此完全摄动SKM算法的复杂度与PM算法的复杂度相当(且阻尼参数越大，算法速度越快);原始矩阵上的NM比SKM快得多:其复杂度与完全扰动的SKM和PM相当;对角扰动下的NM比NM更快，且阻尼参数越大，算法速度越快。
与替代能源措施的关系。Bonacich2提出了基于两个参数的参数测度家族:而且．如果一个图的邻接矩阵是波那奇索引吗x被定义为
节点的索引是两个分量的和:第一个分量(由参数加权))取决于节点的程度，以及第二个(由参数加权))依赖于节点邻居的索引。由式(6)，条件为我一个是不是奇异的，就有可能得到下面所提出的测度的明确表示
当|时，与无穷大和等价| < 1 /r,在那里r=最大我|我|,我．的特征值一个；也就是说,r的谱半径是一个．当参数是正的，该指数是一个中心性的衡量。特别地，该测度将特征向量中心性作为一种极限方法1 /r．另一方面，当为负时，指数为幂测度;它对应于奇数长度路径(正号)和偶数长度路径(负号)的加权和。2因此，强大的节点对应的是具有许多弱邻居的节点。最后,当= 0时，衡量标准归结为度中心性。
这种测量的困难在于它是参数化的;也就是说，它取决于参数而且．而参数的设置很简单，可用于分配节点外生功率，参数的选择更微妙的。特别是，当参数|时，索引是有意义的| < 1 /r，因此有光谱半径r必须计算或至少近似。
波那契指数与负的精确关系，式(4)中定义的幂函数的解释如下x0= (1 /）e在牛顿迭代中，我们得到了前面所描述的功率的计算
但是第一种近似是波纳奇方法家族的一员= 2而且＝2．自是消极的，我们面对的确实是一种力量的衡量。因此，波纳奇幂可以被认为是一阶近似的幂利用NM。
波等。3.研究了节点集上的功率度量。给定一个节点集T让B（T)是其邻居都属于的节点的集合T．请注意B（T)与外界没有联系T，因此可能受节点的支配T．我们定义一个幂函数p这样p（T) = |B（T) | |T|。因此,一组T如果它有可能控制更多的邻居，那么它是强大的吗B（T)．幂测度被解释为联盟博弈在图上的特征函数和博弈的“沙普利值”;或者提出一个节点加入任意节点集时，其对功率的平均边际贡献作为单个节点功率的度量。有趣的是，所发现的博弈论幂测度对应于SKM的第二次迭代，用于计算如式(4)所定义的幂;也就是邻域度倒数的和。
一个国家的实力多少与邻国的实力成反比。
对权力的研究在经济学(对议价能力的承认)和社会学(对社会权力的解释)中都有很长的历史。10考虑最基本的情况，只有两个参与者，一个而且B他们正在就如何分配一单位的钱进行谈判。每个参与者都有一个备选方案，在谈判失败的情况下可以收集备份量，比如，为一个而且为B．一个自然的预测，被称为“纳什议价方案”，15这两个演员会平分剩余的钱吗年代= 1，如有，则在两者之间相等;也就是说,如果年代< 0之间不一致一个而且B是可能的，因为对于至少一方来说，任何分裂都比备份选项更糟糕。另一方面，如果年代> = 0一个而且B会达成一致+年代/ 2一个而且+年代/ 2B．
库克等人提出了将纳什议价方案从行动者对自然扩展到行动者网络。8和Rochford16和进一步的研究，特别是在Bayati等人。1和Kleinberg等人。13在下面的内容中，我们将描述捕获这种扩展的动态过程。让一个是一个无向无权图的邻接矩阵G．因此,一个我,我= 1，如果有一条边(我,我)G而且一个我,我= 0。行动者之间的协商只能沿着边缘进行;每对处于边缘的参与者协商一个固定数量的1，并且每个参与者最多可以与一个邻居结束协商(一个交换规则)。对于每条边(我,我)定义
- R我,我作为演员的“收入”数额我在谈判中与j．
- l我,我作为演员的收入数额我在最佳替代谈判中收到，排除与j．
注意到矩阵R而且l和?一样的零-非零模式一个．更准确地说，考虑下面的迭代过程。我们开始
对于所有边(我,我),
其他地方。让N（我)为节点的邻居集合我．为t> 0，最佳替代矩阵l（t）在时间t是
让盈余
是哪个演员的量我而且j到时会协商t；请注意,演员我永远不会接受来自j比他的选择要少
,演员j永远不会接受来自我比她的选择少
利润矩阵R（t）在时间t然后
请注意,
也就是说,
而且
纳什的谈判解决方案是演员之间的谈判吗我而且j考虑到他们的其他选择而且让R成为迭代过程的固定点R（t）种植时间t．“纳什力量”x我的节点我收入最高的是演员吗我在其邻国;这是
在许多其他有吸引力的结果中，Bayati等人。1证明了动力学总是收敛于不动点解。纳什力与我们在此提出和研究的纳什力有一些相似之处;特别是，这两个概念具有相同的递归的“强者与弱者相联系”的哲学。演员的纳什力我直接取决于收入我在它的邻国中，这些国家直接依赖于我其邻国之间，则反过来依赖邻国的收入我，这决定了邻国的力量我．因此，一个国家的力量多少与邻国的力量成反比。
利用肯德尔相关性(Kendall correlation)，我们评估了本文定义的权力重叠的中心性和程度，以及Bonacich权力(带负参数的Bonacich指数))、沙普利(Shapley)力(邻居度的倒数之和)以及之前提到的社交网络上的纳什力。主要的实证结果总结如下(见表2):正如预期的那样，权力、中心性与程度呈正相关，但在排除程度的影响后，权力与中心性呈负相关(我们采用偏相关);功率与波纳奇功率呈正相关，且相关性随参数增大而增大从0下降到1/r,r邻接图矩阵的谱半径(邻接矩阵受扰动时关联更大);权力与沙普利权力呈正相关，且这种关联一般比波纳奇权力更强;权力与Nash议价网络权力呈正相关，但其相关强度普遍低于Shapley权力和Bonacich权力。特别地，我们注意到，基于纳什的方法将被调查网络的节点的能量得分映射到一个小的值集，接近0、0.5和1的值的频率非常高。因此，很难区分节点的不同功率等级。
激励的例子重新加载
在这里，我们重温“激励例子”一节中的例子，用它们作为基准来比较“与替代动力措施的关系”一节中描述的不同权力概念。当图不完全支持时(除两节点路径外的所有情况)，我们使用阻尼0.15的对角摄动来获得解。此外，我们设置Bonacich索引参数= 1,= 0.85 /r,在那里r是图的谱半径。
在双节点路径中，所有方法都同意给予两个节点相同的权力。三节点路径美国广播公司，所有的方法都认为B是最强大的。值得注意的是，纳什幂将所有的幂(1)分配给B，而没有幂(0)分配给A和C，而其他方法认为A和C持有少量的幂。在四节点路径中ABCD，所有的方法都声称B和C是强大的。此外，所有方法都认识到B在这个实例中的功率小于它在三节点路径中的功率。最后，在五节点路径中中的，所有方法都将B和D区分为最强大的节点，其次是C，最后是A和E，只有纳什幂例外，它将所有的幂(1)分配给B和D，将零幂(0)分配给所有其他节点;因此，根据该方法，中心节点C与外围节点A和E具有相同的功率。所有的方法，除了Shapley，都注意到在五节点路径上B的幂比在三节点路径上要大。这是因为Shapley是一个局部方法，而其他方法是全局(递归)方法。
现在让我们回顾一下天然气管道的例子。我们根据以下权力和中心性指标对所有国家进行排名:Shapley权力(S)、Bonacich权力(B)、本文定义的权力(P)、纳什权力(N)和特征向量中心性(C)。表3为对应的肯德尔相关矩阵。正如预期的那样，P与其近似的B和s有很好的相关性，而且P与N正相关，但相关强度较弱。此外，P和C之间的联系是正的，但很弱，主要是由与两种测量的程度的联系解释。事实上，如果我们排除程度的影响，这种相关性是负的。
这些关联反映在《科学》所列的前10个排名和评级中表4，以及比较权力和中心性的散点图图4．请注意德国(DE)是如何强大和核心的;意大利(IT)和土耳其(TR)很强大，但不是中心;挪威(NO)处于中心地位，但并不强大;还有很多国家在排名之外既不强大也不处于中心位置。例如，意大利与既无能又边缘的国家签订合同，即奥地利、瑞士、克罗地亚、突尼斯、利比亚和斯洛文尼亚，只有奥地利进入了前10名的权力名单，只有奥地利和瑞士进入了前10名的中心地位名单(不是在第一位置)。与其他权力衡量标准相比，纳什权力的排名有些不同寻常;例如，德国的议价能力为0.5，只有14th地位，与其他国家挂钩。值得注意的是，广义纳什议价解决方案最初是在分配问题的背景下提出的(如公寓与租客匹配，学生与大学匹配)，并没有被建议作为网络中节点的评级和排名方法。例如，在天然气网络的平衡匹配方面，意大利最好与利比亚谈判，土耳其与格鲁吉亚谈判。事实上，库克和山岸8提出利用该方案中各节点的协商值作为结构功率度量;参见Easley和Kleinberg10(第12章)以作类似的解释。根据我们为这篇文章所做的实验，这种解释似乎是可预见的，但进一步的调查是必要的，以获得一个坚实的结论。
结论
我们提出了一个网络环境下的权力理论。我们权力概念的基础哲学认为，如果一个行为者与许多无权无势的行为者联系在一起，他就是有权力的。这篇论文主要在社会学和经济学中有其根源和应用，并追溯了与它著名的线性对应物，即特征向量中心性的历史平行。12
我们对权力的定义的优点是:它是一种简单、优雅、易懂的衡量标准;它在理论上有着良好的基础，并且与经过充分研究的平衡问题直接相关，这使得我们能够从这种设置中借鉴结果和技术;这个公式不是参数化的;它是全局的(一个节点的功率依赖于整个网络)，可以用一个简单的局部测量来近似，即节点度的倒数之和，具有博弈论解释，可以在所有网络上有效地计算。该定义也有局限性，主要是精确解只存在于完全支持的网络类中，不能立即归一化，因此在比较不同网络中节点的功率值时需要注意。
参考文献
1.M. Bayati, Borgs, C.， Chayes, J.， Kanoria, Y.， Montanari, A. A.交换网络中的讨价还价动态。j .经济学。理论156(2015), 417454。
2.权力与中心性:一系列衡量标准。点。j . Sociol。92， 5(1987)， 11701182。
3.Bozzo, E.， Franceschet, M.和Rinaldi, F.网络上的脆弱性和力量。网络科学。3， 2(2015)， 196226。
4.Brown, j.b.， Chase, p.j.， Pittenger, A.O.，迭代缩放的阶独立性和因子收敛。线性代数应用190(1993), 138。
5.完全支持0和1的矩阵。j . Combin。Ser的理论。一个28， 3(1980)， 249256。
6.R.A. Brualdi和H.J. Ryser《组合矩阵理论》，《数学百科全书及其应用》第39卷．剑桥大学出版社，英国剑桥，1991年。
7.库克，k.s.，爱默生，r.m.，吉尔摩，m.r.和山岸，T.交换网络中的功率分配:理论和实验结果。点。j . Sociol。89， 2(1983)， 275305。
8.Cook, K.S.， Yamagishi, T. .交换网络中的功率:一个功率依赖公式。社交网络14(1992), 245265。
9.J.和B.N.对称非负矩阵的DAD定理。j . Combin。理论12， 1(1972)， 147152。
10.伊斯利博士和克莱因伯格博士。网络、人群和市场:关于高度连接世界的推理．剑桥大学出版社，纽约，2010。
11.权力依赖关系。点。Sociol。启27， 1(1962)， 3141。
12.站在巨人的肩膀上。Commun。ACM 54， 6(2011)， 92101。
13.刘志刚，刘志刚，刘志刚。社会交换网络的平衡结果。在40周年会议的会议记录th计算机学会计算理论年会(2008), 295304。
14.奈特，P.A.和鲁伊斯，D.一种矩阵平衡的快速算法。IMA j .号码。33肛门。， 3(2013)， 10291047。
15.J.纳什的《议价问题》。费雪18(1950), 155162。
16.Rochford, S.C.在分配市场上对称的两两讨价还价的分配。j .经济学。理论34， 2(1984)， 262281。
数据
图2。(左上角)这个图没有支持，因为没有一个生成循环森林。(右上图)。图有边(1,4)和边(2,3)构成的支撑，但支撑不是全部;(边(1,3)和(1,2)不属于任何生成环图。(左下)图有完全支持，但不是不可约的，因此不是完全不可分解的。(右下)图具有完全支持，且不可约，不可二部，因此是完全不可分解的。
图3。原始功率和扰动功率之间的相关性使海豚社交网络中最大的双连通部分的阻尼参数从0到1变化(这有全部支持)。水平线对应对角扰动与最大阻尼的相关性。其他网络上的相关性也是类似的。
表
表1。不同方法计算功率的复杂性:PM(基准);完全支持网络中无扰动的SKM;SKM- d(对角扰动和阻尼0.15的SKM);SKM- f(全扰动阻尼0.01的SKM);全支持网络中无扰动的NM;NM- d(对角扰动和阻尼0.15的NM)。
表2。本文定义的权力相关度(D)、中心性(C)、Bonacich权力(B)、Shapley权力(S)、Nash权力(N)。
数字图书馆是由计算机协会出版的。版权所有©2016 ACM股份有限公司
没有发现记录