当前社会正处于信息化浪潮的新阶段,大量数据时刻生成并可建模为大规模网络.快速、准确地识别这些网络数据潜在的聚类结构,是商家定位用户群体,制定精准营销策略的依据.网络中可能存在社区结构^[1-2]、星型结构或层次结构,甚至同时存在多种结构.关于这些网络的先验信息很少,成为人们发现网络潜在结构的难点.FORTUNATO^[2]采用社区发现算法识别网络中类内链接紧密和类间链接稀疏的结构,但当网络中可能不存在这种结构时,该算法不能发现真实的网络聚类模式.一些网络结构发现方法可识别网络的多类型潜在聚类模式,如基于随机块模型的算法^[3],但此类方法复杂度高,不能处理大规模网络.基于混合模型的网络结构发现算法——在线变分期望最大(online variational expectation maximization, onlineVEM)算法^[1],可发现大规模网络的多类型聚类结构,但其结果受初始参数影响,准确性和稳定性还有待提升.

近年来出现的半监督社区发现方法,利用先验信息提高了网络社区发现的准确率^[4-13].根据半监督社区发现算法使用先验的形式,将现有方法分为基于节点先验的方法^[4-6]和基于约束对先验的方法^[7-13].后者因先验信息容易获得而较为流行.根据约束对先验信息的获得方式,将现有算法大致分为2类:① 随机选择约束对标记^[7-11],如YANG等^[9]提出基于非负矩阵分解(nonnegative matrix factorization, NMF)的超网络半监督社区发现算法(SuperNMF),随机选择约束对先验标记,利用约束先验改变网络的邻接矩阵,采用传统的社区发现方法获取网络节点聚类.② 基于主动学习策略选择约束对进行人工标记,以较少的先验实现算法性能较大程度提升^[12-13].如YANG等^[13]提出迭代主动半监督社区发现算法ALISE(active link selection),主动选择最不确定的节点对进行人工标记,利用已标记链接重构网络拓扑结构.这些半监督社区发现算法主要发现网络中的社区结构,如果网络中不存在这种社区结构,或者存在其他类型结构,此类算法无效,且这些方法主要针对中小规模网络.

综合大规模在线网络结构发现方法、半监督社区发现方法和主动半监督聚类方法研究成果可知,通过主动选择信息量大的节点,利用约束对先验,对其进行类别标记,可用较少的代价获得高质量的先验,使算法不仅能更准确地识别网络的各种聚类模式,还能高效处理大规模网络.为此,本研究基于onlineVEM算法,提出一种用于大规模网络结构发现的基于迭代框架的主动半监督在线变分期望最大(active semi-supervised onlineVEM, ASonlineVEM)算法.算法包含初始化阶段和在线算法迭代阶段.初始化阶段主动选择代表节点,并基于代表节点初始化模型参数.在线算法迭代阶段每次迭代执行3个任务:① 运行onlineVEM算法; ② 不确定节点选择; ③ 模型参数更新.在不同网络数据上与同类算法进行比对,结果表明,ASonlineVEM算法可利用少量先验信息较大程度提高网络结构发现的准确率.

onlineVEM算法是针对大规模网络结构发现设计的在线算法.算法先随机选择网络中部分节点构成子网络,利用期望最大(expectation maximization, EM)算法估计节点的类隶属度及混合模型参数,再迭代估计网络的剩余节点隶属度及模型参数.估计方法为:

迭代过程中选择1个节点i, 它属于类k的概率γ_ik即为该节点的隶属度

γ_ik=(π_k∏_jθ^<sup>A_ijkj)/(∑_kπ_k∏_jθ^<sup>A_ijkj)(1)

其中, θ^<sup>A_ijkj为类k的节点链接到节点j的概率, A_ij为初始网络的邻接矩阵 A的元素, A_ij=0或1; π_k为所有节点属于k的概率.

利用当前节点的隶属度更新模型参数,则第t+1 次迭代时所有节点属于类k的概率为

π^t+1_k=1/(n+1)N^t+1_k(2)

其中, N^t+1_k为第t+1次迭代时节点属于类k的隶属度和, N^t+1_k=N^t_k+γ_(t+1),k.

第t+1次迭代时, 类k节点链接到节点 j的概率为

θ^t+1_kj=(H^t+1_kj)/(G^t+1_k)(3)

其中, H^t+1_kj为第t+1次迭代类k节点链接到j的概率和, H^t+1_kj=H^t_kj+γ_(t+1),kA_ij; G^t+1_k为第t+1次迭代类k中节点链接到所有节点的概率和, G^t+1_k=G^t_k+γ_(t+1),kdeg_t+1, deg_t+1为第t+1次节点的度.

onlineVEM算法每次迭代随机选择1个节点,利用式(1)计算其隶属度,再利用式(2)和式(3)更新模型参数,迭代此过程直到算法准确率或迭代次数达到阈值(准确率阈值通常为算法两次迭代优化目标函数差值<1×10^-6,迭代次数阈值设为网络节点数的2倍).若初始估计的模型参数不准确,会导致后期更新的模型参数是一个较差的局部最优解; 每次随机选择1个节点则会使算法不能快速收敛.因此,可利用主动策略选择信息量大或难以识别的节点进行标记的特点,将这些信息作为监督信息,以提高算法的准确率.本研究采用3种策略对onlineVEM算法的准确性及效率进行改进.

策略1 主动选择代表节点进行标记.考虑到在线算法上次迭代参数对下次迭代的参数更新有较大影响,初始参数应保证有较高准确性,因此,需在初始化参数时尽量确定影响力大的节点的类隶属度.为使代表节点对其同类节点具有较大影响,可通过主动策略选择代表节点标定初始化参数,并利用代表节点的精确标定最大程度影响剩余节点.基于k-rank-D^[14-15]选择最可能成为代表节点的候选集合,并用标定的约束对先验从候选集合中选择各类的代表节点,利用代表节点初始化模型参数.

策略2 主动选择不确定节点进行标记.当代表节点确定后,网络中仍存在一些难以确定类别的边界节点.通过节点类隶属度信息主动选择不确定性高的节点,利用约束对先验确定其与哪个代表节点具有必联(must-link)关系,从而实现不确定节点类别的标记.

策略3 基于迭代框架的在线算法.迭代运行onlineVEM算法,每次基于上次算法迭代的结果,选择最不确定的节点进行标记,进而得到一个更优解,下次算法从该解开始寻找更优的解.该迭代框架能找到比运行1次onlineVEM算法更优的解.为提高算法运行效率,在迭代过程中,对于已标记类别信息的节点在后续算法中将不再估计其类隶属度.

选取不同结构的人工网络和真实网络数据集对ASonlineVEM算法进行测试,并与半监督社区发现SuperNMF和ALISE算法比较.其中,主动节点标记使用的约束对先验比例R_P为网络节点对的百分比; 网络节点对为n(n-1)/2, n为网络节点数.

使用如式(7)的标准化互信息^[17](normalized mutual information, NMI)来衡量算法准确性.它可较好地评估基准标签与计算得到的标签之间的相互关系和吻合程度,常用来评价网络结构发现的质量.NMI值越接近1,表示算法聚类准确度越高.

NMI(X,Y)=(2I(X; Y))/(H(X)+H(Y))(7)

其中, X是计算结果; Y是真实结果; I(X; Y)=∑_x∑_yp(x,y)lg(p(x,y))/(p(x)p(y)); H(X)=-∑_x[p(x)lg p(x)]; H(Y)=-∑_yp(y)lg p(y); p(x)和p(y)分别为x和y的概率分布; p(x, y)为x和y的联合概率分布.

算法使用Matlab 2014软件在Intel^ Core^TM i5-6200U CPU,8 Gbyte内存的Windows 7(64 bit)计算机上运行.考虑到算法每次运行都存在差异性,取5次结果的均值作为实验结果.

基准网络 Girvan-Newman(GN)网络中,顶点与社团外顶点连边数的均值Z_out决定社区结构的清晰程度, Z_out越大,网络结构越复杂.图1分别为Z_out=8和Z_out=9时3种算法的NMI结果对比.可见,ASonlineVEM算法准确率明显高于其他网络,尤其当Z_out=9时, R_P=1.6%, ASonlineVEM算法准确率为0.92,ALISE算法仅0.33.随着Z_out增加,对比算法准确率明显下降,ASonlineVEM准确率较高,说明后者能准确发现更复杂的网络结构.

图1 三种算法在GN网络上的NMI对比结果
Fig.1 NMI comparison results of three algorithms on GN networks

图2 三种算法在LFR网络的NMI对比结果
Fig.2 NMI comparison results of three algorithms on LFR networks

Lancichinetti-Fortunato-Radicchi(LFR)基准网络结构比GN网络的更复杂.设网络节点数分别为1 000,最小和最大社区节点数分别为20和100,节点度分布参数为2,社区大小分布参数为1,混合参数μ决定了发现网络结构的难易程度,设μ为0.7和0.8.图2为在LFR基准网络上3种算法的NMI结果.由图2可见,ASonlineVEM算法的的准确率明显高于对比的半监督社区发现算法.综上可见,在具有社区结构的基准网络上,ASonlineVEM算法的社区发现准确率要高于对比算法,尤其在网络结构不清晰时更能体现算法的优势.

人工网络 采用ASonlineVEM、SuperNMF和ALISE算法对人工生成具有社区结构(network1)和二分结构(network2和network3)的网络进行实验,参数设置如表1.图3为3种算法在3个网络上的性能实验结果.由图3可见,在社区结构网络中,3种算法效果相当; 而在二分结构网络中,相同先验比例下ASonlineVEM算法准确率高于对比算法.如在network2中,R_P=0.12%时,ASonlineVEM算法的准确率约是对比算法的2倍.在人工网络上,ASonlineVEM的准确率高于对比算法.

表1 人工网络数据集
Table 1 Synthetic network dataset

图3 三种算法在人工网络上的NMI对比结果
Fig.3 NMI comparison results of three algorithms on synthetic networks

真实网络 本研究使用的真实网络数据集包括经典网络Dolphins、Football、Adjnoun和Friendship^[18],以及Facebook网络Baylor、USC、Maryland和NYU^[19].真实网络数据集合的具体参数请扫描论文末页右下角二维码见表S1.图4为分别采用ASonlineVEM、SuperNMF和ALISE算法在小规模经典网络数据集上测得的NMI结果.由图4可见,不同先验比例下ASonlineVEM算法性能均优于其他算法.

图4 三种算法在经典真实网络的NMI对比结果
Fig.4 NMI comparison results of three algorithms on classic real networks

ASonlineVEM和ALISE算法都是基于迭代框架的主动半监督社区发现算法,图5为2种算法在真实大规模复杂网络Baylor和USC数据集上的NMI性能对比.由图5可见,在大规模复杂结构网络上,ASonlineVEM算法的准确性都优于ALISE算法.

图5 ASonlineVEM和ALISE算法在Facebook网络上的NMI对比结果
Fig.5 NMI comparison results of ASonlineVEM and ALISE algorithms on Facebook networks

对于具有社区结构的网络,ASonlineVEM算法初始通过主动策略选择代表节点进行标定,保证初始参数有较高的准确性,再利用代表节点的精确标定最大程度影响剩余节点.迭代过程主动选择不确定性且信息量大的节点进行标记,提高了算法发现网络结构的准确率.SuperNMF算法随机选择先验导致无法充分利用高质量先验信息.ALISE算法可发现社区网络的聚类结构,但非社区网络network2和network3的聚类结构属于二分结构,SuperNMF和ALISE算法主要处理的是社区结构发现问题,无法发现多类型网络聚类结构.

分析不同网络的准确率结果发现,随着先验比例的增加,ASonlineVEM算法较其他同类算法准确率更高、收敛速度更快、稳定性更佳,表明该算法效果均优于其他算法.

ASonlineVEM算法不仅能准确识别网络的聚类模式,还能高效处理不同规模网络.对于规模较小的基准网络,如Z_out=9的GN网络,当R_p=2%时,ASonlineVEM、SuperNMF和ALISE算法运行时间t分别为0.258 7 、0.611 6和0.552 0 s.在网络节点较少的真实网络Football上,当R_p=14%时,ASonlineVEM、SuperNMF和ALISE算法的运行时间分别为0.185 4、0.364 0和4.296 4 s.可见,ASonlineVEM算法运行效率最高,其他小规模网络上也有相同运行结果.

针对节点较多或边数较多的大规模复杂网络,为简单起见,给出部分大规模网络上ASonlineVEM和ALISE算法的运行时间对比结果.network2和network3人工网络的时间对比结果如图6.图7为两种算法在Facebook数据集上数据传输一次所需要的时间对比结果.总的来说,在不同规模网络上,ASonlineVEM算法明显比ALISE算法高效.

ASonlineVEM算法在迭代过程中,对已标记类别信息的节点将不在后续算法中估计其类隶属度,只计算剩余节点的类隶属度,大幅节省了算法耗时. ALISE算法每次迭代选择网络中最不确定的链接进行人工标记,而大规模网络的边数往往远大于节点数,这使ALISE算法每次迭代计算边不确定性的复杂度较大,导致算法运行时间长.

图6 ASonlineVEM和ALISE算法在人工网络上的运行时间对比
Fig.6 Time comparison of ASonlineVEM and ALISE algorithms on synthetic networks

图7 ASonlineVEM和ALISE算法在Facebook网络上运行时间对比
Fig.7 Time comparison of ASonlineVEM and ALISE algorithms on Facebook networks

提出了主动半监督大规模网络结构发现算法ASonlineVEM,基于网络数据可快速且准确地识别潜在的多类型聚类结构,利用主动学习方法选择构造高质量先验提高了算法准确率,利用在线技术提高了算法运行效率,有利于在推荐系统和舆情分析中用户群体划分等领域的实际应用.但是,该算法目前主要针对的是静态大规模网络,如何实现动态大规模网络的结构发现算法以及在大数据平台下的大规模网络结构发现算法仍需深入研究.