基于博弈的有向时序网络两阶段社区发现算法

2024-02-29董继远刘九强

科技和产业 2024年3期

董继远, 刘九强

(贵州财经大学大数据统计学院, 贵阳 550000)

近年来,研究人员对复杂网络结构进行了很多研究,反应连边紧密程度的社区结构也在其中。在经典的理解中,社区结构具有内部集群关系密集而不同社区之间关系稀疏的特征。目前有很多基于静态网络的社区划分算法,有通过矩阵计算的方法[1],通过监督式学习如标签传播的方法[2-3]和基于节点关键程度的方法[4],以及通过图嵌入进行社区发现的算法[5]。

然而,大多数真实世界的图都是动态的,因为它们随着时间的推移而变化,新数据产生了需要合并到现有图中的新顶点和边,从而使网络结构发生相应的变化。传统的静态图分析方法在满足这一需求方面面临着重大限制[6]。使用传统的静态网络社区探索算法分析动态网络社区时,往往会忽视节点在时间维度上的关联,从而对社区结构的演化分析出现偏差。

现在学者已经提出了一些时序网络社区发现算法。例如,基于谱聚类的动态社区发现算法(spectral clustering based dynamic community discovery algorithm, SC-DCDA)[7];基于层次聚类算法作为初始时间段内动态时序网络的社区划分算法[8];Lin等[9]提出的关于节点历史信息的社区发现算法;He和Chen[10]利用独立时空的方式进行时序网络上的社区划分与演化行为。

随着贸易全球化的发展,复杂网络模型在贸易分析中展现出很多优势,不少学者进行了相关的应用与研究。例如,谭丹和杨曼羚[11]通过构建网络对亚太14国间机电产品贸易进行研究;蒋培祥和董志良[12]通过网络模型对常规能源贸易网络进行分析研究;何健佳和郑添元[13]建立了“负载-容量”模型发掘汽车供应链网络中关节节点。

本文将有向动态网络社区划分任务分为两个步骤:第1个阶段通过节点距离、源节点影响力、目标节点影响力以及节点分解度4个矩阵,确定节点在网络中的重要程度;第2阶段确定社区划分的核心节点,接着分别令核心节点作为源头节点进行级联传播,其他节点通过博弈收益值确定与各个领导节点的跟随度,最后选择跟随度最高的节点所领导的社区。使用Huo等[14]编制的2015—2019年共5年的全球区域投入产出表构建全球时序贸易网络,通过两阶段社区发现算法,探索动态网络中的关键节点和社区结构。

1 理论基础

1.1 有向加权网络模型

图论和矩阵法是社会网络分析中常用的数据表示方式。庞大的系统可以映射到复杂网络中,系统中的元素视为网络中的节点,系统中元素之间的关联视为网络中的连边。根据研究问题的需要连边可以选择有向与无向、赋权与不赋权。

一般的,有向复杂网络可以由G=(N,E,W)表示。其中:N={v1,v2,…vn}表示网络的节点集;E={|vi,vj∈V,i≠j}表示网络中的节点连边;表示节点vi指向节点vj的有向边;W={w(vi,vj)|vi,vj∈V,i≠j}表示图中边e的权重。

为方便计算,用Amxm表示网络G的邻接矩阵,其中m=|V|表示图的节点数,A中元素aij=w(vi,vj),在无权图中,w(vi,vj)取1或0,在加权图中,aij=w(vi,vj)表示边e的权重。

(1)

通过邻接矩阵的n次幂可以得到节点对间长度为n的路径数量。

现实生活中,网络中的节点与边都是随时间发生变化的,因此按时间段选取结点并在这些时间节点对不停变化的某个网络进行快照处理就构建出了时序网络模型,用G={G1,G2,G3,…}来表示,其中Gt={Nt,Et,Wt}表示在t时刻的切片网络,Nt,Et,Wt分别代表t时刻的节点集、边集以及连边权重的集合,用At表示Gt对应的邻接矩阵。

1.2 独立级联传播模型

独立级联模型(independent cascade)[15]研究信息在网络中的传播最大化。独立级联模型是一种经典的扩散模型,该模型假定网络中每个节点根据是否受信息影响而处于激发B*或者非激发B两种状态。处于非激发的节点会受其邻居节点的影响转为激发状态,同时激发状态是不可逆的,即处于激发状态的节点不会转变为非激发状态。在传播的初期只有设定的节点处于激发状态,其余节点均处于非激发状态,当节点Nodei在时刻a转变为激发状态,那么它将在a+1时刻尝试激发它的邻居节点,传播过程将在网络中没有新的节点会被激发时停止。

表1 节点收益矩阵

2 两阶段动态有向网络社区发现算法

提出一种两阶段的动态有向网络社区发现算法,该算法主要包括两个部分:①通过构建网络邻接矩阵,计算节点的重要程度,挖掘出网络中的局部核心节点与全局核心节点;②将网络中的局部核心节点作为社区中心节点,让每个核心节点作为源头向其余节点进行标签传播,将每个跟随者节点通过与其邻居间的协调博弈进行策略选择(更改或不更改当前标签)得到对当前核心节点的关联度,在所有核心节点进行标签传播结束后,各个跟随者节点选择加入关联度最高的社区,得到最终的社区划分结果。

2.1 阶段1:节点关键程度

定义1：节点交叉强度。在有向网络中,某个节点的交叉强度由该节点的入强度与出强度正相关,可以用式(2)表示,通过这个节点同社区中的负邻居数与不同社区中的负邻居数的和来确定。

(2)

式中:λ为一个介于0与1的常数,可以根据研究的需求确定,当其大于0.5时,表示入强度对节点重要性的影响更大,若小于0.5则表示出强度对节点的重要性影响更大;wpi为有向边e的权重;wiq为有向边e的权重;Neiin、Neiout分别为节点i的入邻居所构成的集合与出邻居构成的集合。

为了发现节点的重要性,引用王雨和郭进利[16]的方法,构建效率矩阵E、以源节点为中心的影响力矩阵L和以目标节点为中心的影响力矩阵T。

(1)效率矩阵E,其中元素Eij=1/dij,为从节点i出发至节点j最短路径长度的倒数。

在社区划分任务中,具有较高重要性的节点往往处于相同的社区中,为了发现有效的社区发现核心节点,受Shahriari和Klamma[17]在符号网络社区划分中基于混合度与信息扩散的算法(signed degree mixing and information diffusion, SDMID)的启发,引入了节点分解度矩阵D,其中元素

Dij=p|degin(i)-degin(j)|+

(1-p)|degout(i)-degout(j)|

(3)

式中:p为一个介于0与1的常数,可以根据研究的需求确定,本文中取值为0.5;degin(i)、degout(i)分别为节点i的入度与出度。

结合节点分解度矩阵与前面3个矩阵进行赋权加总,构建影响力-分解度矩阵,采用(0,1,2)三标度法对4个矩阵进行两两比较,比较矩阵见表2,其中,bij取值为0时表示i不如j重要,取值为1时表示i与j同等重要,当取值为2时则表示i比j更重要。接着利用极差法将比较矩阵转化为判断矩阵,并进行一致性检验得到矩阵权重。

比较矩阵的构建考虑到,效率矩阵E通过距离直接体现了节点间的亲疏关系,而且在比较节点间的影响比例值大小时,首先要考虑的是两节点之间的距离,然后再去考虑当距离相同时,最短路径数对比例值的影响。因此可认为效率矩阵E比其他两个矩阵更加重要;而矩阵L和T都是基于最短路径数来研究节点间的相互影响的,区别仅在于侧重点不同,L考虑到影响节点对网络中所有待评估节点的影响,T考虑到网络中所有影响节点对待评估节点的影响,这两种情况都需要考虑在内,无法比较其好坏,因此认为这两个矩阵具有同等的重要性。在社区划分的任务中,关键值较高的节点相对集中,会划分于同一社区当中,因此为了选取相对分散的聚类核心节点,节点的分解度矩阵D较其余3个矩阵赋予更高的权重。

经过一致性检验,4个矩阵权重分别为wE=2/9,wT=1/18,wL=1/18,wD=2/2,这样得到影响力矩阵为M=2/9E+1/18T+1/18L+2/3D,其中元素mij表示节点i对节点j的影响力。

表2 比较矩阵

以综合影响力矩阵为基础结合节点交叉强度,最终节点的重要度为

(4)

2.2 阶段2:节点社区发现

在确定节点重要性后,基于级联模型发现网络中的社区结构。为了设置级联行为的发起者,定义了局部中心节点。

数据和流程是销售团队管理中不能忽视的两个大问题。本书主要讲销售团队建设中如何利用好数据分析和抓好流程来强化团队管理，提升销售团队的业绩。上篇主要讲如何抓好流程的规范与管理来提升销售团队的整体业绩，轻松复制销售精英，让团队中的每个销售员都可以成为销售精英；下篇主要讲如何做好数据管理的分析与应用来帮助团队管理者掌握团队的动态，及时发现团队的弱项和问题，找到问题的根源，激发销售团队中的各个员工的内动力，带领整个销售团队开创更高的业绩。作者李庆南，广誉恒集团董事长，高级营销策划师。

定义2：局部中心节点。当一个节点的领导度高于其所有邻居节点的领导度时,则将其定义为局部中心节点。

在时序网络建模中,第t期节点的演化行为会收到前期经验的影响,因此节点在决策过程中,不仅仅要考虑节点的收益值,还需要总结前期的经验。为此,当第t-1期节点Nodei为局部中心节点时,第t期它的领导度只需要高于80%邻居的领导度时,则将其设定为第t期的局部中心节点。

在获得局部中心节点集合后,依次令领导节点作为信息传播的源节点,其他节点设置为跟随者节点,在传播的开始将该领导节点的策略选择设定为B*即激发状态,其他节点的策略选择设定为未激发状态B,接着按随机次序对跟随着节点进行信息传播,当转变策略收益值大于当前的阈值时,便依一定概率转变为激发状态B*,并更新对领导节点l的归属度Cli,在所有领导节点迭代结束后,跟随者节点将最终选择接入归属度最大的一个或多个局部中心节点社区。在所有迭代结束后,使用余弦相似度对相似度较高的社区进行合并操作。算法流程见算法1。

算法1:基于级联行为博弈的社区发现算法

Input: Network G=(V,E,W); Leader nodes listLLOutput: C1forl in LLdo2 l’s behavior ← B*3 threshold ← 0.54 followerlist ← V-{l}5 forf in followerlistdo6f’s behavior ← B7randomly generate node sequence Srl8for i in Srldo9ifpayoff(i) > thresholdthen10i’s behavior ← B*11CMil ← 1/(t**2)12update threshold

算法中阈值按二分搜索法逐渐变化,搜索上界Tu,下界Tl的初始值分别设置为1和0,阈值threshold=(Tu+Tl)/2,如果所有节点都分配给至少一个社区,则减小上限,否则增大下限。在算法中,将迭代次数设置为20。

3 实证分析

3.1 数据来源及预处理

引用Huo等[14]编制的2015—2019年共5年的全球区域投入产出表,每张区域投入产出表由245个经济体的135个部门构成,表的架构如图1所示。

图1 全球区域投入产出表分解示意图

3.2 评价措施

引入模块度[18]和标准化互信息[19]评估社区划分的效果。

模块度QG的计算方法为

(5)

式中:wij为节点i指向j的连边权重;wi为以节点i为源节点的总权重;wj为以节点j为目标节点的总权重;δ(Ci,Cj)为一个表现节点i与j是否在同一社区的示性函数,当两个节点处于同一个社区时取值为1,否则取值为0。模块度的数值表现出社区之间连边紧密、连边稀疏的程度,模块度越高表明划分结果越理想。

最大标准化互信息(NMImax)[19]能够表示重叠社团结构的相似度,取值为0～1,取值越大表明社团结构的相似程度越高,计算公式为

(6)

式中:H(X)和H(Y)分别为X与Y的信息熵;I(X,Y)为X与Y的交互信息。

3.3 基于MRIO(国际多区域投入产出表)的动态贸易网络构建

提取出区域投入产出表的中间流量矩阵,首先计算经济体A与经济体B之间的贸易流xAB,空间自相关理论认为距离越远对对方的依赖程度越低,据此构建基于效率的影响力矩阵,矩阵中元素rAB表示经济体A与B之间无权网络距离的倒数,当rAB=0时表示A经济体向B经济体没有任何直接或间接的贸易关系,当rAB=1时表示A经济体向B经济体存在直接的贸易流关系,当0

(7)

(8)

式中:当k取全部135个部门时,X为国际贸易流量矩阵;当k按照不同需求选取不同的部门时,便可以构成国际间不同部门的贸易矩阵。

提取出5个贸易矩阵后,以1年为时间结点,各个经济体为网络节点,经济体之间的流量作为加权有向边,便可以构成一个关于国际贸易的时序有向加权网络。但是直接利用得到的矩阵构建网络,连线太多不利于进行网络特征分析,因此,根据经济体A总投入的均值作为阈值,若经济体A对于经济体B的贸易流出大于阈值t,则定义经济体A对经济体B有贸易流出,否则经济体A对经济体B没有有贸易流出。这样最终得到的贸易网络可以表示为

(10)

式中:tr为贸易网络的邻接矩阵。

得到的加权贸易网络基本信息见表3。5年间网络中节点数均为234,相较于整张投入产出表,有11个经济体因为总进出口量不高或编制过程中经济数据获取的原因而未能在贸易网络中出现,但是这些经济体占总体不到5%,没有这些节点对整体网络分析的影响不大。总体来说,5年中连边数的变化不大,连边的平均权重大致呈现逐年增加的趋势,也反映出随着时间变化,经济体之间的贸易是逐渐增加的。

表3 2015—2019 年贸易网络基本信息

3.4 区域间贸易关键节点

通过实验,网络中的节点关键程度的前20的经济体见表4,其中每年前20个最关键的节点中都有法国、美国、中国、印度、土耳其、意大利、加拿大、日本、荷兰、新加坡、英国、瑞士、俄罗斯、比利时、韩国、德国和西班牙这17个经济体,可以得出在国际贸易网络中这些网络承担着比较关键的所用。实际上,这些经济体在国际贸易的进口、出口以及中转过程中分别扮演着不同的重要角色,对世界贸易网络的形成起着不可或缺的作用。