现实世界中事物与事物之间是密切联系的，普遍存在的联系将大部分事物映射成一个个复杂系统，这些系统往往能表示为图或网络的形式.网络中节点间除了存在连接关系外，节点往往可由描述其特征的属性信息刻画.面向属性网络社区结构的深入研究有助于揭示相对独立而又相互关联的社区是如何形成错综复杂的网络，帮助人们更好地理解网络不同层次的结构和功能特性.尽管面向属性网络的社区发现方法已经得到了广泛的关注，但现有方法大多数未能定位基于用户偏好的目标社区.目标社区发现是半监督局部聚类方法，其挖掘到的社区节点受用户偏好控制.例如，化妆品销售经理可能更关注社交网络中的某个社区，该社区中的成员具有一定年龄、性别以及收入水平等特点，并且社区外部影响力较高，经理可以向社区中成员进行产品推荐并期望通过口碑传播的方式推广其产品；科研人员则需要挖掘特定领域的研究人员所在的社区，该社区中的成员具有较高的学术影响力且成员研究兴趣相似.因此，在属性网络中如何基于用户给定的样例信息挖掘与用户兴趣相关的内部一致且与外部分离良好的高影响力目标社区显得尤为重要.少数研究人员通过对现有社区发现方法改进，在一定程度上能够提升目标社区质量，但是现有方法的局限性使得基于用户兴趣的目标社区发现任务仍然面临着严峻挑战，如何同时利用节点间的连接关系和属性信息挖掘外部影响力高的目标社区仍是研究热点.
本文提出融合用户兴趣偏好与影响力的目标社区发现方法(target community detection method with user interest preferences and influence, TCPI).首先，结合节点属性信息，挖掘包含样例节点的极大k-团作为潜在目标社区核心；其次，对于每个极大k-团，设计熵加权属性权重计算方法，计算得到潜在目标社区属性子空间权重；再次，利用属性子空间权重，基于改进的模块度定义社区模型，挖掘高质量潜在目标社区；最后，结合社区质量及外部影响分数对所有潜在目标社区降序排列，选取综合质量较高的社区为目标社区.此外，基于无监督技术给出2重剪枝策略提升方法性能和效率.在人工网络和真实网络数据集上的实验结果印证了本文所提方法的效率和有效性.
本文的主要贡献有3方面:
1) 以包含用户给定样例节点的极大k-团作为潜在目标社区的核心，利用熵加权属性子空间挖掘方法，充分利用用户给定的先验信息，计算目标社区核心节点彼此相似的属性权重，从而精确采集用户偏好信息.特别地，考虑到极大k-团间的冗余特征，设计2重剪枝策略，减少运行时间并增强方法效率.
2) 基于社区内部连接紧密且外部分离性较好的性质，定义高质量的目标社区模型，使得社区内部节点连接紧密，与此同时在对应属性子空间权重下内部节点彼此相似且与外部节点不相似，因此提升方法的性能.
3) 除了准确挖掘与用户给定样例节点相似的高质量节点所构成的社区外，社区向外部用户传播社区内部信息的能力即社区的外部影响力也是非常重要的方面.本文创新性地融合用户偏好和节点及社区的影响力挖掘目标社区，增进方法的应用价值.
融合用户兴趣偏好与影响力的目标社区发现方法框架图如图1所示：
Fig. 1 Research framework for target community detection method with user interest preferences and influence
图1 融合用户兴趣偏好与影响力的目标社区发现方法框架
1 相关工作
1.1 社区发现研究现状
社区发现已成为复杂网络分析领域中非常重要的研究方向[1-2].现有的社区发现方法大致可以划分为2类：面向整个复杂网络分析的全局社区发现方法和针对特定目标设计的局部社区发现方法.
1) 全局社区检测.传统的社区发现方法多是基于全局信息，主要可以分为两大类：一类是计算机科学中的图分割方法，主要根据添加或者删除边的原理[3]；另一类是社会学中分级聚类方法，这是寻找网络中社区结构的传统方法，其原理是将具有相似性的一类节点归为同一个社区.除此之外，也有很多学者提出了与其他领域融合的方法:如基于信息论、基于模拟物理电路、基于信号传播等特殊的方法.Rosvall等人[4]从信息论出发，对网络中社区结构进行编码，并对编码进行压缩可得到社区划分.马慧芳等人[5]提出融合标签平均划分距离和结构关系的微博用户可重叠社区发现方法.然而，随着网络规模不断增大，要获得网络的全局信息是十分困难，同时获取过程中计算量也十分巨大，因此传统社区发现方法在大规模网络环境下效率不高.
2) 局部社区检测.现有大多数局部社区检测方法往往以种子为初始社区，通过运行质量函数的贪婪优化过程来扩展社区.因此，质量函数和扩展办法决定了局部社区检测方法的有效性.Rhouma等人[6]提出了基于凝聚聚类的重叠社区发现方法.该方法从节点开始聚类，通过重复扩展节点的邻居直到扩展达到平衡状态停止.Ding等人[7]设计了基于核检测和社区扩展的2阶段局部社区检测方法.核心检测阶段将种子替换为目标社区的核心成员，而社区扩展阶段以检测到的社区核心单元为初始社区，并根据节点关系强度对社区进行扩展.Zhang等人[8]提出了将网络划分为任意数量社区的谱方法，该方法利用从模块度最大化到向量分区问题的映射，并结合向量分区对网络进行划分.局部社区检测一定程度上缓解了全局社区检测所面临的效率问题，但是难以针对特定应用准确定位基于用户偏好的目标社区.
1.2 社区外部影响力量化方法
“口碑效应”和“病毒式营销”中的影响力模型研究是近年来网络分析领域的研究热点之一.因此，节点及社区影响力量化变得尤为重要.现有影响力计算方法主要分为2类：一类是针对单个节点的中心性度量；另一类是将社区作为整体量化其外部影响力.
1) 基于核心节点的外部影响力量化方法.节点中心性度量主要针对局部社区发现方法中核心节点的选择所设计.Zhang等人[9]针对大规模的社会网络提出了基于节点重要性和标签影响的社区检测标签传播方法.Shi等人[10]认为具有较大影响力的人总是扮演更重要的角色，更可能成为社区的核心，据此提出了基于影响力的方法来发现潜在的核心成员，从而揭示社区结构特征.特别地，王星等人[11]针对复杂网络中的社区检测问题，提出了基于节点影响力的离散粒子群社区检测方法，将社区中节点影响力与社区检测相结合.从影响范围、影响程度等角度来看，将众多节点组成的社区作为一个整体，其影响力无疑将大大超过单个节点的影响力[12].
2) 基于社区整体的外部影响力.现有针对以社区为整体开展影响力分析的工作较少.代表性工作有：Liu等人[13]研究微博社区影响力的评价方法，提出了一个基于微博信息传播机制的指标体系，将定量指标和定性指标相结合，并利用主成分分析将这些指标组合成若干综合指标，简化了指标体系；Zhang等人[14]提出了具有信息传播视角的社区影响评价模型框架和一套相关的社区影响评价形式定义，涉及到用户影响和社区影响；Yao等人[15]提出基于PageRank的可变影响社区检测方法，可以调整特定节点所在的社区，增加其影响力.然而对于目标社区发现任务，除了准确挖掘高质量的与用户给定的样例节点相似的节点构成的社区外，社区向外部用户传播社区内部信息的能力即社区的外部影响力也是一个非常重要的方面.
1.3 现有目标社区发现方法
无论是基于全局的社区发现还是基于局部的社区发现方法均与基于用户偏好的目标社区发现方法具有紧密的联系和严格的区别.与本研究相关的研究通常可分为社区搜索和目标社区发现.
1) 社区搜索.在图中给定样例节点，社区搜索旨在查找样本节点周围的子图，这些子图中的节点由与种子节点高度相关的节点组成.将输入节点作为种子，并根据特定的目标函数从种子中扩张社区同样可以获得与查询节点相关的社区.
代表性的目标函数有局部模块度、偏向密度的查询、个性化PageRank和邻域扩张.例如：Fang等人[16]研究有向图上的社区搜索问题，在给定有向图和查询节点的情况下，基于节点的最小入
出度，寻找一个包含查询节点的稠密连通子图；Liu等人[17]设计了2阶段局部社区检测方法，利用广度优先扩展由种子替换和扩展来定位局部社区；Kloumann等人[18]研究了使用个性化PageRank模型来识别一组种子节点所在社区，该研究依赖于种子选择并假设有一些基准社区，但无法高效地基于查询请求在大型图中搜索特定的目标社区；Bian等人[19]提出了基于多查询随机游走社区检测方法，该方法在访问过程中考虑不同游走者之间的交互信息精准捕获社区；Yan等人[20]以种子节点的社区隶属关系作为先验信息，通过颜色标记不同种子节点，并引入基于染色的随机游走机制将种子节点颜色传播到图中的其余节点，挖掘不同颜色种子所在社区.然而以上方法均适用于简单图且仅仅考虑节点间直接交互信息，忽略了高阶邻居对节点重要性的影响，因此对于用户兴趣发现不够有效.在这些方法中，局部社区结构通常通过某些度量值(如局部模块化、k-团、k-truss和k-core)来捕获[21-23].近年来出现了许多新颖的网络模型，社区搜索方法面向这些类型多样的网络也开展了一些初步研究，包括异构网络[24]、public-private网络[25]、地理社会网络[26]和层次属性图[27]等.特别地，在搜索社区时，将属性引入图节点可以在一定程度上实现更大的个性化[28].例如基于关键字的社区搜索方法可以显著提高检索有效性.但是，基于属性的社区搜索只关注简单的属性，现实世界中的图具有3种类型的属性，即数字属性、二进制属性和分类属性.
2) 目标社区发现.目标社区发现方法以用户给定样例节点作为先验信息，发现与用户偏好相关节点所构成的高质量且有一定的外部影响力的社区.Perozzi等人[29]提出了面向用户的属性图挖掘方法，该方法允许用户通过提供一组样本节点来引导社区，所提供的样例节点被认为是相似的，并且与用户感兴趣的社区节点相似.Perozzi等人提出的方法没有说明需要多少样例节点，但明确指出需要2个以上的样例节点.Wu等人[30]提出了在目标子空间中挖掘目标社区集合的方法，该方法根据用户提供的2个样本节点扩展一组样本节点，并从中推导出目标属性权重指导挖掘目标社区的集合.然而，现有的半监督目标社区聚类技术虽然考虑了用户偏好，但在聚类过程中仅考虑了节点属性信息或只利用节点部分属性.文献[31]提出的目标社区发现方法未能考虑社区外部影响，并且社区模型仅考虑社区内部节点间的紧密程度，忽略了社区与其外部节点间的连接关系.此外，现有的目标社区方法均忽略了社区对外部节点及社区的影响能力.
针对以上问题，本文提出的方法可以有效地挖掘与用户偏好相关的高质量且具有一定外部影响力的目标社区.首先，为了有效挖掘用户偏好信息，基于用户给定的样例节点，挖掘包含样例节点的极大k-团作为社区核心，并设计熵加权属性子空间计算办法，自动捕获用户兴趣；然后，基于社区内部连接紧密及与外部节点分离较好的特性，定义高质量的目标社区模型，以极大k-团为社区核心挖掘得到质量较高的潜在目标社区；最后，利用社区内部节点与外部剩余节点的连接及属性关系，定义社区外部影响力，并创新性地首次将社区内部质量与其外部影响力相结合，基于用户偏好挖掘得到高质量且具有一定影响力的目标社区.此外，该方法可以扩展到网络中多个社区发现任务中.在人工数据集和真实网络数据集上的实验结果印证了本文所提方法的有效性和效率以及应用价值.
2 社区核心挖掘
2.1 问题定义
给定属性图G=(V,E,F)，V={v1,v2,…,vn}是节点集合，n为节点数目，E={(vi,vj)|vi和vj之间存在边}是边的集合，|E|=m；A=[aij]n×n是图G的邻接矩阵,如果(vi,vj)∈E，则aij=1，否则aij=0.F={f1,f2,…,fr}是属性集合，给定节点v∈V，其属性列向量f(v)=(fv1,fv2,…,fvr)T.z∈V表示用户给定的样例节点.
是根据用户给定的样例节点z挖掘得到包含节点z的极大k-团.
是由
修剪得到的新极大k-团集合，
是由集合Ck中的每一个极大k-团扩展得到的候选目标社区集合，其中
集合B={B1,B2,…,Bx,…,Bd}，其中的元素Bx是社区Cx的邻居节点构成的集合，即(u,v)∈E,∀u∈Cx,v∈Bx.潜在目标社区的属性子空间权重矩阵为L=(l1,l2,…,lt,…,ld)，第x个潜在目标社区Cx的属性子空间可以通过权重列向量lx=(lx1,lx2,…,lxt,…,lxr)T表示，lxt衡量了潜在目标社区Cx中第t维节点属性ft的重要性，并且属性子空间权重满足一个约束，即
2.2 极大k-团挖掘
极大k-团模型具有4个可取的内在属性，即社团、凝聚力、连通性和极大值.具体来说，一个极大k-团是一个连通的诱导子图，包含至少k个节点(社团)；k-团中任意2个节点之间连接(连通性)，且属性相似性较高(内聚性)；对于任意k-团都不是另一个k-团的子图(极大值).
基于节点间的属性关系，改进文献[32]提出了非递归极大团挖掘算法，即Kose算法，具体地，定义节点间属性相似度如下：
定义1. 节点属性相似度.节点u和v的属性相似度s(u,v)定义为
(1)
其中，
为节点u，v属性列向量差值二范式，节点间属性相似性介于0和1之间.
如果2个具有N个节点的团有N-1个节点相同，剩余不相同的2个节点之间存在边且节点间属性相似度较大，即s(u,v)>α，α为节点间最低属性相似度阈值，则2个N节点大小的团可以形成一个N+1个节点团.改进Kose算法从2个节点大小的极大团生成所有3个节点大小的团，再用3个节点大小的团来生成所有4个节点大小的团，迭代直到没有新的更大的团可以生成为止.
给定属性图G=(V,E,F)和用户提供的样例节点z∈V，利用改进的Kose算法，同时考虑节点间的连接关系和属性相似度，局部挖掘包含用户给定样例节点z的极大k-团所构成的集合
2.3 基于熵权约束的属性子空间挖掘
以极大k-团作为潜在目标社区的核心，计算核心内节点彼此相似的属性权重，该属性权重能够使得社区中的内部节点基于属性彼此相似且与外部节点不相似[33].利用文献[31]改进的目标社区属性子空间权重目标函数计算属性子空间权重向量.社区Cx(x∈{1,2,…,d})属性子空间权重目标函数定义为
(2)
其中，|Cx|是社区所包含节点的个数，r是节点属性维度个数，lxt表示社区Cx第t维属性的权重.第1项是集合内部节点间距离，第2项是负熵值，γ是控制多维度权重激励强度的一个正参数.最小化目标函数，对于潜在目标社区Cx可以得到该社区的属性子空间权重向量lx=(lx1,lx2,…,lxt,…,lxr)T，且lx只在少数与子空间中属性对应的维度有较高的值，其余维度的值较小.该属性子空间权重满足了一个约束，即
通过对F(lx)最小化，求得：
(3)
其中，
2.4 挖掘k-团剪枝策略
考虑到以用户所给定样例节点作为先验信息，挖掘得到的包含已知节点的极大k-团彼此之间存在相互重叠，因此基于无监督技术设计2重剪枝策略，优化极大k-团集合，提高方法的效率.
策略1. 无监督剪枝策略.如果用户未能给定任何有关属性先验信息，则定义2重无监督剪枝策略.首先，消除所有多余极大k-团.在当前极大k-团集合中，如果选中的极大k-团不是冗余的，那么该极大k-团将保留在集合中，否则删除.其次，在去除冗余后的极大k-团挖掘得到的目标子空间集合中，依据不同节点间可能没有连接关系但基于属性可能相似的特性，基于改进的k-medoid算法[24]中的初始点选取策略选择差异最大的d个k-团作为每个潜在目标社区的核心.
具体地，给定与用户相关的极大k-团集合
及参数μ∈[0,1]，极大团
相对于
来说是多余的，当且仅当
所有冗余的极大团都被淘汰得到去冗余后的极大k-团集合
没有特殊要求的情形下，μ=0.5是可以被允许的重叠[29].其次，挖掘去冗余后的极大k-团集合Ck′所对应属性矩阵
并将每个极大k-团所对应的属性子空间作为集合中的元素存入空集
得到去冗余后的极大k-团属性权重集合
然后在集合
中随机选取一个权重向量lx作为初始点存入新的属性权重集合
中，并更新权重矩阵L，即
最后根据式(4)选取中与集合所包含的元素相似度最小的节点作为下一个潜在目标社区权重，即：
(4)
其中，lx为待选定的第x个属性子空间；β为决定属性子空间个数的阈值，β越大则得到的属性子空间个数越多，得到的社区越多.不断重复直到
中无满足式(4)的子空间时结束，得到新的子空间集合为
以及新的子空间矩阵L=(l1,l2,…,ld)，d为更新后的属性子空间个数.极大k-团集合被更新为
3 社区发现及综合排名
推断出第x个潜在目标社区Cx的属性子空间权重向量lx=(lx1,lx2,…,lxt,…,lxr)T之后，挖掘潜在目标社区Cx中心点集
及属性子空间lx所对应的潜在目标社区.本节将以去除冗余后的每个包含样例节点的极大k-团作为潜在目标社区的种子，调整种子以找到基于属性子空间权重内部连接紧密且与外部有较好分离性的潜在目标社区.值得注意的是，在推断目标社区时是基于局部信息提取的而不是划分整个图.
3.1 目标社区模型构建
高质量的社区满足2个特性[34]：1)内部一致性；2)外部可分性.直观地说，好的社区在其内部节点之间有许多内部边，且彼此共享一组具有相似值的属性.换句话说，其内部节点只在对应属性子空间权重下彼此相似且与外部节点不相似.此外，好的社区在其边界上要么只有较少边，要么许多交叉边可以被“免除”，也就是说，使社区内部节点彼此相似的属性子空间也会使其与边界节点不相似或与其边界节点分离.因此，本文基于高质量社区的2个方面量化了社区质量.
定义2. 节点加权属性相似度.给定节点u和v在社区Cx的属性子空间下的加权属性相似度s(u,v|lx)定义为
s(u,v|lx)=exp(-
)=
(5)
其中，f(v)表示与节点v关联的属性向量,diag(lx)是用lx构建的一个对角矩阵.对于一个社区而言，每个属性对社区均有贡献，但贡献不同.通过引入社区Cx的非负权向量lx来计算加权节点相似性.
定义3. 社区质量函数.给定社区Cx及其属性子空间lx，则社区Cx质量函数的定义为：
s(vi,vj|lx)=Ix+Ex，
(6)
其中，Ix表示社区Cx的内部一致性，Ex表示社区Cx外部可分离性.ki表示节点vi的度数，
表示在随机网络中度为ki的节点vi和度为kj的节点vj在与原图相同度分布的随机网络中互相连接的“期望”.交叉边(vi,bj)∈E(vi∈Cx,bj∈Bx)在高“期望”的情况下或当内部节点vi与基于焦点属性权重的边界节点bj不相似时被免除.
对于具有较高质量分数的目标社区而言，存在较多“期望”低的内部边，与此同时成对节点的相似性很高.这确保了式(6)中第1项的最大化.此外，社区要么没有交叉边，要么现有交叉边“期望”高，或者内部节点基于属性子空间与边界节点的相似性接近于0，因此第2项消失.
3.2 候选目标社区发现
确定了候选目标社区中心点集及对应属性子空间权重后，挖掘每个候选中心点集及属性子空间权重所在的潜在目标社区.首先以中心点集作为目标社区的种子，然后扩展种子以找到目标社区.算法1中描述了第x个初始潜在目标社区Cx的挖掘过程.
算法1. 潜在初始目标社区挖掘.
输入:属性图G=(V, E, F)、第x个极大k-团以及对应的属性子空间权重lx；
输出:初始潜在目标社区Cx.
① Ncn=∅； *存储候选节点*
②
初始化初始目标社区集合*
③ Ncn={vj|vi和vj之间有边,vi∈Cx,vj∉Cx∧vj∈V}; *将集合中现有节点的邻居节点作为候选节点*
④ ΔQ(Cx,lx)=0,ΔQ(Cx,lx)best=0；
*ΔQ(Cx,lx)记录每次添加节点时潜在目标社区Cx质量值的变化，ΔQ(Cx, lx)best记录质量值的最大变化*
⑤ Repeat
⑥ vbest=null； *最佳候选节点*
⑦ for each v∈Ncn do
⑧ ΔQ(Cx,lx)=Q(Cx,lx,add(v))-
Q(Cx,lx)； *节点v加入社区时质量值的变化*
⑨ if ΔQ(Cx,lx)>ΔQ(Cx,lx)best≥0
⑩ ΔQ(Cx,lx)best=ΔQ(Cx,lx)；
*更新质量值的最大变化*
vbest =v； *记录当前质量值正向变
化最大的节点为最佳节点*
end if
end for
Cx=Cx∪{vbest}； *加入最佳节点*
Ncn←{Ncn∪{v|(v,vbest)∈E,v∉Cx}}
{vbest}； *更新候选节点*
ΔQ(Cx,lx)best=0；
Until vbest=null； *直到没有节点加入使
得目标社区质量值正向增加，停止循环*
Return Cx. *输出初始目标社区*
采用贪婪算法对目标社区进行局部调整，在每次迭代中，计算所有可能调整质量变化的操作，选择社区质量正变化最大的节点加入目标社区.迭代继续，直到没有节点的加入导致质量发生正的改变，社区的质量值不再增加.
节点的添加基于改进的最优搜索策略，即每次添加的节点都是当前最优的选择.类似地，采用了追溯策略检查是否有节点的移除使得社区的质量正向增加.社区的质量函数值小于等于1，每次选择节点加入社区或者删除社区中的节点都能使得目标社区的质量值正向增加，因此算法的收敛性得到保证.
3.3 社区综合质量评估
本节首先定义社区外部质量分数来衡量社区外部影响能力，然后结合社区的质量分数和外部影响能力综合评估社区综合质量.
给定社区Cx及该社区的外部邻居节点集合Bx={b1,b2,…,bw}，定义矩阵
其中每一个元素
表示社区Cx内部节点vi∈Cx对外部邻居节点bj∈Bx的影响程度，具体定义为
(7)
其中，r(vi,bj)表示节点vi和bj之间的最短路径长度.
定义4. 社区对节点影响分数.一个社区Cx对其邻居节点bj的影响分数定义为
(8)
其中，
表示矩阵Px的第j列，定义向量S=(s1,s2,…,s|Cx|)T,其中si=s(vi,z|lx)表示社区内节点vi∈Cx与用户所给定样例节点z基于社区Cx的属性子空间lx之间的相似度.
定义5. 社区外部影响率.给定社区Cx，其社区外部影响率定义为
Score(Cx)=
(9)
其中，max(S)和avg(S)分别表示向量S中的最大值和平均值.邻居节点bj基于2个原则可以被社区Cx影响：1)如果社区Cx内大多数节点与bj基于属性子空间lx较为相似且最短路径长度较短，则bj受社区Cx的影响较大；2)与bj连接最短路径长度较短的社区内部节点与中心节点相似度较高.
为了精确挖掘与用户给定的先验信息相关的目标社区，结合社区质量及社区与内部节点对外影响分数定义社区综合质量分数，并降序排列所有候选目标社区.
定义6. 社区综合质量.给定社区Cx其综合质量Qinf(Cx)定义为
(10)
因此，可以挖掘质量较高且外部影响力较大的目标社区.
3.4 方法推广
大多数属性网络中的节点具有较高的属性维度，考虑到用户更期望关注少数属性，因此用户可以选择给定最关注的属性fi∈F，i∈{1,2,…,r}作为先验信息.基于用户给定的属性信息，根据本文所提出的方法得到去除冗余后的极大k-团所对应的属性子空间，修剪去除部分在用户给定的属性上权重较低的极大k-团，得到新的极大k-团集合，其中集合中每个元素均作为一个潜在目标社区的核心.
策略2. 半监督剪枝策略.给定与用户相关的极大k-团集合
以及挖掘得到的每个极大k-团所对应的属性子空间矩阵
设第x个极大k-团的属性权重向量lx=(lx1,lx2,…,lxt,…,lxr)T，若lx中对应的用户最关心的属性维度fi的权重
则删除该极大k-团，其中
表示权重矩阵
的第i行中的最大值，
等于权重矩阵的第i行中的所有元素的平均值.最终得到包含用户给定样例节点且在属性子空间中对于用户最关心属性有较大权重值的极大k-团所构成的集合
4 实 验
为验证本文所提出方法的有效性及其效率，本节分别在人工数据集和真实数据集上设计了2组不同的实验.首先，对实验所用到的人工数据集和真实数据集分别进行了描述；其次，观察不同参数值的设置对实验结果的影响，选择适宜的参数值；最后，选取3个目标社区发现方法与本文所提出方法进行分析比较.
4.1 实验设置
4.1.1 人工数据集
对于社区检测结果的评估最直接的方法就是将检测结果和现实网络中真实社区相比较.考虑到现实世界中针对目标社区发现的可用网络较少且质量参差不齐，利用人工生成网络对本文所提方法的有效性进行测评成为评价社区检测方法优劣的高效可行的方法.本节利用LFR Benchmark算法生成人工图，具体参数设置参照文献[31].
值得注意的是，在现实世界的图中，每个社区中的成员基于多个属性彼此相似.对于每个带有属性的子空间社区，对于所分配的属性子集中的每个属性fi，其节点属性值从均值μi∈[0,1]和方差σ=0.001的正态分布N(μi,σ)中提取，使得社区节点在对应属性子空间上“一致”，其余属性取值从方差较大的正态分布N(0,1)中提取.共生成了6个内部节点基于属性子空间彼此相似且连接紧密的社区(社区1～6)和1个不分配任何属性子空间的社区(社区7)，总共有7个不同的社区.
实验利用给定的来自社区1的样例节点挖掘社区1，详情如表1所示：
Table 1 Synthetic Network
表1 人工数据集
社区编号节点数边数属性子集132035840{f1,f2,f3,f12}221816634{f4,f6,f13}331634950{f4,f6,f11,f15,f20}41205040{f5,f7,f9,f18}518411850{f2,f3,f8,f10,f14,f19}623018515{f16,f17,f20}740056000总计1788178829{f1,f2,…,f20}
4.1.2 真实数据集
为了验证本文所提出方法在真实网络上的效果，本节选取4个真实世界中的属性网络进行验证.Orkut是一个免费的在线社交网络，用户之间形成友谊.Orkut还允许用户组成一个组即真实社区，然后其他成员可以加入该组.Amazon网络是基于消费者购买某一项目收集的，如果产品1经常与产品2被共同购买，则该图包含从节点1到节点2的无向边.Amazon数据集中为每个类别的产品都定义了真实的社区.DBLP是计算机领域作者的合著网络，以作者与作者合著的国际期刊和会议等公开发表的论文为边构建关系网络，DBLP集成元素不多，只有最基本的论文题目、时间、作者、发表类型及期刊或会议名称等.以DBLP中作者的主要研究方向所在的6个研究领域，即人工智能(artificial inte-lligence, AI)、计算机视觉(computer vision, CV)、数据库(database, DB)、数据挖掘(data mining, DM)、信息检索(information retrieval, IR)和机器学习(machine learning, ML)为社区划分基准.LastFM是用户收听音乐的信息，具体包括双向朋友关系、用户所收听艺术家信息、用户对艺术家标签信息、艺术家标签信息.LastFM中的成员被划分到该成员收听最多的音乐风格，如House，Britpop，Trip-Hop，Gangsta Rap等.预处理后的真实数据信息情况详见表2:
Table 2 The Real-World Network Datasets
表2 真实数据信息
数据集节点边属性名称数量名称数量名称类型Orkut用户2441友谊93102主题分类型Amazon产品14863共购关系33446产品特征混合型DBLP作者28030合著关系 56658关键字二进制LastFM用户12412友谊85239歌曲名称二进制
4.2 实验结果
为了评估所提出方法的性能，本节中采用标准化互信息(normalized mutual information, NMI)均值和F1评分均值[29]，即在同一数据集中运行100次的NMIF1的平均值来度量检测结果与标准结果之间的相似性.该相似性越高，NMI值越接近1；反之则NMI值接近0.F1评分是社区检测方法常用的标准，是查全率和召回率的调和值.NMI和F1评分均值作为后续评价指标并用于实验效果的综合评价.
4.2.1 参数分析
本文所提出方法总共涉及4个参数，其中α为生成包含用户提供节点样例节点间的极大团时所要求的最低属性相似度阈值.β是决定属性子空间个数的阈值，β越大则得到属性子空间个数越多得到的社区越多，β的大小决定了过滤的子空间的数量，直接影响着方法效率.γ是控制多维度权重激励强度的一个正参数，实验结果对γ取值的变化不敏感，与文献[31]相同γ=0.5.μ∈[0,1]是控制极大团冗余度的参数，选取不同的μ值对方法有效性影响较低.没有特殊要求情形下，μ=0.5是可以被允许的重叠[29].给定参数γ和μ的情况下，α和β取不同值时，运行结果不相同.为了寻找最优参数取值，设置实验对比参数α和β取值不同时的运行结果.
为了选取合适的参数，在人工数据集和4个真实数据集上运行本文所提出的TCPI方法.本节将通过实验对参数进行调节，以确定最优的实验参数.由于β的不同取值对参数α没有影响，因此固定β=0.5后，将参数α作为自变量，给定不同参数值观察NMI和F1评分均值的变化.最后通过比对不同参数下的NMI和F1评分均值，取使目标社区的NMI和F1评分均值最大的参数值作为参数，该实验分别在人工数据集和真实数据集上进行.如图2所示，x轴为参数α在0～1之间的不同取值，y轴为NMI或F1评分均值的变化情况.
Fig. 2 Parameter α analysis
图2 参数α分析
当α≥0.7时，5个数据集上的NMI和F1评分均值变化较小，基本趋于稳定，因此设定α=0.7，该数值也将用作后续实验中参数α取值.
相似度阈值β作为选取中心点集时邻居节点与样例节点间相似度的最低标准，在目标社区发现中有着极高的重要性.为选择合适的阈值，设置α=0.7，将β作为自变量，给定不同的β观察标准化互信息NMI和F1评分均值的变化.该实验在5种数据集上进行.如图3所示，x轴为β在0～1之间的不同取值，y轴为NMI均值或F1均值的变化情况.
Fig. 3 Parameter β analysis
图3 参数β分析
从图3可以看到，β=0.65左右时，5个数据集上的NMI和F1均值较高，即设定参数β=0.65可使得检测结果与标准结果之间相似度趋于最大化，该数值也将用作后续实验中参数的取值.
4.2.2 与其他方法的对比
选取2个目标社区划分方法FocusCO(focused clustering and outlier detection in large attributed graphs)[29]，TSCM(mining target attribute subspace and set of target communities in large attributed networks)[30]和一个未考虑社区外部影响力的目标社区发现方法TC-AE(target community discovery based on attribute subspace with entropy weighting)[31]与本文方法分别从发现的目标社区质量和运行时间2方面进行比较.其中FocusCO创新性地提出了以用户为中心的属性图目标社区发现方法；TSCM基于目标子空间挖掘目标社区集合；TC-AE在不考虑社区的外部影响力及边“期望”的情况下划分目标社区.因此本文选取上述3种方法作为对比方法，对比结果如表3所示.
为了进一步验证该方法的有效性，在上述参数设置下，本文基于真实网络数据集对TCPI，FocusCO，TSCM，TC-AE方法进行了评价.所有比较方法的平均运行次数超过10次，每次运行都随机提供样本中描述的默认参数.图4显示了不同数据集上不同指标的总体性能.
Table 3 Comparison of Different Target Community Detection Methods
表3 现存目标社区检测方法对比
方法属性结构属性权重用户偏好边“期望”社区影响力FocusCO√×√√××TSCM√×√√××TC-AE√√√√√×TCPI√√√√√√
Fig. 4 NMI/F1 scores on different datasets
图4 不同数据集上的NMI或F1得分
由图4可知，在4种数据集上，本文所提出的TCPI方法挖掘的目标社区NMI均值和F1均值在所有真实数据集较为稳定且最高，TC-AE与TSCM方法挖掘的目标社区NMI均值和F1均值较为接近且均低于本文所提出方法；FocusCO方法效率最低.特别地，在Amazon数据集中，本文所提出目标社区发现方法TCPI的NMI均值和F1均值最高，因此，TCPI方法适用于高维且具有多种属性类型的数据.
4.2.3 扩展性验证
为了进一步验证本文所提出方法的可扩展性，基于LFR Benchmark生成具有不同节点个数、不同边数或不同属性个数社区的图，并运行基于2重剪枝策略的融合用户兴趣与影响力的目标社区发现方法.图5显示了在人工网络上随着节点或属性数量的增加子空间挖掘运行的平均时间变化情况.
Fig. 6 Experimental results on Amazon data
图6 Amazon数据运行结果
Fig. 5 Running time analysis of mining target subspace
图5 子空间挖掘运行时间分析
从图5(a)可以看出，随着节点个数的增长，FocusCO，TSCM，TC-AE，TCPI的时间成本都略有增加.此外，这些方法的时间成本相对比较稳定，并且维持在一个较低的水平.在图5(b)中，随着属性个数变大时，所有方法花费的时间均有所增加，而属性个数对TSCM的运行时间影响最小，TCPI略逊于TSCM，但是与基于距离度量优化的FocusCO相比，可与TC-AE方法相媲美.尽管与TCPI相比，TSCM需要的时间更少，但本文所提出的方法能够识别出更好的真实社区.
4.2.4 案例分析
由于真实网络对于融合影响力的目标社区的集合没有给定的基准，而且大多数社区发现方法都未能考虑节点及社区影响力问题，因此在真实的网络中对本文所提出的方法很难进行定量分析.以下在真实网络的案例研究主要说明本文所提出方法的应用价值.针对本文所提出的方法在Amazon数据集上的运行结果设计了目标社区的案例研究.如图6所示，同一种形状的节点隶属于同一个社区，特别地标示出用户给出的样例节点.
图6中，左边为原始网络，右边为检测结果，其中每个圆圈中同一形状节点构成的子图为一个真实社区，六边形节点表示用户给定的样例节点，七角星节点表示部分社区的邻居节点.同样地，对于某个产品的推销人员而言，除了挖掘经常购买该产品的客户所构成的社区方便进行客户维护外，还需要关注该社区内人员能否吸引更多的潜在客户进行购买，以便扩大产品销售市场，增加市场占有率.因此，本文提出的方法在现实生活中有较高的应用价值.
5 总 结
本文提出面向属性网络的融合用户兴趣偏好与影响力的目标社区发现方法TCPI，挖掘用户偏好信息，挖掘包含样例节点极大k-团作为潜在目标社区核心，并设计熵加权属性权重计算方法来提取潜在目标社区属性子空间权重，捕获用户偏好；其次，综合社区内部紧密性和外部可分离性定义社区质量函数，以极大k-团为核心扩展得到高质量潜在目标社区；最后，定义社区外部影响分数，并结合社区质量函数值及外部影响分数对所有潜在目标社区排序，输出综合质量较高的社区为目标社区.并且，计算得到所有极大k-团的属性子空间权重后，设计了2重剪枝策略提升方法的性能和效率.此外，在用户提供额外属性信息的情况下，该方法可进一步推广.在人工网络和真实网络数据集上的实验结果印证了本文所提方法的效率和有效性.
[1]Conte A, Matteis T D, Sensi D D, et al. D2K: Scalable community detection in massive networks via small-diameter k-plexes[C] 
Proc of the 24th ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2018: 1272-1281
[2]Liu Zhiyuan, Ma Yinghong. A divide and agglomerate algorithm for community detection in social networks[J]. Information Science, 2019, 482: 321-333
[3]Girvan M, Newman M E. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826
[4]Rosvall M, Axelsson D, Bergstrom C T. The map equation[J]. European Physical Journal Special Topics, 2009,178(1): 13-23
[5]Ma Huifang, Chen Haibo, Zhao Weizhong, et al. Overlapping community discovery for microblog users integrating average distance and structure of tags[J]. Acta Electronica Sinica, 2018, 46 (11): 2612-2618 (in Chinese)(马慧芳, 陈海波, 赵卫中, 等. 融合标签平均划分距离和结构关系的微博用户可重叠社区发现[J]. 电子学报, 2018, 46(11): 2612-2618)
[6]Rhouma D, Romdhane L B. An efficient algorithm for community mining with overlap in social networks[J]. Expert System with Applications, 2014, 41(9): 4309-4321
[7]Ding Xiaoyu, Zhang Jianpei, Yang Jing. A robust two-stage algorithm for local community detection[J]. Knowledge-Based Systems, 2018, 152: 188-199
[8]Zhang Xiao, Newman M E J. Multiway spectral community detection in networks[J]. Physical Review E, 2015, 92(5): 052808
[9]Zhang Xiankun, Ren Jing, Song Chen, et al. Label propagation algorithm for community detection based on node importance and label influence[J]. Physics Letters A, 2017, 381(33): 2691-2698
[10]Shi Wei, Wang Changdong, Lai Jianhuang. Community detection based on influence power[J]. Applied Informatics, 2017, 4(1): 5-8
[11]Zhou Dongqing, Wang Xing, Cheng Siyi, et al. Discrete particle swarm optimization community detection algorithm[J]. System Engineering and Electronic Technology, 2016 (2): 428-433 (in Chinese)(周东青, 王星, 程嗣怡, 等. 离散粒子群社区检测算法[J]. 系统工程与电子技术, 2016 (2): 428-433)
[12]Zheng Wenping, Wu Zhikang, Yang Gui. A novel algorithm for identifying critical nodes in networks based on local centrality[J]. Journal of Computer Research and Development, 2019, 56(9): 1872-1880 ( in Chinese)(郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880)
[13]Liu Chengshui, Wang Qiang, Lai K. Evaluation model based on support vector machine for community micro-blog influence[C] Proc of the 6th Int Conf on Business Intelligence and Financial Engineering. Piscataway, NJ: IEEE, 2013: 75-79
[14]Zhang Bo, Song Qianqian, Peng Ruixiang, et al. A novel community influence evaluation scheme based on information propagation in social network[J]. International Journal of Computing Science and Mathematics, 2016, 7(1): 29-41
[15]Yao Yuntao, Wu Wei, Lei Mingtao, et al. Community detection based on variable vertex influence[C] Proc of the 1st IEEE Int Conf on Data Science in Cyberspace. Piscataway, NJ: IEEE, 2016: 418-423
[16]Fang Yixiang, Wang Zhongran, Cheng Reynold, et al. Effective and efficient community search over large directed graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2019,31(11): 2093-2107
[17]Liu Saisai, Xia Zhengyou. A two-stage BFS local community detection algorithm based on node transfer similarity and local clustering coefficient[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 537: 122717
[18]Kloumann I M, Kleinberg J M. Community membership identification from small seed sets[C] Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 1366-1375
[19]Bian Yuchen, Yan Yaowei, Cheng Wei, et al. On multi-query local community detection[C] Proc of the 2018 IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2018: 9-18
[20]Yan Yaowei, Bian Yuchen, Luo Dongshen, et al. Constrained local graph clustering by colored random walk[C] Proc of the World Wide Web Conf. New York: ACM, 2019: 2137-2146
[21]Yuan Long, Qin Lu, Zhang Wenjie, et al. Index-based densest clique percolation community search in networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(5): 922-935
[22]Zhang Zhiwei, Huang Xin, Xu Jianliang, et al. Keyword-centric community search[C] Proc of the 35th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2019: 422-433
[23]Hu Jiafeng, Wu Xiaowei, Cheng R, et al. On minimal Steiner maximum-connected subgraph queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2017,29(11): 2455-2469
[24]Fang Yixiang, Yang Yixing, Zhang Wenjie, et al. Effective and efficient community search over large heterogeneous information networks[J]. Proceedings of the VLDB Endowment, 2020,13(6): 854-867
[25]Ebadian S, Huang X. Fast algorithm for K-truss discovery on public-private graphs[C] Proc of the 28th Int Joint Conf on Artificial Intelligence. New York: ACM, 2019: 2258-2264
[26]Wang Kai, Cao Xin, Lin Xuemin, et al. Efficient computing of radius-bounded k-cores[C] Proc of the 34th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2018: 233-244
[27]Du Hangyuan, Wang Wenjian, Bai Liang. An overlapping community detection algorithm based on centrality measurement of network node[J]. Journal of Computer Research and Development, 2018, 55(8): 1619-1630 (in Chinese)(杜航原, 王文剑, 白亮. 基于网络节点中心性度量的重叠社区发现算法[J]. 计算机研究与发展, 2018, 55(8): 1619-1630)
[28]Sourabh V, Chowdary C R. Peer recommendation in dynamic attributed graphs[J]. Expert Systems with Applications, 2019, 120(3): 335-345
[29]Perozzi B, Akoglu L, Sánchez P. et al. Focused clustering and outlier detection in large attributed graphs[C] Proc of the 14th Int ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 1346-1355
[30]Wu Peng, Pan Li. Mining target attribute subspace and set of target communities in large attributed networks[J]. arXiv preprint, arXiv: 1705.03590, 2017
[31]Liu Haijiao, Ma Huifang, Chang Yang, et al. Target community discovery based on entropy weighted attribute subspace[J]. Chinese Journal of Information Technology, 2019, 33(8): 111-120 (in Chinese)(刘海姣, 马慧芳, 昌阳, 等. 基于熵加权属性子空间的目标社区发现[J]. 中文信息学报, 2019,33(8):111-120)
[32]Kose F, Linke T, Fiehn O. Visualizing plant metabolomic correlation networks using clique-metabolite matrices[J]. Bioinformatics, 2001, 17(12): 1198-1208
[33]Jing Liping, Ng M K, Huang Zhexue. An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(8): 1026-1041
[34]Perozzi B, Akoglu L. Scalable anomaly ranking of attributed neighborhoods[C] Proc of the 3rd Int Conf Sustainable Design and Manufacturing. Philadelphia: SIAM, 2016: 207-215
