社交网络中结构洞识别研究现状及展望

仝博

（四川大学计算机学院，成都610065）

0 引言

近年来，随着信息技术的高速发展和通讯设备的成本不断下降，推动了如新浪微博、知乎、Facebook、Twitter 等各种社交网络的快速普及。社交网络中用户规模庞大且还是快速增长中，据统计，2018 年全球社交网络用户已经超过31.2 亿且平均每天仍有大约100 万社交网络新增用户。这些社交网络随着用户的快速增长，产生了海量数据并存储起来。社交网络中关系复杂，例如Facebook 拥有超过10 亿用户和1000 亿的好友关系。这些网络中呈现出了社区的特性[1-2]，例如在一个社交网络中，具有同样的兴趣爱好、成长背景、行为习惯的用户更容易成为朋友，形成一个社区。用户在社区中与同社区的用户交流更加频繁，联系更加紧密，而较少地和其他社区的用户交流，即社区中关系紧密，社区间关系稀疏。当信息在社交网络中传播时，社区对信息的传播具有重要的作用。由于同一社区内用户联系更加紧密，那么信息就会在社区内部迅速传播。此外，信息可以通过同时存在于多个社区内的用户，从一个社区传递到另一个社区。

这些同时属于多个社区的用户，在信息传播的过程中充当了桥梁作用的节点被称为结构洞（Structural Holes）[3-4]。在弱关系理论（Weak Tie）的基础上，Burt[3-4]首先提出结构洞的概念，并利用结构洞来解释社会资本的差别起源。不同于只属于一个社区的节点，结构洞节点可以从多个社区中更多和更早地获取信息，并且可以利用这些信息给自己建立竞争优势，从而获得更多的收益。例如，在科研合作网络中，一个社区代表了具有相似研究方向的学者，那些同时身处多个社区的学者更容易结合多个不同研究领域的思想来进行跨学科的创新性工作。在公司职场中，那些和多个部门交流合作的员工，在跨部门协作中更容易获得更高的评价和更快地晋升[4-5]。此外，在社交网络中，当谣言在网络中传播时，我们只需要在关键的结构洞节点进行信息审查，而不必审查所有的信息，即可有效地阻碍谣言信息在网络中的传播。

1 结构洞识别研究现状

最近几年，由于结构洞的广泛的应用前景，识别社交网络中关键的结构洞节点引起了专家学者们的注意。在提出结构洞概念后，Burt 随后又将结构洞理论进一步的扩展[6-7]。随着网络规模的不断扩大，在大规模网络中识别结构洞节点也是异常困难的。学者们付出了诸多的努力，对结构洞有了初步的了解。现在的结构洞识别研究可以分为以下三类。

1.1 基于网络拓扑的结构洞识别研究

Goyal 等人[5]将结构洞识别问题定义为存在于不同节点对之间的最短路径上的节点，当一个节点位于网络中越多的最短路径上，那么该节点的结构洞重要性就越高。由于在网络中寻找所有节点的最短路径是非常消耗时间的，并且当网络规模很大时，消耗的时间更是无法接受，Tang 等人[8]提出只计算顶点所在的长度为2 的最短路径，忽略所有长度超过2 的最短路径。Rezvani 等人[9]提出利用网络平均通信距离来衡量节点结构洞重要性，在网络中一个节点的移除，将会增加某些节点间的通信距离。那么致使网络间平均通信距离增长最多的节点，就是结构洞重要性最大的节点。由于该问题是NP-难的，所以采取贪心算法迭代找出top-k个结构洞。此外，利用节点的有界逆接近中心性和网络中关节点的特殊性质以及改进后的深度优先搜索方法，提出了两种快速且可扩展的线性时间的算法。Xu等人[10]在基于Rezvani 等的基础上，将该问题表示为了一个优化问题，设计出了创新的过滤方法，尽早地过滤出不太可能的节点，能够快速地估计出最优解的上下界，将该问题可以推广到大规模网络中。在真实数据集中的大量实验上可以表明，该方法可以准确地捕捉到结构洞的特征，并且计算迅速。Zhang 等人[11]在符号网络中考虑到用户间的信任问题，在有符号社交网络中的信息传播受链接极性和用户位置的影响，在传播过程中识别可信的联系和不可信的联系，进而识别出可信的结构洞。

基于网络拓扑的结构洞识别研究的不足在于网络中节点与节点之间、节点与社区之间、社区与社区之间的连边仅表示两者有相互联系的可能，不代表一定会产生信息交换。那么仅通过网络拓扑方法识别出的结构洞未必能带来实际的收益。为了确保识别出的结构洞能够带来收益，不仅需要在网络拓扑上能够连接多个社区，而且还需要和这些社区建立并保持稳定可信的联系。

1.2 基于社区的结构洞识别研究

Lou 等人[12]假设社交网络中所有的社区都是给定的，提出了第一个社交网络中结构洞识别模型。他们模型的目标是利用一个效用函数来最大化的衡量结构洞节点跨越社区的程度。效用函数是在网络中找到一组节点，删除这些节点会使得网络中不同的社区之间的边的数量得到最大的减少。为了实现该效用函数，Lou等人开发了两个实例模型。对于第一个实例模型，给出了精确的算法来求解，并证明了该算法的收敛性。对于第二个实例模型，证明了其最优化是NP-难的，并设计了一个可证明的近似保证的有效算法。除此之外，Lou等人在Twitter 的实验表明，在Twitter 网络中1%的结构洞节点控制了25%的信息传播，进一步说明结构洞在社交网络中的重要性。He 等人[13]提出一种新的谐波模块化（Harmonic Modularity）方法，只利用网络拓扑信息，即可同时识别出社区和结构洞节点。假设一个节点只属于一个社区，利用调和函数来衡量社区结构的平滑程度并获得社区指标。然后重点研究连接多个社区的节点在社区间交互作用，来判断是否是结构洞。

基于社区的结构洞识别研究的不足在于社区在网络中往往是未知的，利用不同的社区发现的算法会得到不同的社区结果。所以Lou 等人[12]识别出的结构洞严重依赖于找到的社区的质量。He 等人[13]提出的方法，假定一个节点只能属于一个社区，但在现实网络中，一个节点往往属于多个社区。

1.3 基于网络形成的结构洞研究

Goyal 等人[5]提出了一个网络形成模型，在货物交易或者信息交换中，当成员之间产生关联，交换才能发生，如果是直接交换，则收益两者平分。如果是通过中介进行间接交换，则包括中介在内，一起平分收益，一个节点可以充当多个节点之间的中介，那么成员之间将倾向于更短的路径。在没有链路容量限制的条件下，会形成一个星型网络。然而，这显然和实际网络不同，为此Kleinberg 等人[14]借鉴博弈论中的方法提出一个模型来刻画充当结构洞的节点收益。当网络中原本不相连的各方，为了收益，网络中的个体有动机形成连接。Kleinberg 等人将收益建模为连接不相邻节点的好处和维护连接成本之间的权衡。通过理论分析和计算实验，该收益与经过此节点两跳的路径数量成正比。此外，即使在相同的环境下，个体也会不断分化，占据不同的社会阶层，并获得不同的回报。

基于网络形成的结构洞研究的不足是需要对很多参数进行多次的调节才能使模型达到最优，这只能在小型网络中实现，在大规模的网络中是很难实现的。

2 结构洞识别研究总结和发展趋势

经过对上述社交网络中结构洞识别研究的分析，将结构洞识别分为三类：基于网络拓扑的结构洞识别研究、基于社区的结构洞识别研究和基于网络形成的结构洞研究。基于网络拓扑的结构洞识别研究最为常见，类似于介数中心性和接近中心性，仅根据节点在网络拓扑中的位置，来判断是否为结构洞。这种方法便于理解，但可扩展性差，在大规模网络中需要耗费大量的时间计算。只能采取启发式算法和近似算法来加速计算。基于社区的结构洞识别研究和基于网络形成的结构洞研究局限更多，不仅不适合在大规模网络中运行，而且获得结果并不稳定。通过网络拓扑来识别的结构洞的过程中，连接多个社区的节点比只在一个社区内的节点是更好的结构洞，因为该节点的移除将会显著增加社区间的节点距离。连接大型社区的节点比连接较小型社区的节点是更好地结构洞，因为其移除将导致网络中更多节点的断开。连接多个社区的节点比连接少数社区的节点是更好的结构洞，因为它的移除将增加更多社区间的距离。由此可见，目前在社交网络中结构洞识别研究仍处于初级阶段，对结构洞的衡量还处于定性研究而非定量研究。

介于目前结构洞识别研究的不足，未来在社交网络中结构洞识别研究不仅要考虑网络拓扑，还需要考虑节点间关系强度和信息是否可靠。只有保持稳定的联系才能让结构洞产生收益。目前对结构洞的定性研究过于粗糙，需要精确地衡量节点结构洞重要性。只有对结构洞节点精确定义和准确计算重要性才能加深对结构洞的认识，产生更多更有意义的应用。此外，随着网络规模的不断迅速扩大，所以需要设计出适合于大规模网络中的快速、有效且可扩展的识别算法。