导航菜单
首页 > 管理学论文 > 情报论文 » 正文

KiC:一种结合“结构洞”约束值与K壳分解的社交网络关键节点识别算法

李钢 王聿达 崔蓉




收稿日期:2020-03-19

基金项目:2019年国家社会科学基金项目“智能时代的意识形态风险防范研究”(项目编号:19BKS098)。

作者简介:李钢(1968-),男,教授,博士,研究方向:网络社会管理、网络与公共信息管理。崔蓉(1989-),女,博士研究生,研究方向:复杂网络理论与应用。

通讯作者:王聿达(1989-),男,博士研究生,研究方向:复杂网络与信息传播、数据挖掘。

摘  要:[目的/意义]在大规模社交网络中快速搜索关键节点对于舆情的引导和控制具有重要意义。[方法/过程]本文提出一种适用于社交网络的局部中心性关键节点识别算法,该方法综合评估了节点的K壳、自身的聚集特性以及邻居的扩散特性和节点自身传播状态,同时体现了节点在空间上的网络位置和邻居的拓扑结构以及在时间上演化特征,评价指标更加全面高效。[结果/结论]实验结果表明,该方法识别的关键节点对网络鲁棒性的影响与介数中心性接近,但计算仅基于节点局部信息,时间复杂度低。剔除这些节点后网络的连通性受到较大影响,网络聚类系数降低,平均路径长度增加。同时,利用SIR传播模型模拟验证,以该算法识别的关键节点为初始传播源可提升信息传播范围和平均传播速度。

关键词:复杂网络;关键节点;K壳;约束系数;舆情传播

DOI:10.3969/j.issn.1008-0821.2020.12.003

〔中图分类号〕G201  〔文献标识码〕A  〔文章编号〕1008-0821(2020)12-0027-09

KiC:An Extended K-shell Decomposition Based on

Improved Network Constraint Coefficient

Li Gang  Wang Yuda*  Cui Rong

(School of Economics and Management,Beijing University of Posts and Telecommunications,

Beijing 100876,China)

Abstract:[Purpose/Significance]Evaluating vital nodes rapidly in large-scale social networks is of great significance for the control of information dissemination.[Method/Process]In this paper,we proposed a local centrality vital node identification algorithm.The method comprehensively evaluated the K-shell of a node,its own clustering characteristics,the diffusion characteristics of its neighbors and propagation state of nodes,which simultaneously reflected the network location of the nodes,the topology of the neighbors and evolutionary features in time.The evaluation indicators were more comprehensive and efficient.[Result/Conclusion]The experimental results showed that the vital nodes identified by this method had a greater impact on the robustness of the network.After removing these nodes,the connectivity of the network was greatly affected,the network clustering coefficient was reduced,and the average path length was increased.Meanwhile,SIR model was used to evaluate the ability to spread nodes.Simulations of five real networks showed that our proposed method could improve the scope and average speed of information dissemination.

Key words:complex network;vital node;K-shell;constraint coefficient;information dissemination

近年来,对复杂网络的研究已成为许多领域关注的热点。几乎所有的复杂系统都可以表示为网络,网络的顶点代表实体,而边则表示实体间的关系与相互作用。网络中存在对提高系统鲁棒性意义重大的节点,这些节点一般数量非常少,但其影响却可以快速波及网络中大部分节点。例如:在社交网络中,对少量最重要节点的删除能够有效控制信息的传播。可见重要节点对网络的动力学行为有着巨大的影响。因此,在大规模社交网络中快速搜索关键节点意义重大。

識别网络中的关键节点受到物理、数学、计算机和管理科学等多学科的广泛关注,使其成为各个学科所共同关注的交叉科学,各学科研究人员根据所关注的具体问题,提出了众多重要节点排序方法。利用节点度中心性来判断节点的重要性是最简单的方法[1],该方法认为,一个节点的度越大,影响力就越大,其缺点是没有全局角度考虑节点所处的网络位置和邻居的拓扑结构,在很多情况下不够精确。介数中心性[2]和接近度中心性[3]从全局出发,分别考虑节点到达其余节点的最短路径数目,节点与其他所有节点最短距离的平均值,此类方法在评估节点重要性方面有了明显的效果,但由于需要获得整个网络的拓扑特征,导致时间复杂度高,不适用于当前社交网络关键节点的识别。为平衡识别效果和时间复杂度,Chen D等[4]提出了半局部中心性,半局部中心性使用了节点的四阶邻居的度作为判断依据,相较介数中心性该算法消耗非常少的计算时间,然而该算法只考虑了邻居节点信息,忽略了节点在全局网络中所处的位置。Burt R S等[5-7]基于经典社会学中的“结构洞”理论,用网络约束系数来衡量节点形成结构洞时所受到的约束,该方法利用了局部属性评价节点的重要性,具有较好的时间复杂度和计算精度,然而,该方案没有考虑邻居节点与其余节点相连的拓扑结构对节点的影响。

Kitsak M等[8]依据网络中节点处于网络的核心位置往往有较高影响力的思想,提出用K壳分解法确定网络中节点的位置,在分析大规模网络的关键节点等方面具有良好的时间复杂度。然而此方法也有一定局限性,如未考虑删除节点等。Zeng A等[9]提出了混合度分解算法,混合度以网络中剩下的邻居节点以及删除的邻居节点的混合度进行K壳计算,此方法较好地提高了节点区分度。王环等[10]提出了点权分解算法,该算法综合考虑了节点的全局指标加权核值以及节点的局部指标度数,真实网络的实验结果表明,此算法在关键节点识别中可取得较好的效果。

综上所述,要准确识别社交网络环境下节点的传播能力,不但要考虑节点所处的网络位置和邻居的拓扑结构,还需考虑计算的时间复杂度,同时由于网络舆情时间特性明显,节点时序特性也是识别关键节点的重要因素。K壳分解算法可以高效准确地识别节点在网络中的位置,然而当前的K壳分解及其优化算法还存在如下局限性:第一,没有考虑邻居之间的拓扑关系,不能在计算中反映邻居节点间的相互作用。第二,缺乏“桥”节点的识别,在社交网络中存在着一些度很小但是很重要的“桥接”节点,它们在信息的传递中担任重要的角色[11]。第三,识别会受到网络中类核(Core-like)的影响[12],这些类核结构里的节点对信息或者病毒的扩散能力通常较弱,但却会被识别为处在网络核心位置。第四,排序结果太过粗粒度,节点的区分度不大,尤其是在树形结构网络和无标度网络中。第五,未考虑节点在不同时间自身的传播属性。因此,本文从以上5个角度出发,通过在K壳分解原理的基础上,利用节点及其邻居的聚集性和扩散性,并结合节点传播状态的时序变化优化计算节点结构洞约束值,以K壳值与结构洞约束值联合评价作为节点重要性指标。通过在真实的网络中进行仿真验证,结果表明,该算法识别的关键节点对于网络鲁棒性的影响较大,从这些关键节点传入的信息能够在网络中更快地传播,并且传播范围更广。

1  基础理论

1.1  网络定义

对于一个无向无权网络,可以通过G=(V,E)进行表示,其中V表示网络中节点的集合,E是网络边的集合。eij用于表示节点i和节点j之间边的关系,如果节点i与节点j有边,则eij=1,否则eij=0。节点i的度表示为ki。为便于理论分析和实验验证,本文所用到的网络为静态网络,即网络中的节点数量及节点间关系不会随时间发生变化。

1.2  K壳分解算法

K壳分解算法可用于确定网络中节点的位置。其核心思想是根据节点度数递归地删除网络中的节点,分解过程如下:网络中如果存在度为1的节点,从度中心性的角度看它们就是最不重要的节点,删除这些节点及其相连的边,剩下的网络中会新出现一些度为1的节点,再将这些度为1的节点去掉,循環直至所剩的网络中没有度为1的节点为止,记这些删除的节点称为1。按上述方法继续剥壳,重复这些操作直到网络中没有节点为止。图1为经K壳算法分解后的网络示意图,其中1~3为3壳节点,5为2壳节点,6~14为1壳节点。

1.3  结构洞理论及网络约束值

社会学理论中,结构洞存在于社会网络中没有冗余连接的两个个体之间,洞两边的个体可以带来累加的网络收益[5]。从复杂网络的角度来看,结构洞特征强的两个节点之间的边在网络中能够获得更多竞争优势,是约束信息传播的关键边。Burt R S首先提出了用约束系数来衡量网络节点受到结构洞的约束,其表达式如下:

Ci=∑j∈τ(i)pij+∑qpiqpqj2, q≠i,j(1)

其中pij表示节点i为维持与节点j的邻居关系所投入的精力占总精力的比例(也就是度),piq和pqj分别是节点i、j与共同邻居q维持关系投入的精力占其总精力的比例。约束系数综合考虑了节点的邻居数目以及邻居之间连接的紧密程度(邻居间的闭合程度),节点邻居数量越少且与其邻居间的闭合程度越高,越不利于信息传播。

1.4  SIR疾病传播模型

疾病传播是社交网络上信息交换并可能传播的一种抽象表现形式,其传播是一个非常复杂的问题,结果依赖于传播过程中的具体情况。由于存在着这种相似性,学术界关于谣言传播模型的研究大多来源于经典的疾病传播模型。疾病传播模型最初是Kermack[13]在研究黑死病时提出的SIR模型。该模型描述了有些疾病的传播是具有免疫能力的,人被感染后就不会再次被感染。SIR模型将疾病流行范围内的人群分成易感者S,感染者I和免疫者R,人群中每个个体的时序状态在3类之间转换。在疾病演进过程中,处于感染态的节点以概率β向相邻的易感节点进行传播,同时每个感染节点则以概率γ治愈或死亡。

SIR模型适用于典型的社交网络舆情传播场景,针对一条信息,社交网络中的人群可分为不知情者S、知情并传播者I和知情不传播者R,通过SIR模型可动态描述信息在社交网络中的演进过程。

2  社交网络关键节点识别改进算法及算法论证

2.1  理论及算法

从上述相关理论分析可以看到,K壳分解算法可以高效地识别出节点所处的网络位置,“结构洞”约束值可从节点局部拓扑分析邻居节点之间的相互作用,节点传播状态可以从时间演进角度对舆情传播中的节点重要性进行评估。本文所提出的改进算法(Extended K-shell Based on Improved Network Constraint)综合考虑了K壳分解算法、优化后的“结构洞”约束值计算方法以及结合了节点传播状态的时序特征,更适用于社交网络的关键节点识别,算法定义如下:

KiCi(t)=ksi·ICi(t)(2)

KiCi(t)表示节点i在t时刻的KiC系数,ksi是节点i的K壳值,ICi(t)是本文优化后的节点i在t时刻的约束系数。从式(2)可以看出,KiC是t时刻由K壳值与约束系数点乘得出,因此该值既能够体现出节点的网络位置,又能够结合邻居的拓扑结构和时间维度上的传播状态。网络约束系数(Improved Constraint)的表达式为:

ICi(t)=TFi(t)·∑j∈τiTFj(t)·pij+∑k∈τjTFk(t)·qij·qjk, k≠i,j(3)

在Burt R S提出的算法中,通过节点的邻居数目(度)以及邻居之间连接的紧密程度(邻居之间的闭合程度)计算约束系数来识别关键节点,该算法应用在社交网络中存在3个问题:一是用节点度的大小来衡量节点是否处于社团的局部中心性不够全面;二是仅使用一阶邻居的闭合情况无法准确发现一些重要的“桥”节点;三是只考虑了网络空间特性,未考虑舆情演化的时间特性。因此,本文改进了约束系数的计算方式,通过边的聚集性代替度表示节点的局部中心性,通过边的二阶扩散性代替邻居闭合程度解决了“桥”节点识别不准的问题,通过节点的当前传播状态还原不同时序下节点的真实重要性。

式(3)中τi代表了节点i的邻居节点的集合,pij定义为边eij的聚集系数,qij定义为边eij的扩散系数,TFi(t)表示节点的时间演化因子(Time Evolution Factor)。其中:

pij={k∶k∈τ(i,j)\i,j,Δijk∈ΔG}τ(i,j)\i,j(4)

qij=∑k∈τ(i,j)\i,jθkτ(i,j)\i,j(5)

TFi(t)=1, t时刻i状态为S

1+β, t时刻i状态为I, β为传播概率

0, t时刻i状态为R(6)

1)边eij的聚集特性[14-16]可通过节点i和j的邻居节点与eij构成的三角形的占比来表示,无法构成三角形的邻居节点占比表示边eij的聚集特性。如图2所示,当信息从节点i经过边eij传播时,可通过扩散特性中的节点2和节点3将信息传播到网络中的其他节点,也可通过聚类特性中的节点1回传至节点j,因此边的聚类与扩散特性通过点的二阶邻居信息,有效地描述了对信息传播的影响作用。

2)时间演进因子TFi(t)表示在舆情演进过程中,i节点在t时刻所处的不同状态对节点约束系数正向促进或负向抑制的作用。本文认为S状态为节点的基础状态,在某时刻不知情状态(S状态)的节点将不会对约束系数起到作用;当节点处于I状态时,由于该节点当前具有传播性,因此会比网络空间中的其他节点更加重要,此时与该节点重要性相关的约束系数会加强;当节点处于R状态时,该节点当前及之后的时间将不会对信息进行传播,因此从舆情传播的角度来看该节点重要性降为0。

收藏此文 赞一个 ( ) 打赏本站

如果本文对您有所帮助请打赏本站

  • 打赏方法如下:
  • 支付宝打赏
    支付宝扫描打赏
    微信打赏
    微信扫描打赏
留言与评论(共有 0 条评论)
   
验证码:
二维码