融合属性熵权和拓扑的局部社区发现算法

曹 旭，殷 铭，漆翔宇

(1.西南民族大学计算机科学与工程学院，四川 成都 610041；2.东华大学信息科学与技术学院，上海 200051)

复杂网络研究一直是图领域中的热点研究问题，通过对复杂网络的研究可以有效揭示事物间隐含的固有深层关系.例如通过对社交网络的研究可以帮助人们理解社会现象，对社交网络用户的关系和所发表的言论进行分析，从而获取不同群体的关系和观点立场，进而对网络舆论予以管控[1].

社区结构是社交网络的一个重要特征，通常定义为具有紧密联系的一组节点.社区内的节点连接紧密，即内聚性强；社区之间连接较为松散，即耦合度弱[2].社区发现在现实生活中具备广阔的应用前景.如，可以对形成的社区进行针对性的定向营销、疾病传播建模预测、社交平台的舆情监测分析等[3].

1 研究现状和存在问题分析

传统的社区发现算法通常侧重于全局角度检测社区，但是随着网络规模的快速扩张，网络的全局信息获取难度不断加大，导致算法效率不断下降甚至算法无法使用.2005年，Clauset[4]提出只考虑目标节点以及周围节点信息的局部社区发现算法.该算法定义了“局部社区模块度”这一局部社区质量指标.此为局部社区发现算法被首次提出.近年来，Wu[5]等人考虑到节点和社区相似度这一因素，通过赋予更高权重优先级给高相似度的节点，以利于构建局部社区.Bouyer[6]提出了一种基于局部相似性的多级标签扩散算法.该方法的优势在于从低度节点由外向内的传播标签，具有极低的时间复杂度.考虑到节点的属性可以帮助发现社区，同时可使所形成的社区具有更好的可解释性[7].Naderipour[8]等人基于可能性C-means模型，通过在大规模社交网络中使用结构相似性和属性相似性来发现局部社区.Lu[9]等人提出了一种基于领袖节点的局部社区发现算法.该算法利用网络中节点之间的属性信息构造属性相似度矩阵，然后将其与网络拓扑信息相结合来建立节点之间的依赖关系.进而，借助形成的依赖树，可以得到社区划分的最终结果.此外，研究人员还提出诸如模糊相似度[10]、节点熵[11]、图嵌入[12]等方法来完成局部社区的发现.

综上所述，当前研究都仅从相似性出发考虑节点属性信息，着重于属性值自身意义，忽略了属性值在概率上的含义.地发现社区.此外，设计一种两阶段的属性加权策略来区分不同属性的权重，以满足社区扩张过程的动态变化.综合以上二者再加之文献[13]提出的社区密度，从而形成了“融合加权属性熵和拓扑结构的局部社区发现算法(WAET)”.

2.1 问题定义

给定图G＝{VG，EG，A}，其中VG＝{vi｜i＝1...n}为图G的节点集，共n个节点；EG＝{eij｜(i，j)∈VG}为图G的边集，共m条边；A＝{at｜t＝1...d}为图G的属性集，共d条属性.ai＝{avit｜vi∈VG，t∈A}是节点vi的属性向量，avit表示节点vi在属性at上的取值.Q是目标节点.要求在图G上寻找一个包含目标节点集的子图C(即社区)，社区节点集为VC＝{vi｜i＝1...c}，共c个节点；EC＝{eij｜(i，j)∈VC}为图的边集.

2.2 算法描述

2 WAET局部社区发现算法

本文将信息熵理论引入社区发现中，提出利用“社区加权属性熵”衡量社区的属性同质性，从而更好

首先，创建初始社区:结合“节点属性”和“拓扑结构”挖掘目标节点的核心节点集.其次，根据核心节点集学习社区初始属性权重.之后，遍历当前社区的邻居节点，并计算不同邻居节点加入社区所能带来的社区质量增益.若添加该邻居节点可以给社区带来超越历史加入节点的平均质量增益，则将该节点加入社区并更新社区属性权重；反之则跳过该节点.循环遍历直到没有邻居节点可以加入则终止循环.最终，将当前社区作为局部社区结果返回.算法流程详见图1.

图1 WAET算法流程图Fig.1 Algorithm flow chart of WAET

2.3 核心检测

本阶段是算法的第一步，旨在检测合适的节点集作为局部社区的核心成员，对应图1的“a”部分.研究表明，社区的形成和稳定取决于其核心成员[14]，因此合适的核心检测是十分重要的.首先，挖掘图G中包含目标节点的极大团[15].由于包含目标节点的极大团之间可能相互重叠，所以需要进行筛选.若两个规模为N的极大团之间存在N-1个重叠节点，且两个非重叠节点的属性相似度同时大于两个极大团的平均属性相似度，则将两个极大团合并成一个新节点集.当所有节点集均无法合并时，选择平均属性相似度最大的节点集作为核心节点集.离散属性相似度采用余弦相似度计算，连续属性相似度采用欧几里得相似度计算.

2.4 初始属性权重

由于不同属性在发现社区时的贡献并非相同，也并非恒定的，因此本文设计了一种两阶段的属性加权策略来确定属性的权重.首先考虑到社区的核心节点集可以在一定程度上代表最终的局部社区，因此可以根据社区的核心节点集学习属性初始权重.本阶段对应图1中的“b”部分.

给定核心节点集Z，可通过最小化核心节点集的加权属性距离之和，求解各属性初始权重向量，目标函数定义如式(1).

其中，c是核心节点集的节点数，d是属性集的大小，wt代表属性at的权重，β是权重wt的参数，avit是节点vi在属性at上的值，vt＝K∈Vcore，‖avit-avjt‖2是节点vi和节点vj在属性at上值的差值二范数.该目标函数描述了初始社区中节点之间基于属性的加权距离之和，属性权重遵循约束条件:其中wt∈[0，1].

对于有约束的函数极值求解，可通过Lagrange乘子法解决，最终求解出的初始权重wt见式(2).

2.5 局部社区质量函数

求解出属性的初始权重之后，便可扩张核心节点集以获得最终的局部社区，即图1中的“c”部分.在本阶段，算法会根据不同邻居节点加入社区所能带来的社区质量增益判断是否将其加入当前社区.社区质量由本文提出的局部社区质量函数计算，该函数从社区密度和社区加权属性熵两个角度对社区质量进行了衡量.函数公式见式(3).

其中，α为平衡结构信息和属性信息的参数；Dens(C)为社区密度；Ent(C)为社区加权属性熵.

2.5.1 社区密度

文献[13]提出的社区密度可以衡量社区的结构内聚性，虽其原是针对二部图所设计，但其思想可沿用于本文所用图中.社区密度Dens(C)定义为社区中节点对密度均值.节点对密度Dens(C)_node定义见式(4).

其中，(a，b)是社区C中的节点对；N(a)是节点a的邻居集；为节点a的邻居数量；vi是节点a的邻居；vi是节点b的邻居；φ为示性函数，见式(5).

进一步的，局部社区密度计算方式见式(6).

当使用社区密度Dens(C)作为社区检测的评价标准时，社区密度越高，社区内部的节点对越紧密.这一趋势与社区发现所要求的社区结构非常一致.因此，社区密度可以用来判断社区发现结果的好坏.

2.5.2 社区加权属性熵

信息熵[16]可以衡量一个系统的混乱程度，信息熵越大则系统越混乱，反之则系统越有序.

基于信息熵可以衡量系统混乱程度的思想，本文提出社区加权属性熵.假设社区内各属性之间相互独立的情况下，首先计算社区内各属性的信息熵值，之后将各属性熵加权加总后即为社区的加权属性熵.计算方法如下.

设社区中任一节点vi∈VC在属性at∈A上的属性概率为

即节点vi在属性at上能取到值avit的概率.显然，pi天然具有归一性，则社区C在属性at上的属性熵定义为:

当各属性相互独立时，社区的加权属性熵计算见式(10).

由于前文中社区密度的值域为[0，1]，而属性熵的值域在[0，log2c]之间，在值域不同的情况下无法将两者线性结合.故本文采用反正切归一法将社区属性熵映射到[0，1]中，最终和社区密度构成局部社区质量指标.反正切归一法计算见式(10).

2.6 动态权重调整

虽然社区加权属性熵从属性取值概率出发，提供了考虑节点属性的新角度，但也忽略了属性值的自身信息.因此在社区扩张过程中，采用属性相似度作为基本指标来弥补社区属性熵的不足，并据此完成第二阶段的属性权重调整.本阶段同样属于图1中“c”部分的内容.

若社区内多数节点在属性at上都取值相似，则属性at有利于社区发现；反之，若取值分布十分随机，则at不是很好的社区属性.社区属性权重的计算见式(11).

其中，sim(avit，avjt)是节点vi，vj关于属性vi，vj的相似度.

3 实验及分析

为了验证本文所提出算法的有效性，本文选择与两种局部社区发现方法:FocusCO[17]和TSCM[18]及一种全局社区发现方法:CODICIL[19]在真实数据集上进行了大量实验以作对比.实验选择三个指标:准确率(Accuracy)、标准化互信息(NMI)[20]和局部模块度(Local Modularity)来衡量算法性能.实验数据集使用了四个真实数据集:Political Books(Polbooks)、SinaNet、Facebook100以及Cora数据集.由于SinaNet数据集中存在无边节点，故予以清除.真实数据集信息详见表1.

表1 真实数据集Table 1 Realworld datasets

3.1 WAET参数设定

3.1.1 参数α的取值

参数α是平衡局部社区质量函数的拓扑结构和节点属性的参数.图2为当α取值区间为[0，1]时对Accuracy和局部模块度的影响.

图2 α取值对于算法性能的影响Fig.2 Influence of different α values on algorithm performance

由于Polbooks数据集只有“政治倾向”一个属性且并非稀疏图，其在属性和结构相对平衡时表现较好；Cora数据集由于是二进制属性同时属性维度较高，当属性占比过大时会影响实际社区发现的精确性；SinaNet数据集和Facebook100数据集均为较为密集的图，且属性维度均在10以内，但Facebook100数据集中属性缺省值较多，即便进行填充，属性占比过大也会降低算法性能；而SinaNet数据集的真实社区分类就是依据属性偏好进行分类，所以属性占比相较拓扑结构多时反而会取得较好的结果.

3.1.2 参数β的取值

在计算属性权重时，除了属性内部的相似度会影响到权重值外，参数β同样会对权重产生影响.

当β＜0时，Dt越大，wt越大，但wβt越小.而且由于β是负数的原因，在计算Dt时，权重wβt对于计算结果的影响也越小了，显然该情况不考虑.

当β＝0时，所有的权重值恒为1，相当于忽略了权重因素，不符本文初衷，故不予考虑；当β∈(0，1)时，Dt越大，权重wt越大，wβ t越大，这并不符合实际情况中社区的属性同质性，所以不考虑.

当β＝1时，对于可以让Dt中的最小值的属性at来说，可以让其权重为1，其余的属性的权重为0.虽然目标函数此时已经最小化，但是相当于只用了一个属性进行社区发现，抛弃了其余属性的影响.对于高维属性社区发现问题来说，故该方法不可取.

当β＞1时，Dt越大，wt越小，wβt也越小.具有较大Dt的属性at对于社区发现的影响也就越小.

综上所述，最终权重参数β的取值应当大于1.

由于Polbooks数据集只有一个属性，因此对该数据集β取1即可，对于其他数据集，本文进行了大量的实验.实验证明，β取值在8、10、12时表现较好.图3展示了不同的β值对算法Accuracy和局部模块度的影响.

图3 β取值对于算法性能的影响Fig.3 Influence of different β values on algorithm performance

3.2 结果分析

由于所用真实数据集中只有SinaNet数据集和Cora数据集具有真实社区分类结果，因此选择用NMI和Accracy两个指标与TSCM、FocusCO这两个局部社区发现算法和全局社区发现方法CODICIL对比；而没有真实社区结果的Polbooks数据集和Facebook数据集选择使用局部模块度(Local Modularity)指标进行衡量.

图4和图5展示了本文算法与对比算法在具有真实社区情况数据集上的准确率和NMI值表现，图6展示了本文算法在没有真实社区分类的数据集上的局部模块度表现.

图4 Cora数据集上的Accuracy和NMI结果对比Fig.4 Comparison of Accuracy and NMI results on Cora dataset

由图4和图5可知，本文算法无论是在Accuracy还是NMI指标上的表现均优于对比算法，而全局社区发现算法CODICIL的表现较差.

图5 SinaNet数据集上的Accuracy和NMI结果对比Fig.5 Comparison of Accuracy and NMI results on SinaNet dataset

由图6可知，本文算法在无真实社区分类的数据集上的表现也保持稳定，CODICIL因其为全局算法，因此在局部模块度上的表现较差，与其他局部社区发现算法差距较大.

图6 Polbooks和Facebook100数据集上局部模块度结果对比Fig.6 Comparison of local modularity results on Polbooks and Facebook100 datasets

4 总结

针对现有局部社区发现算法中利用节点属性时仅从相似度出发，存在过于针对属性值而未考虑其概率值的问题.本文提出了一种从信息熵理论出发的社区加权属性熵指标，并在此基础上设计了新的局部社区发现算法——WAET算法.该算法不仅为衡量社区属性同质性提供了新的思考角度，还较好解决了局部社区发现所存在的问题.

事实上，实际情况中的社区结构大多是重叠的，但本文算法无法识别重叠社区结构，因此对于重叠社区的发现将在下一步的研究工作中进行.