邓治文，许 英，曹 璐
(新疆财经大学 统计与数据科学学院，乌鲁木齐 830012)
A·L·Barabasi等人在《科学》出版的“Emergence of Scaling in Random Networks”[1],标志了小世界网络和无标度网络的诞生，从此开启了复杂网络的新篇章.在社交网络中，具有相同爱好或者相同特征的个体在同一个社团中的可能性更大，但是大多数复杂的社团关系表现出较强的社会效应.这种社会效应一般表示社团内部具有较强的联系，反而社团之间的联系较少.大多数情况下会存在一个个体属于多个社团，这些同时属于多个社团的节点被称作重叠节点，此时进行的就是重叠社团的检测.已有的一些经典检测方法多是通过计算邻接矩阵来表示网络中节点的交互信息.但是邻接矩阵仅仅代表有之间相连关系的信息，通常存在不确定性.Zhu X J[2]提出一种先标记一部分节点从而预测其他节点信息的方法，被称为标签传播算法(LPA).首先任意选择一个节点作为种子节点，然后由该节点开始扩散，逐渐形成一个社团，直到适应度函数达到局部最优为止.由于该算法简单，时间复杂度低且分类效果好，引起了国内外学者的关注，并将其广泛地应用到多领域中.两种较为经典的算法COPRAL[3]和SLPA[4]是对LPA的改进算法，得以实现检测重叠社团，COPRAL算法是基于标签传播的模糊重叠社团检测方法，该算法对每一个节点分配了有限的标签数和归属的社团数，SLAP算法是基于spemer-listener的检测重叠社团的标签传播算法.Hong-tao Liu[5]运用网络表征学习的方法表示节点的向量信息，采用密度峰值获取中心节点，通过每个节点的归属度值来确定节点所属的社团.
2014年Rodriguez等人[6]提出了一种基于密度的聚类方法(密度峰值聚类法DPC)，该方法的主要思想是利用低密度区域以分离高密度区域.它可以快速从中挑选出密度高、且与其他密度较高区域相隔较远的节点作为聚类中心，这些点被称为密度峰值点.在密度峰值聚类法中，主要有两个需要计算的量：1)节点间的局部密度；
2)低密度节点与高密度节点之间的距离.但是该方法不适用于高维数据，也就是说传统的密度峰聚类只能检测非重叠社团.
基于节点向量和密度峰值的重叠社区检测方法(DPCL算法)用低维向量表示网络中的节点信息，利用向量内积改进局部密度ρ和节点间的相对距离δ，从而确定出网络的中心节点，接着根据节点与社团的归属度分配其他节点到相应的社团中，直到所有节点分配完成，从而得到网络的重叠社团结构划分.
1.1 基本密度峰值聚类法(DPC)
密度峰值聚类(DPC)方法基于局部密度相对距离分布的特点进行聚类.
1)计算局部密度
在密度峰聚类算法中， 节点i的局部密度是指在截止距离内节点i附近的节点数量.节点i的局部密度ρi定义为：
ρi=∑jχ(dij-dc)
(1)
(2)
其中：ρi是节点i的局部密度，dij是节点i和节点j之间的距离，dc是截止距离.
2)计算距离
与其他高密度点的最小距离δi定义为：
(3)
我们注意到节点的局部密度ρi和相对距离δi越大越有可能处于类的中心.
1.2 改进的密度峰值聚类法
在DPC算法中由ρ和δ都较大的点选作为聚类中心.但是在现实世界网络当中，由于社团数量过大，所以局部密度和相对距离同时显著较大的点并不多，这就导致密度较小或者相对距离较小的社团中心并没有被选中.也就是说，此时的中心节点的ρ和δ可能同时大，也可能一个较大，另一个较小.为了更加准确的选择聚类中心，本文对上述密度峰值聚类法进行了改进.
1.2.1 基于节点向量的距离
在真实世界的网络当中节点之间的直接连接并不多，导致节点之间的关系表现不佳.为解决这一问题，本文采用节点向量余弦相似度对复杂网络数据进行分析.
(4)
(5)
根据式(5)所得节点i和j之间的相似度，从而可以计算出节点i和j的距离d(i,j)：
d(i,j)=1-S(i,j)
(6)
1.2.2 选择中心节点
利用式(6)和式(1)以及式(3)，可得节点的局部密度ρi和相对距离δi，定义ρ和δ的乘积为节点的中心值，记为γ.首先需要对ρ和δ进行标准化处理，以确保它们在相同的范围内， 标准化式如下：
(7)
(8)
(9)
经典的密度峰值聚类以局部距离和局部密度较高的节点作为中心节点，但是真实世界网络存在大量重叠节点(即属于多个社团的节点)，并且重叠节点通常具有较高的局部密度，重叠节点就很容易被选作为社团中心.因此我们将中心值γ按升序排列，可以得到节点中心值从小到大的变化情况，中心值越大的节点成为社团中心的可能性就越大.
1.2.3 分配剩余节点
在密度峰聚类算法中使每个剩余的节点只属于一个集群.因此，本文改进了实现剩余节点重叠分配的方法.具体的分配步骤如下.
1)给中心节点分配标签：假设所获得的社团中心点的数量是m，并将每个社团的标签设置为C={C1,C2,C3,…,Cm}；
2)给与中心节点直接相邻的节点分配标签：如果点i是某一个中心节点的邻点，就把该节点i分配到对应的中心节点所在的社团中，对于与两个以上中心节点的相邻的点，暂时不分配；
3)给剩余节点分配标签：完成步骤2)后，社团中心的邻居将被分配与中心节点相同的标签，因为在下一个标签策略中，这些节点将把它们的标签传播到其余的节点.
当种子区域形成后，标签将根据种子区域的信息在整个网络中扩散到节点的邻居.为了评估节点i与某个社团之间的联系紧密程度，定义节点i与ck社团的归属度为
(10)
本文在计算节点归属关系时，一方面考虑了节点i与局部密度大于节点i的邻节点之间的相似性，另一方面考虑了N个相邻节点的归属度.在方程(10)中，节点与相邻节点的相似性越大，对某个社团的归属度越大，那么节点对该社团的归属度就越大，节点的归属度值最大的那个社团就是该节点所属的社团.依次对剩余节点进行标签，同时更新节点标签重复上述操作，直到所有节点都被标签，即分配完成.
我们假设节点i对Cr社团的归属度与对Ci社团归属度的比值大于阈值σ，即Pi,Cr/Pi,Ci，则节点i同时分配给社团Cr和Ci.也就是说，节点i对社团Cr和Ci的归属度相差不大，即节点i是一个重叠节点.
DPCL算法输入:网络G和阈值σ输出:网络的社团结构划分C={C1,…,Ck}1.计算节点的局部密度和距离:2.For i=1∶n do3. 计算ρi,δi,γi4. 对节点进行标签:5.center=Al(G)6. for i=(1∶n)[-center]do7. if i只与一个中心节点直接相连8. 将节点i分配在对应中心节点所在的社团中9.else不分配10. for未被分配的节点i do11. 由式(10)计算归属度12. 把节点i分配到归属度最大的社团中13.for i=1∶n do14.for所有社团对Cr,Ci,计算15. Pi,Cr/Pi,Ci16. if Pi,Cr/Pi,Ci>σ,17. then节点i同时属于社团Cr和Ci结束
模块度Q[8]是目前常用的测量网络社团结构强度的方法.模块度的值更接近1，社团划分的效果越好，相应的Q值越大.但是它通常只能用来测试非重叠社团结构的划分效果.因此本文采用的是重叠社团模块度EQ作为评价指标.
(11)
其中：m表示网络中的边数，Cl表示第l个社团，O(i)和O(j)分别表示节点i和j所属的社团数，A(i,j)表示网络中的邻接矩阵中ij位置的元素，k(i)和k(j)分别表示节点i和j的度.
标准互信息NMI[9]基本可以客观的评价出社团划分和标准划分之间相比的准确度，用于测量两集之间差值的信息论方法.NMI定义如下:
(12)
其中:A为标准划分结果，B为算法划分的结果，N(i,j)为社团划分A中第i个社团和B中第j个社团之间的公共节点数，N为网络中的节点总数，Ni为A中第i个社团中节点数，Nj为B中第j个社团中的节点数.
本文在4个真实网络:karate、dolphin、football、polbook网络和计算机生成网络上对DPCL算法进行检测，并与其他算法进行对比分析.
3.1 在计算机生成网络上的检测
本文的实验利用近年来广泛使用的人工基准网络程序LFR基准[10]来生成人工合成网络数据集.该程序生成的人工网络可以很好地显示网络的社区结构，也可以很好地模拟真实的网络.LFR基准程序需要调整参数，以生成不同规模和连接强度的人工合成网络.本节所用到的计算机生成网络的参数设置信息见表1.
为了验证DPCL算法在节点分配过程中给出的阈值σ对不同网络检测结果的影响，我们在5个合成网络上进行实验，每个模型的模块度以及NMI的结果如图1.
表1 计算机生成网络的参数信息
图1 不同阈值σ下计算机生成网络的模块度值EQ和标准互信息NMI
如图1所示，在计算机生成网络中，EQ值和NMI值在不同尺度的网络上变化趋势差别不大，所以在以下实验中将阈值设置为0.9.
考虑到在不同的网络结构中算法性能会受到影响，所以本节对网络的一些参数是否对DPCL算法的结果有影响进行验证.
我们测试了网络中节点度、网络的规模和网络中的社团的规模对算法的影响.参数k为节点的平均度，其他参数相同.k被设置为5和10，maxk分别为20和50.网络中较大社团规模设置为(20,100)，偏小的社团大小设置为(10,50).实验在N1、N2、N3、N4和个不同大小的网络上进行了实验.如图2(A)所示，在不同网络大小的数据集上，平均度为10的合成网络的NMI值通常较大.由于实际情况中大多数大规模真实社交网络的平均度值都在10左右，因此实验结果与之相符.从图2(A)和(B)中可以看出，随着网络规模的增大，图中的大部分曲线变化并不明显，网络规模的大小对DPCL算法并没有太大影响.因此，接下来的实验使用合成网络N1来测试内部连接强度和重叠比例对算法的影响.参数μ为社团的内部连接强度系数，分别设置为0.1和0.3.On分别设置为100和500.Om分别设置为2、4、6、8.在图2(C)中，μ的值越大，网络中的社团结构就越复杂，社团检测也就更复杂.在图2(D)中，社团重叠的程度对算法也有一定的影响，重叠的程度越大，算法的性能会逐渐下降.
图2 合成网络上的参数测试
为进一步验证DPCL算法的有效性和可行性.本节实验在同一人工合成网络上:网络节点数为1 000，k=10，μ=0.1，社团规模为，On=10%.选择标准化互信息NMI作为测量指标.所选择的比较算法为DCN算法、CDRS算法、NRLDP算法、Multiscale算法、COPRA算法，结果如图3所示.
图3 不同算法在合成网络上的NMI值
由图3可以看出，在合成网络上本文方法随重叠社团的社团成员的增加没有太大影响，且在现实中重叠节点的社团数量一般不会超过五个，所以DPCL算法比其余五种算法更高一些，因此在某种程度上DPCL具有更多的优势.
3.2 在真实世界网络上进行检测
本节将在四个真实世界网络上去检测本文DPCL算法，四个真实网络如下.
karate俱乐部网络[11]描述了美国某大学空手道俱乐部34个成员之间的社会关系，该网络是由1号节点和34号节点为中心的两个社团；
dolphin网络[12]描述了新西兰62头宽吻海豚之间的关系.dolphin网络的标准化分为2个社团；
football网络[13]是美国某大学举办的橄榄球联赛.这一数据描述了美国橄榄球联赛中共115支大学队伍分为12个联赛先进行小组内部比赛，其次是联队间的比赛情况；
polbooks网络[14]是美国政治书籍的网络，这组数据描述了2004年美国总统大选期间亚马逊上美国政治书籍的销售网络，该网络的标准划分为3个社团.见表2.
表2 真实世界网络基本信息
本节选择了模块度值EQ作为评价指标，并与6个社团检测算法进行了比较.试验结果见表3.由于在阈值在模块度和NMI的影响效果一致，因此选择的阈值大小依然为0.9.根据真实世界网络数据集上每个算法的EQ值，可以看出本文提出的DPCL算法是在4个数据集上实现的比DCN算法、LDC算法和Multiscale算法的EQ值更高.karate网络中的模块度值比CDRS、LDC、Multiscale、COPRA几种方法都要好一些，仅仅比NRLDP算法稍差.在dolphin数据集和football数据集上DPCL算法都取得了较好的效果,仅仅在football网络上比COPRA性能略低，虽然在polbook网络上的模块度值并不突出，但总体上DPCL算法的平均值大于6个算法.因此，可以说本文的DPCL算法总体优于其他六种算法.
表3 不同算法在真实网络上的模块度值
本文提出的基于节点向量和密度峰值的重叠社团的检测方法可以处理维度高且数据更为复杂的网络数据，DPCL首先用低维向量表示节点信息，然后利用向量内积计算节点相似度从而获得节点间的距离，优化了局部密度的计算方法.根据计算的相对距离和局部密度选择核心节点，最后通过归属度分配剩余的节点来检测网络的重叠社团结构.在未来的工作中，用低维向量表示网络的节点和边属性信息，并进一步增强算法，以检测更复杂的网络社团结构.
猜你喜欢 社团标签分配缤纷社团阅读(中年级）(2022年9期)2022-10-08应答器THR和TFFR分配及SIL等级探讨铁道通信信号(2020年9期)2020-02-06遗产的分配数学大王·趣味逻辑(2019年5期)2019-06-13一种分配十分不均的财富小学科学(学生版)(2019年5期)2019-05-21无惧标签 Alfa Romeo Giulia 200HP车迷(2018年11期)2018-08-30不害怕撕掉标签的人，都活出了真正的漂亮海峡姐妹(2018年3期)2018-05-09最棒的健美操社团军事文摘(2017年16期)2018-01-19K-BOT拼插社团中学生(2016年13期)2016-12-01让衣柜摆脱“杂乱无章”的标签Coco薇(2015年11期)2015-11-09科学家的标签少儿科学周刊·少年版(2015年2期)2015-07-07