本章将先简单回顾无向无权网络中节点的度、H指数和核数之间的关系，而接下来的两小节，本文尝试将度、H指数和核数之间的关系推广到无向含权网络与有向含权网络中。这种推广并不那么显而易见，而是需要一定的特殊处理。

文献[31]给出了无向无权网络上节点的度、H指数和核数之间的关系证明，此处做简单回顾。定义作用在有限的整数序列$ ({x_1}, {x_2}, \cdots, {x_n}) $上的算子$ {\cal H} $，它将返回一个整数$ y = {\cal H}({x_1}, {x_2}, \cdots, {x_\text{n}}) > 0 $，$ y $表示这个集合中最多存在$ y $个不小于$ y $的整数。例如，对于一个发表了$ n $篇文章的学者来说，$ {x_1}, {x_2}, \cdots, {x_n} $就是每一篇文章的他引次数，$ {\cal H}({x_1}, {x_2}, \cdots, {x_\text{n}}) $就是该学者的H指数。在一个无向简单网络$ G(V, E) $中，$ V $是节点集合，$ E $是连边集合，任意节点$ i $的度被记为$ {k_i} $, 它的邻居的度依次被记为$ {k_{{j_1}}}, {k_{j{}_2}}, \cdots, {k_{{j_{{k_i}}}}} $，则定义节点$ i $的H指数为：

同时可迭代定义节点$ i $的$ n(n > 0) $阶H指数为$ h_i^{(n)} $:

式中，节点的度等于其0阶H指数$ h_i^{(0)} = {k_i} $，节点的H指数等于其1阶H指数，即$ h_i^{(1)} = {h_i} $。

定理1  (DHC定理)对于无向无权网络$ G(V, E) $上的任一节点$ i \in V $, 它的H指数$ h_i^{(0)}, h_i^{(1)}, h_i^{(2)}, \cdots $最终收敛到节点$ i $的核数$ {c_i} $，即：

这个定理说明度、H指数和核数，可以通过一个简单的算子$ \mathcal{H} $连接起来，而度、H指数和核数是这一算子运算的初态、中间态和稳态。给定一个网络$ G(V, E) $，当任给一个节点$ i $，都有$ h_{i}^{(n)}=h_{i}^{(n+1)} $成立时，则称节点$ i $的核数$ c_{i}^{{}} $等于$ h_{i}^{(n)} $。网络的收敛时间$ n{}_{\infty } $定义为$ \mathcal{H} $算子从度迭代计算到核数所需要的最小的迭代次数，即$ n{}_{\infty } $是使得$ h_{i}^{({{n}_{\infty }})}=h_{i}^{\infty }={{c}_{i}}, \forall i\in V $成立的的最小整数。

值得注意的是，定理1给出了一种不同于$ k $-壳分解的计算节点核数与网络层数的新方法。

定理2  给定一个无向简单网络$ G(V, E) $，对于任意节点$ j\in V $，定义$ {{g}_{j}}={{k}_{j}} $, 在每一次异步更新迭代过程中，随机选择一个$ i $节点更新其$ g $值：

式中，$ {{j}_{1}}, {{j}_{2}}, \cdots, {{j}_{{{k}_{i}}}} $是节点$ i $的邻居。如果$ \left| V \right| $是有限值，那么这个更新过程将会在迭代有限的次数之后达到一个稳定状态，表示为$ (g_{1}^{\infty }, g_{2}^{\infty }, \cdots, g_{\left| V \right|}^{\infty }) $，即此时对于任何节点的更新都不会让该节点的$ g $值发生变化：

并且对于任意节点，都有$ g_{i}^{\infty }={{c}_{i}} $。

定理2说明，在异步更新中该方法仍然可以保证收敛，这使得可以通过一种非中心化的、局部化的方法来计算节点核数与网络层数^[32]。

权的H指数计算中只考虑了节点的度信息，并没有考虑节点之间连边的权重。然而，在实际中很多网络都是含权的，而且连边的权重往往具有重要意义。例如，在社交网络中，边权表示两个人之间关系的亲密程度；在国际贸易网络中，边权可以表示两个国家之间的贸易额等。无权的H指数方法相当于把所有的边权当作1来处理。

为了能够更加真实全面的反映含权网络的信息以及更加准确的评估节点的影响力^[33]，将该方法扩展到含权网络上成为必然。定义节点$ i $的含权H指数为一个作用在节点$ i $的所有邻居节点的含权度(也称节点强度)上的函数，记为$ {{H}^{w}} $，即：

式中，$ {{j}_{1}}, {{j}_{2}}, \cdots, {{j}_{{{k}_{i}}}} $是节点$ i $的邻居；$ {{k}_{i}} $等于节点$ i $的度，且二元数对$ ({{w}_{i{{j}_{*}}}}, {{s}_{{{j}_{*}}}}) $按照强度$ {{s}_{{{j}_{*}}}} $的大小降序排列；$ {{\mathcal{H}}^{w}} $函数返回一个最大实数$ x $，且$ x $满足$ f(x)\ge x $，这里：

接下来，分别讨论边权是整数和实数两种情况下的计算方法。

本部分将以整数边权为例研究带有离散权重的含权网络。在整数边权的情况下，可以将每一条边权为$ w $的边分解成$ w $条权重均为1的边。设有节点$ i $，它的度为$ {{k}_{i}} $，它与邻居$ j $的连边权重为$ {{w}_{ij}} $，它的邻居节点分别为$ ({{j}_{1}}, {{j}_{2}}, \cdots, {{j}_{{{k}_{i}}}}) $，邻居节点的强度分别为$ ({{s}_{{{j}_{1}}}}, {{s}_{{{j}_{2}}}}, \cdots, {{s}_{{{j}_{{{k}_{i}}}}}})\text{且}{{s}_{{{j}_{1}}}}\ge {{s}_{{{j}_{2}}}}\ge \cdots \ge {{s}_{{{j}_{{{k}_{i}}}}}} $，则式(6) 也可以表示为：

以图 1为例，计算节点f的含权H指数$ h_{f}^{w} $为：

图  1  含权网络示例

也可以借助直角坐标系来更清楚地展示含权$ {{H}^{w}} $函数的计算过程。仍以图 1中节点f为例，把它的邻居按照其强度大小做降序排序，并将每个节点重复$ {{w}_{ij}} $次，如式(9) 的序列，然后绘入坐标系中，横坐标为节点，纵坐标为强度，如图 2所示。此时，这些点与X轴和Y轴围成的区域中存在一个以原点(0, 0) 为顶点的面积最大的正方形，这个正方形的边长$ h $就是节点f的$ {{H}^{w}} $指数值。

图  2  含权$ {{H}^{w}} $函数的图像表达

同样地，也可以把含权的$ {{H}^{w}} $指数做迭代，类似于式(1) 和式(2)，得到含权的$ n $阶$ {{H}^{w}} $指数：

式中，节点的强度等于其0阶$ {{H}^{w}} $指数$ h_{i}^{w(0)}={{s}_{i}} $，节点的$ {{H}^{w}} $指数等于其1阶$ {{H}^{w}} $指数$ h_{i}^{w}=h_{i}^{w(1)} $。

在实数权重下计算含权$ {{H}^{w}} $指数时，式(8) 已经不再适用。然而利用坐标轴计算含权$ {{H}^{w}} $指数在实数权重的情况下依然适用。根据上述方法，式(6) 的计算过程为：对于节点$ i $(其度为$ {{k}_{i}} $)，如果$ {{k}_{i}}=1 $，则$ h_{i}^{w} $的值取$ {{w}_{i{{j}_{1}}}} $与$ {{s}_{{{j}_{1}}}} $中较小的值；当$ {{k}_{i}}>1 $，则寻找一个整数$ k(k<{{k}_{i}}) $，使得式(12) 成立：

根据图 3所示的两种情况可知，当$ \sum\limits_{m=1}^{k}{{{w}_{i{{j}_{m}}}}\ge {{s}_{{{j}_{k+1}}}}} $时，所得结果如图 3a所示，即$ h_{i}^{w}=\sum\limits_{m=1}^{k}{{{w}_{i{{j}_{m}}}}} $；当$ \sum\limits_{m=1}^{k}{{{w}_{i{{j}_{m}}}}<{{s}_{{{j}_{k+1}}}}} $时，所得结果如图 3b所示，即$ h_{i}^{w}={{s}_{{{j}_{k+1}}}} $。

综上可知，节点$ i $的含权$ {{H}^{w}} $数为：

图  3  连续权重下的含权$ {{H}^{w}} $函数计算^[33]

式中，$ \min \left\{ {{w}_{i{{j}_{1}}}}, {{s}_{{{j}_{1}}}} \right\} $表示$ h_{i}^{w} $取两者中的较小值，$ \max \left\{ \sum\limits_{m=1}^{k}{{{w}_{i{{j}_{m}}}}}, {{s}_{{{j}_{k+1}}}} \right\} $表示$ h_{i}^{w} $取两者中的较大值。

同样，节点$ i $在连续权重下的$ n $阶含权$ {{H}^{w}} $指数就可以表示为：

式中，节点的强度等于其0阶$ {{H}^{w}} $指数$ h_{i}^{w(0)}={{s}_{i}} $，节点的$ {{H}^{w}} $指数等于其1阶$ {{H}^{w}} $指数$ h_{i}^{w}=h_{i}^{w(1)} $(按照式(6) 计算)。

含权网络的k-壳分解法^[34]定义如下：找到网络中强度最小的节点集合$ S $，设此时最小强度值为$ {{s}_{\text{min}-\text{1}}} $，删除网络中所有出现在该集合中的节点及其与邻居的连边；然后在经过上一步操作的网络上，继续找出所有强度小于等于$ {{s}_{\text{min}-\text{1}}} $的节点加入集合$ S $，然后将它们及其与邻居的连边删除。重复以上操作，直至网络中所有节点的强度都大于$ {{s}_{\text{min}-\text{1}}} $。此时集合$ S $中的节点组成一层，称为原网络含权$ {{s}_{\min -1}} $-壳，记为$ k_{s}^{w}={{s}_{\text{min}-\text{1}}} $。继续上述方法，可以得到网络的含权$ {{s}_{\text{min}-\text{2}}} $-壳。按照同样的方式反复操作，直到网络中没有节点为止。按照上述定义，原网络中的孤立节点(即度为0的点)就属于0-壳，记为$ k_{s}^{w}=0 $。类似的，一个含权网络经过上述的含权k-壳分解后，网络中所有的节点都有一个唯一的$ k_{s}^{w} $值，并且$ k_{s}^{w} $小于等于节点的强度，称这一值为节点的含权核数，记为$ c_{{}}^{w}={{s}_{\text{min}-\text{1}}} $。

同时，把k-壳分解后网络中所有$ k_{s}^{w} $大于等于k的节点称为该网络的含权k-核(k-core)。也就是说，网络的含权k-核是网络中所有$ k_{s}^{w} $大于等于k的含权k-壳的并集。在一个边权为整数的连通的含权网络中，含权1-核就包含了网络的所有节点。经过研究我们发现在含权网络中DHC定理依然有效。

定理3  (含权网络中的DHC定理)对于无向含权网络$ G(V, E, W) $上的任一节点$ i\in V $，无论是在同步迭代更新还是异步迭代更新中，它的含权$ {{H}^{w}} $指数$ h_{i}^{w(0)}, h_{i}^{w(1)}, h_{i}^{w(2)}, \cdots $最终都会收敛到节点$ i $的含权核数$ c_{i}^{w} $，即：

定理3证明见补充材料^[35]。

进一步，本文将该方法扩展到有向含权网络上。对于有向含权网络$ G<V, E, W> $，定义其上任意节点$ i $的入向含权H指数(记为$ {{H}^{{{w}_{\text{in}}}}} $)为一个作用在节点$ i $的所有邻居节点的含权入度(此处以入向强度为例)上的函数，即：

式中，$ {{j}_{1}}, {{j}_{2}}, \cdots, {{j}_{k_{i}^{\text{in}}}} $是节点$ i $的入向邻居，按照节点的入强度$ s_{{{j}_{*}}}^{\text{in}} $降序排列；$ k_{i}^{in} $为节点的入度，即入向邻居的个数；$ {{w}_{{{j}_{*}}i}} $是从邻居节点$ {{j}_{*}} $指向节点$ i $的连边的权重。零阶的$ {{H}^{{{w}_{\text{in}}}}} $指数定义为：

而其$ n $阶$ {{H}^{{{w}_{\text{in}}}}} $指数可迭代定义为：

同理，得到节点$ i $的出向$ {{H}^{{{w}_{\text{in}}}}} $指数：

定理4  对于有向含权网络$ G<V, E, W> $上的任一节点$ i\in V $，无论是在同步迭代更新还是异步迭代更新中，它的入向含权$ {{H}^{{{w}_{\text{in}}}(n)}} $指数序列和出向含权$ {{H}^{{{w}_{\rm{out}}}(n)}} $指数序列最终都会分别收敛到节点$ i $的入向含权核数$ c_{i}^{{{w}_{\rm{in}}}} $和出向含权核数$ c_{i}^{{{w}_{\rm{out}}}} $，即：

定理4证明类似定理3，不再赘述。

为了验证含权H指数的性能，接下来在C. elegans网络^[36]、USAir网络^[37]和将在本文第3部分提到的中国城市间的微博转发网络(Weibo)，这3个无向含权网络上进行实验，并将结果与无向无权H指数作出比较。C. elegans网络是秀丽隐杆线虫(C. elegans)的新陈代谢网络，节点表示神经元，连边表示它们之间的突触连接；USAir网络是美国航空网络，节点表示机场，连边代表他们之间存在直飞航线，连边权重代表这两个机场的距离(已做归一化处理)。3个网络的基本属性如表 1所示。

首先，比较含权H指数与不含权H指数对网络层数的划分情况。实际上，无权H指数与无权$ k $-壳分解作为节点排序算法的时候，一个主要缺陷就是节点的层级划分少，导致很多处于同一层的节点无法区分重要性。如表 2所示，$ H $、$ {{H}^{w}} $、$ c $、$ {{c}^{w}} $分别为无权H指数、含权H指数、无权核数、含权核数4种指标下的网络层数划分情况，$ {{n}_{\infty }} $与$ n_{\infty }^{w} $分别代表无权H指数与含权H指数的收敛时间。显然，无论是H指数还是核数，含权的方法都可以得到更精细的划分，对于节点的分辨能力更高；同时，含权网络的收敛时间并没有大幅上升。

接下来，继续分析含权与无权H指数这两种方法的重要节点识别的准确性。分别将含权与无权情况下的H指数和核数与WSIR模型^[38]的仿真结果做相关性分析，计算它们之间的Kendall Tau(τ)相关系数^[39]，结果如表 3所示。结果表明，无论是以H指数，还是节点核数作为计算指标，含权的方法都比不含权的方法的重要节点排序准确性更高。

最后，本文分析权重因素对含权H指数的节点排序结果的准确率的影响。对边权进行重新分配，定义节点i和j的连边的新权重为：

式中，$ {{w}_{ij}} $是原网络中连边$ {{e}_{ij}} $的权重。特别地，当$ \alpha \text{=0} $时原网络变为不含权的。接下来比较不同$ \alpha $时的含权H指数的排序结果与WSIR模型所得结果的Kendall Tau(τ)相关系数。$ \tau $值越大，说明含权H指数方法对节点的排序越准确。实验结果如图 4所示。从图中可以看出，随着边权调整因子$ \alpha $的变化，3个网络都存在一个峰值：在C.elegans网络上，当$ \alpha \text{=0}\text{.62} $时，取到峰值$ {{\tau }_{\text{max}}}\text{=0}\text{.666} $；在USAir网络上，当$ \alpha \text{=0}\text{.72} $时，取到峰值$ {{\tau }_{\text{max}}}\text{=0}\text{.710} $；而在城市间微博转发网络上，当$ \alpha \text{=1}\text{.05} $时，取到峰值$ {{\tau }_{\text{max}}}\text{=0}\text{.701} $。由此，可以通过调整$ \alpha $，进一步提升含权H指数方法的准确性。有意思的是，在原网络对应的不含权网络中(即$ \alpha \text{=0} $时)，节点排序的准确率都比较低，甚至为最低。这在某种程度上说明了一般情况下，不可以简单地将含权网络映射为同结构的不含权网络，否则将损失很多重要的信息。更进一步地，这也启示我们，很多不含权网络上的指标和方法不能简单地套用到含权网络上。实际存在的更多是含有更多信息的含权网络^[40]。

图  4  使用参数$ \alpha $对权重重新分布情况下得到的H指数与WSIR模型所得结果的相关性τ

为了研究社交网络上信息流动的空间特性，本文通过爬取新浪微博(www.weibo.com)上的微博转发数据，提取含有准确用户位置(精确到城市)的转发记录，构建了代表不同城市间信息流动的有向含权网络。例如注册城市为city1的用户转发了注册城市为city2的用户m条微博，则在最终生成的网络中表示为：“city2 →city1 m”，节点表示城市，连边方向表示信息的流动方向，边权“1”表示位置为city1的用户对位置为city2的用户的微博的转发总次数为1。该有向网络的统计特性如表 4所示，其中，$ {{L}^{\text{out}}} $、C、D和Q分别代表网络的出向平均路径长度、聚类系数、图密度和模块度。图 5中分别展示了连边权重的概率分布，节点的出向强度和入向强度的累积概率分布。图 6为权重与H指数的阶数对于网络层数的影响。

图  5  城市间微博转发网络的基本属性

图  6  权重与H指数的阶数对于网络层数的影响

图 7给出了城市间微博转发网络的邻接矩阵热度图。这是一个不对称的邻接矩阵，图中已将相同省份的城市连续编号，而且同一省份的城市按照其出强度大小降序编号。图中已对转发量取自然数e为底的对数，并用颜色深浅表示其大小，行累加与列累加分别为一个城市的出强度与入强度。从图中可以发现省内城市之间的微博互动要比不同省份的城市之间的互动更多一些。此外，省会城市几乎全排在各自省(或自治区，下同)内的第一位，且图中明显可以看出这些省会城市在省际之间的活跃度要远高于非城会城市。

图  7  城市间微博转发热度图

本文在城市间微博转发网络上分别计算了节点的出向强度$ {{s}^{\rm{out}}} $，出向含权H指数$ {{h}^{{{w}_{\rm{out}}}}} $，出向含权核数$ {{c}^{{{w}_{\rm{out}}}}} $，入向强度$ {{s}^{\rm{in}}} $，入向含权H指数$ {{h}^{{{w}_{\rm{in}}}}} $，入向含权核数$ {{c}^{{{w}_{\rm{in}}}}} $，并和对应的无权指标一一加以对比，发现含权的指标在排序准确率和分辨率上都优于无权的指标。进一步用式(24) 的方法对边的权重进行调整时，网络层数的变化情况如图 6a所示，横坐标为边权调整因子$ \alpha $，纵坐标为含权H指数收敛后网络的层数，$ \alpha $为0时等价于无权网络，为1时等价于原含权网络。此外，本文还考察了$ {{H}^{w}} $指数的阶数对网络层数的影响，如图 6b和图 6c所示，横坐标为$ {{H}^{w}} $指数的不同阶数，纵坐标为对应阶数下的网络层数，结果发现含权$ {{H}^{w}} $指数在挖掘重要节点的准确性(如图 4所示)和分辨率上均优于无权H指数。

本文分别按照节点的强度，含权$ {{H}^{w}} $指数，含权核数大小对城市进行排序，如表 5所示(以核数为主序列)。网络中相同颜色的城市含权核数相同。进一步，又拿出出向强度排名前40的城市，比较了它们的出向强度、出向H指数、出向核数这3个指标的排名情况，如图 8所示。横坐标为出向强度排名，纵坐标分别为出向H指数和出向核数排名，虚线表示两对指标排名相同。从表 5和图 8中可以发现泉州、厦门、苏州、沈阳、太原、哈尔滨等城市的出向强度排名与出向H指数和出向核数的排名差异较大，前面3个城市的出向H指数和出向核数排名高于出强度，而后3个城市相反。这说明泉州、厦门、苏州等城市虽然用户总体被转发量(即节点出强度)较少，但实际上位于这些城市的用户的微博影响力(出向H指数与出向核数)却要更高一些；而沈阳、太原、哈尔滨等城市情况相反。

表 5  不同指标的Top30+城市列表

图  8  出度方向上不同指标的比较

为了进一步说明以上结果的原因，将转发厦门、苏州、太原、哈尔滨的微博最多的各自前20个邻居城市分别展示在图 9中。目标城市用五角星表示，其邻居节点的大小表示它自己的出向强度大小，颜色表示它自己的出向核数大小。这些邻居对目标城市的转发量从目标城市左侧沿着顺时针方向依次递减。从图中可以清楚地看到转发厦门、苏州微博最多的这些城市大部分为高影响力的城市，而转发太原、哈尔滨微博最多的这些城市都是影响力较弱的城市。据此，便解释了这些城市出向强度排名与出向H指数排名和出向核数核名存在较大差异的原因，也进一步证明了H指数与核数在刻画城市影响力时具有更高的准确性。

图  9  转发厦门、太原、苏州、哈尔滨微博最多的各自Top20个邻居城市

一个城市的入强度等于这个城市从其他城市转发的微博数之和，代表了这个城市的活跃度，反之，一个城市的出强度等于其他城市从该城市转走的微博数之和，代表了这个城市的影响力——转发该城市微博的邻居城市影响力越大，转发的数量越多，则说明该城市的影响力也越大。

本文进一步对于每个城市的具体转发量按出向和入向进行了分析，最终得出以下结论：

1) 北京、上海、广州、深圳4个城市，无论是它们自身的活跃度(入强度居于前4位)还是对其他城市的影响力都是最高的。具体来说，网络中除了一个孤立节点(三沙市)之外，其他所有城市都至少与北、上、广、深中的一个存在交互；此外，有37个城市从北、上、广、深中的某一个城市转发的微博在其所有转发的微博中占比最高，占所有城市数量的12.8%；有65个城市从北、上、广、深4个城市转发的微博总数高于从其他城市转发的微博数，占所有城市数量的22.5%，且这些城市的平均出强度排名为80.7。

2) 对一个城市而言，与它交互最多的城市是同一省份的另一个城市，这样的城市有255个，占比88%(图 7中也可以看出来)，而这其中与它交互最强的城市是它的省会城市的有229个，在所有城市中占比79.2%。这体现了在线社交媒体具有很强的“局域性”特征。

3) 共有89个城市(均为非省会城市)的省内转发总数大于省外转发总数，他们的平均出强度排名为159，也就是说这89个城市大都是影响力较弱的城市。在所有城市按照各自的出向H指数(或者入向H指数)降序排列的列表中，排名越靠前的城市，上述的“局域性”特征越弱，反之则越强。可以在一定程度上说，一个城市的整体影响力越大，则它“局域性”特征越弱，反之则越强；

4) 无论出向还是入向，所有省会城市以及直辖市的含权H指数的平均出强度排名约为30，且与它们交互最强的城市是非省内城市的占其中三分之一。所以一般而言省会城市的影响力更大，“局域性”特征较弱；非省会城市的影响力较弱，“局域性”特征较强。

之后，本文考察了无权无向H指数和有向含权H指数分别与城市就业人口、城市生产总值之间的相关性，也发现有向含权H指数的相关性要高于无权无向H指数。最后，又参照最新的中国城市等级划分标准^[41]，发现有向含权H指数也比无向无权H指数能更加准确地反映城市的规模划分。

本文首先将H指数这一重要节点挖掘方法拓展到了有向含权网络上，并证明了无论是同步更新还是异步更新，DHC定理在有向含权网络中仍然成立。这为含权网络上的$ k $-壳分解提供了新的计算方法。接着在3个真实网络C. elegans网络、USAir网络和中国城市间微博转发网络上对比分析了含权与不含权两种情况下各指标在识别重要节点方面的表现，并计算了其与WSIR模型仿真结果的相关性，发现含权的各项指标的性能都好于不含权的情况。最后，应用有向含权H指数和核数对中国城市的在线媒体影响力进行排名，识别具有高影响力的城市，并总结了不同城市对于信息转发的偏好特征。