融合结构-属性交互二部图随机游走的社区搜索方法*

李 举，马慧芳,2，李青青，宿 云

(1.西北师范大学计算机科学与工程学院，甘肃 兰州 730070;2.桂林电子科技大学广西可信软件重点实验室,广西 桂林 541004)

1 引言

属性网络是真实世界关系的自然表示形式，本质上是携带属性信息的节点借助特定关系相互连接形成的图。已有研究发现：现实世界的网络中存在明显的“社区”特性，即社区结构满足社区内连接尽可能稠密且属性相似，而社区间连接则尽可能稀疏且属性尽可能相异[1,2]。近年来，面向属性网络的社区发现引起了广泛关注，这类方法往往需要利用异构数据信息间的互补特性，是图挖掘研究中最重要的问题之一[3-5]。随着图规模的不断增大与现实世界应用场景的不断丰富，用户往往不需要对整个图进行划分，而仅需要提供样例节点表征兴趣从而定位局部社区，这使得基于用户个性化要求的社区搜索任务备受关注[6]。寻找用于属性网络的有效、可行的社区搜索方法是一个很重要的课题，其难点在于如何利用属性探索更符合社区语义主题的密集子图。 例如，在科学家合作网络中，以某个科学家作为查询节点执行社区搜索任务，挖掘出的关系子图是与该科学家有相同研究领域且合作密切的同事，此类语义的社区可以为以该科学家为中心的科研讨论提供成员推荐建议。若邀请的同事彼此熟识(结构相似)且具有相似科研兴趣(属性相似)，那么就有更大的可能性成功组织该讨论。再比如在社交网络中，以某个用户作为查询节点的社区发现可以定位该用户的潜在朋友。如果推荐的潜在用户与查询用户兴趣相似度大，则很有可能挖掘到查询用户的潜在朋友。这种类型的社区搜索对于诸如推荐系统等实际应用具有重要意义。

基于随机游走的改进方法因为能够找到与查询节点紧密相连的社区而被广泛应用。代表性工作包括：Tong等人[7]提出了重启随机游走RWR(Random Walk with Restart)，该方法通过改进传统的随机游走方法，得到了针对查询节点的其他节点的重要性排名向量，该向量能较好地提高社区搜索结果的质量。然而这种方法忽略了对节点的属性信息的分析，使得社区搜索结果的可解释性欠佳。越来越多的社区搜索改进方法将属性信息纳入到搜索过程中来改善其在属性图上的表现。这类方法[8 - 11]通常通过节点的属性信息来计算节点相似度，之后基于属性相似度和特定的拓扑结构2类约束从查询节点扩展社区。例如：ACQ(Attributed Community Query)[12]是一种基于社区扩展方法的属性社区搜索算法，其主要是通过将k-core作为结构性约束来找到与查询节点属性相关度高的社区。Andersen等人[13]提出一种基于PageRank-Nibble的方法完成社区搜索任务并证明了其可行性，该方法通过最小化电导值探索社区。电导值由将局部社区与外界的连边数比上局部社区度数和外部社区度数两者之中的最小值得到。模块度被作为图中所有社区的划分基准，因此着眼于图中整体社区划分的优劣，忽略了单个社区的好坏。电导值是对单个社区的密集程度进行评定，不考虑对整个图的影响，因此借助电导值能够发现更具有代表性的个性化社区。

综上所述，以社区扩展为策略的有效属性网络社区搜索方法已经被深入研究，而基于随机游走的属性网络社区搜索的方法依旧稀少。这是因为在属性网络上进行随机游走有以下挑战：(1)如何将属性信息融合到随机游走的过程中；(2)如何利用随机游走得到的重要性得分向量查找社区。针对以上2个挑战，本文提出了融合结构-属性交互二部图的随机游走的社区搜索方法SAR-AC(Structure Attribute Random walk-Attribute Conductance)和适用于属性图社区搜索的电导值。首先，设计了由属性图构造结构-属性交互二部图的方法；其次，给出了融合结构信息和属性信息的转移矩阵的构造方法和融合属性的跳转机制；再次，通过优化传统的电导函数将其应用在了属性图的社区搜索任务中；最后，通过充分的实验表明了本文提出的局部社区搜索方法的可行性和融合属性信息的电导值对社区搜索的有效性。

2 准备知识

2.1 符号介绍与问题定义

设G=(V,E,F)表示属性网络，其中V={v1,v2,…,vn}表示节点集合，E⊆V×V表示边集，F={f1,f2,…,fm}表示属性集。矩阵An×n为结构邻接关系矩阵，若节点vi与节点vj有边，则Aij=1,否则Aij=0。矩阵Qn×m表示节点-属性关系矩阵，若节点vi具有属性fj，则Qij=1,否则Qij=0，Qi是节点vi的属性向量。设G对应的真实社区集合为C={C1,C2,…,Cd}，Ci表示某特定社区，且Ci∩Cj=∅，C1∪…∪Cd=V。

给定查询节点vi，社区搜索的目标是查找包含查询节点vi的社区Ci。设D表示社区搜索算法返回的社区，D中的节点应具有紧密的结构链接性，且节点属性应与查询节点包含的属性高度相关。算法的有效性可由Ci与D之间的相似性评价。

本文使用的具体符号及其含义如表1所示。

Table 1 Notations and their meanings

2.2 重启随机游走与电导值

重启随机游走方法是在传统随机游走方法基础上的改进。步行者从图中的某个节点出发，每一步跳转面临2个选择，随机跳转到相邻节点，或者返回开始节点。经过迭代到达平稳，平稳后得到的概率分布可被看作是受开始节点影响的重要性分布。具体地，重启随机游走公式定义如式(1)所示：

(1)

电导是测定图中一组顶点的紧密程度的常见指标。传统的电导度量定义如式(2)所示：

(2)

其中，|φ(D)|表示社区D与外部连接的边数，vol(D)表示社区D中节点的度数和，vol(V)-vol(D)表示图中去除社区中节点的剩余节点的度数和。

3 融合结构-属性的社区搜索方法

尽管传统的重启随机游走在普通网络上的社区搜索效果良好，但在属性图上的社区搜索结果却差强人意。属性作为属性图中描述节点的关键信息，在包含属性的社区搜索过程中需要着重考虑。因此在执行重启随机游走前，需要将属性信息融入概率转移矩阵中并且利用属性信息优化电导值，以精确地定位社区。本节首先介绍了结构-属性交互二部图并给出了在二部图上的跳转机制和转移矩阵，其目的是将属性信息融入到随机游走的过程中；之后提出了基于融合结构-属性的随机游走和融合属性信息的电导值的社区搜索方法SAR-AC。

3.1 结构-属性交互二部图

为了能够在随机游走的过程中加入属性信息，需要重构跳转机制及其转移矩阵。将节点与属性的链接关系构成的图视为结构-属性交互二部图。首先，将给定网络中的节点和属性分为2个类别的节点；其次，将节点与其对应的属性节点连边。具体定义如下：

定义1(结构-属性交互二部图)SAG=(V∪F,ESAG)，其中ESAG⊆V×F。则节点-属性关系矩阵Qn×m即对应于该二部图的邻接矩阵Qn×m。对于∀vi∈V，∀fj∈F,若节点vi与属性fj存在连边(即节点vi边包含属性fj),则Qij=1，否则Qij=0。

结构-属性交互二部图能够直观地展示节点与属性的关系，如图1所示，为结构-属性二部图的构造过程。带有数字标号的圆形代表节点，灰色条形中的f1～f4代表节点所附着的属性。由属性图可知节点1上附着的属性是f2，f3，f4。由定义1，节点1和f2，f3，f4应有连边。将属性图中的节点与其包含的属性相连即可构造出结构-属性二部图。

Figure 1 Construction process of structure-attribute bipartite graph

传统的随机游走机制在转移矩阵中仅包含拓扑结构上的转移概率，而本文将属性信息纳入了转移矩阵中，这使得步行者不仅仅在节点之间跳转，还可能存在“节点-属性-节点”的跳转方式。值得注意的是，在“节点-属性-节点”的跳转方式上，起始节点可能最终会跳转到其非邻居节点上。这是由于这2个节点都拥有相同的属性，可能属于同一社区，因此这种跳转是合理的。如图1所示，以节点1为起始节点进行跳转，通过掷硬币的方式来介绍跳转机制。如果硬币正面朝上，则由节点1跳转到节点2；如果硬币反面朝上，则由节点1跳转到f4,再由f4跳转到节点3。

假设从任意节点vi∈V开始跳转，通过掷硬币的方式来进行跳转，如果硬币正面朝上，则依照属性图的拓扑结构跳转到相邻的节点上：

(3)

如果硬币反面朝上，依照给定的结构-属性交互二部图以一定概率随机跳转到节点上附着的属性集中的任意节点。然后再任意跳转到包含这个属性的节点上。

(4)

(5)

在硬币反面朝上的情况中，“节点-属性-节点”的跳转满足式(6)定义的结构-属性二部图转移矩阵Sn×n：

S=DvQDaQT

(6)

(7)

由于传统的随机游走中的转移矩阵仅包含拓扑结构的转移概率，要在结构-属性二部图上进行结构-属性随机游走需要将属性信息添加到转移矩阵中，其定义如下：

定义2(属性-结构转移矩阵R) 基于网络拓扑结构所构成的概率转移矩阵和融合结构和属性的2阶段的概率转移矩阵构成属性-结构转移矩阵R，构造方法如式(8)和式(9)所示：

(8)

(9)

假设：通过掷硬币的方式模拟从网络中的任意节点进行跳转时的选择过程。每一次掷硬币的行为之间相互独立；从节点跳转到属性，再由属性跳转到节点，这2个跳转过程也相互独立。以下给出概率转移矩阵R的跳转机制的证明：

证明若硬币正面朝上，则以β概率在拓扑结构网络上进行跳转：

若硬币反面朝上，则以1-β的概率在结构-属性二部图上进行跳转：

则从节点vi跳转到vj的概率为：

□

3.2 结构-属性二部图的社区搜索方法

缺失属性信息是基于传统随机游走的社区搜索在属性图上效果不理想的根本原因，因此如何将属性信息的作用在随机游走中发挥出来是一个值得研究的问题。基于在结构-属性交互二部图上的跳转机制和转移矩阵，本节首先给出了融合结构-属性的随机游走定义，之后给出了融合结构和属性的并行电导，最后提出了结构-属性二部图的社区搜索方法。

定义3(融合结构-属性的随机游走) 融合结构-属性的随机游走是对传统随机游走的改进，将属性信息和结构信息融合成为转移矩阵Rn×n，具体的公式定义如下：

rt+1=α×R×rt+(1-α)×q

(10)

为了能够找到社区内部连接紧密、外部连接稀疏的社区，Andersen等人[13]采取最小化电导值的方法确定社区。传统的电导函数(2.2节)利用社区与外部连接边数比上社区节点度数总和与外部未探测区域度数总和之间的最小值来作为界定社区内聚性优劣的阈值。电导值越小，则说明局部社区与外部连接越稀疏，且内部连接越紧密，因此找到的局部社区自然也就越准确。综上所述，采用电导值衡量社区的内聚性和分离性是准确且有效的。虽然该方法有效地通过结构信息解决了局部社区的定位问题，但是该方法仅考虑到结构上的内聚性，直接应用到属性网络会因为缺少属性信息的支撑而导致局部社区的不准确性。因此，本文提出融合属性的电导值的计算方法如下所示：

属性相似度矩阵Pn×n，Pij表示的是节点vi和节点vj的相似度值。采用Jaccard计算任意2个节点的属性相似度，具体计算如式(11)所示:

(11)

其中,⊙表示2个向量做元素乘积计算，即相应位置相乘。‖Qi‖0表示向量Qi的0-范数,即向量中非零元素的个数。

融合结构和属性信息的并行割定义如式(12)所示：

(12)

由并行割的定义可得知结合结构和属性的并行电导公式如式(13)所示：

(13)

为了能够合理地定位社区，首先将迭代后的得分向量r中的每一个分数值除以其对应节点的度得到rank(vi)并进行降序排列，计算公式如式(14)所示：

(14)

假设得到的排列为rank(v1),rank(v2),…,rank(vk),定义扫描集合大小为从1到k的集合：Vj={v1,v2,…,vj},1≤j≤k。扫描所有的集合，并为每个集合计算电导值，最后将电导值最小的集合作为结果社区D返回。

融合结构-属性交互二部图随机游走的社区搜索方法大致包括以下步骤，首先通过输入的属性图构造结构-属性二部图；之后通过融合结构-属性的随机游走机制得到查询节点的得分向量；最后通过最小化融合结构和属性信息的电导公式找到结果社区。本文方法的流程如算法1所示。

算法1结构-属性二部图社区搜索方法

输入:属性网络G=(V,E,F)，查询节点q，重要性调节参数α，β,最大迭代次数iterations，相似度阈值λ。

输出:结果社区D。

步骤1构建邻接矩阵An×n，节点-属性关系矩阵Qn×m,初始化Nodelist为空集，初始化G[Vi]为空集；

步骤4利用式(6)构造结构-属性二部图转移矩阵Sn×n；

步骤5利用式(8)构造融合结构和属性信息的转移矩阵Rn×n；

步骤6whilet

rt+1=α×R×rt+(1-α)×q;

t=t+1；

rt=rt+1;}

endwhile

步骤7 fori←0 tondo

ifr[i] >λ

Nodelist←r[i]

endif

endfor

步骤8通过Nodelist[i]/vol[i]的大小对Nodelist进行降序排序；

步骤9 fori=startpostoNodelist.lengthdo

G[Vi]←Nodelist[0]～Nodelist[i];

记录Con(G[Vi]);

endfor

步骤10将Con(G[Vi])值最小的G[Vi]作为结果社区D并返回。

具体来说，步骤1～步骤5是初步准备工作。步骤5中的β取值0.5为最优，这是因为在构造转移矩阵Rn×n时，需要通过β来衡量结构信息和属性信息的重要性，而结构信息和属性信息占比过少或过多都会使得结果社区不准确，在4.3.1节中的实验中可以看出β取0.5时，结果最优。步骤6是融合结构-属性的随机游走。步骤7筛选出了高得分的节点，λ的最优取值随着数据集的不同而不同，其中r[i]是指第i个节点的得分值。步骤7～步骤10首先将得分向量中的每一个分数值通过式(14)计算其对应的排名，其中vol(vi)表示第i个节点的度；之后将rank(vi)的值大小进行降序排列；然后按照次序将分数值变动的节点依次加入到局部社区中并计算其对应的电导值；最后将电导值最小的局部社区作为结果社区返回。

该方法的时间复杂度分为执行随机游走部分和社区搜索部分。第1部分的时间复杂度为O(iterations)，第2部分的时间复杂度为O(n+n),其一，因为要筛选节点的重要性分数值，故而要执行n次；其二，因为需要遍历Nodelist，将其中每个节点加入社区来计算电导值，且Nodelist的最大长度为n，故而要执行n次。该方法总体需要的时间复杂度是O(iterations+2n)。

4 实验结果及分析

为了验证本文方法的有效性，设计实验进行验证。首先介绍实验所需的数据集；其次在实验设置中给出本文方法评价指标并介绍对比方法；最后对实验结果进行分析，并结合案例分析阐释本文方法的有效性。实验环境采用内存为16 GB，CPU为Intel i7-8750H Core 2.67 GHz,GPU为NVIDIA RTX2070，操作系统为Windows 10的计算机。所有代码都是使用Python 3.7实现。

4.1 实验数据集

本文在真实和人工数据集上进行了大量的实验以评估本文方法的有效性。真实数据集包括Cora和Citeseer。这2个数据集都是经典的引文网络数据集。其中节点代表的是论文，边代表的是论文之间的引用关系，节点上的属性是与论文相对应的关键词，根据关键词的不同可将论文分类到不同社区。具体描述如表2所示。

Table 2 Statistics of real-world datasets

人工数据集是使用LFR benchmark生成的LFR-1和LFR-2。参数符号的含义如表3所示。其中参数的设置如下：

Table 3 LFR parameters and their meanings

在人工数据集的每个真实社区中，为节点随机地附着相似的属性，且保证2个社区之间的属性有差异。为了提高实验的准确度，在以上4个数据集上的每一个真实局部社区都随机采样50个节点作为查询节点，分别对50个查询节点所得到的评价标准取平均值作为最终结果。

4.2 实验设置

4.2.1 评价指标

为了衡量方法的有效性，采用召回率(recall)，精确率(precision)和F1-socre作为评价指标，具体定义如式(15)～式(17)所示：

(15)

(16)

(17)

其中，CT表示的是查询节点所属的真实社区，CF代表的是本文方法检测出的社区。recall指的是方法返回的正确的社区节点的个数占真实社区节点个数的比例。precision指的是方法返回的正确的社区节点的个数占其返回节点总数的比例。F1-score是召回率和精确率的调和平均数。以上3个评价指标的取值都在0～1，且数值越大代表着方法的性能越佳。

文献[12]提出了衡量局部社区中属性内聚性的评价指标CMF(Community Member Frequency) 来衡量属性社区中的属性内聚性。本文定义改进后的属性内聚性CMF-S(CMF-Single)如式(18)所示：

(18)

其中，FN(q)是节点q携带的属性集，fh是社区D中包含第h个属性的节点个数。CMF-S的取值在0～1，其值越大说明社区的属性内聚性越好。

4.2.2 对比方法

实验的主要对比方法有2类，包括本文方法的变种和其他方法。

为了比较融合属性电导值和传统电导值对结果社区质量的影响，采用本文方法的变种方法SAR-C作为对比方法，该方法的随机游走方法与本文相同，但基于传统电导值获取社区。

为了比较随机游走方法对结果社区质量的影响采用RWR-C和RWR-AC作为对比方法。这2种方法是在无属性图上的社区搜索方法，这2种方法首先通过重启随机游走RWR得到图中节点的重要性排名，之后使用与本文相同的策略对节点进行排名并得到扫描集合，最后分别采用传统电导值(RWR-C)和融合属性的电导值(RWR-AC)对集合的电导值进行计算，将电导值最小的集合作为结果社区返回。

为了说明本文方法的有效性，采用ACQ[12]作为对比方法，该方法是一种在属性图上的社区搜索方法，返回同时满足结构内聚性(即节点之间紧密连接)和关键词内聚性(即社区内的节点共享相同的关键词)的属性社区。

4.3 实验结果与相关分析

4.3.1 参数对实验的影响

本节将探索重要性调节参数对社区结果的影响。采取固定一个参数，调节另一个参数数值的方法来得到参数对社区结果的影响。为了能够有效地测试出参数对测试方法性能的影响，α取0.5。在真实和人工数据集上的实验结果如图2所示。

Figure 2 Influence of β on SAR-AC performance

从图2可以看出，重要性参数会影响结果社区的性能。在2个数据集上的实验结果表明，在属性(或者结构信息)占有极端小的比例时，SAR-AC的性能并不好，而在结构和属性信息各占一半的时候，SAR-AC的性能最好。这是因为SAR-AC在构建转移矩阵时同时考虑了结构和属性信息。如果结构信息占比过高，则查找出的节点大多与查询节点属性相似度低，这导致结果社区在结构上紧凑而在属性上稀疏；如果属性信息占比过高，又会导致查询过于精确而使得查询得到的节点较少，故而导致SAR-AC效果不好。由图2可以看出，在2类信息的占比均接近一半时，SAR-AC的效果最佳，这也符合结构信息和属性信息在属性社区搜索过程中互补的特征。

4.3.2 2种电导值的比较

本节揭示了融合属性的电导值和传统电导值在属性图上社区搜索中的差异。为了能够清晰地辨识出2种搜索标准对社区搜索的准确度，将本文方法与SAR-C、RWR-C和RWR-AC的结果作对比，如表4所示。

Table 4 Influence of conductance on each method performance

由表4可以看出，SAR-AC在2个数据集上的表现都优于SAR-C。这是因为属性社区是由节点之间的公共偏好和关系共同组成的，这意味着仅仅考虑结构信息的社区搜索方法不能够满足属性社区搜索的需要。而本文方法将属性信息融合到随机游走起到了显著的改进作用。RWR-C和RWR-AC的召回率都较小且相同，这是由于RWR的转移矩阵中没有融合属性信息，故而找到的正确节点较少。而引入融合电导值的RWR-AC的精确率有明显升高，这是由于融合属性的电导值有效过滤了那些与查询节点属性同质性低的节点。

图3展示了4种方法的结果社区的CMF-S值，该值越大则说明社区的属性内聚性越高。从图3中可以看到,SAR-AC的效果最好，而SAR-C由于划分社区时忽略了属性信息而导致属性内聚性偏低。同样地，RWR-AC考虑了属性信息，因此属性内聚性略优于RWR-C。

Figure 3 Comparison of the attributes cohesion in local community

4.3.3 与其它方法的比较

本节通过SAR-AC与RWR-C和ACQ的比较来验证本文方法的有效性。表5列出了3种方法在3个数据集上的实验结果，其中粗体字表示最佳性能。

Table 5 Comparison with other methods

从表5中可以看出，考虑了属性信息的方法具有最佳性能，本文方法表现最佳。RWR-C是不考虑属性信息的社区搜索方法；ACQ虽然考虑了节点的属性信息，但是仅仅考虑了局部社区属性同质性最大的情况。SAR-AC既考虑了节点属性信息，又汇聚了节点与属性的跳转关系。实验结果不仅展现了本文方法的有效性，而且还说明了加入“节点-属性-节点”跳转机制对社区搜索效果的优化作用。

4.4 案例分析

为了能够更好地说明本文方法的有效性，本节比较了SAR-AC和SAR-C在数据集Cora上的社区搜索结果，结果如图4所示。其中黑色节点是查询节点，浅灰色节点集是查找到的局部社区，白色节点是其它社区节点，图4a和图4b的查询节点是一样的，因为大小问题，仅展示了全部结果图的一部分。从图4中可以看出，SAR-C和SAR-AC寻找的结果社区都大致符合局部社区的特征，然而SAR-C的结果社区包含数量较多的无关节点。从图4b中可以看出，这些无关节点大多是边界节点。该类节点与真实社区的属性交互较稀疏，所以将其划分到了结果社区中，但是这类节点与真实社区节点的属性同质性并不高，所以采用传统的电导率方法无法将其与真实社区分割。但是，在图4a中，融合属性的电导值可以有效地过滤这些边界节点。

Figure 4 Local communities discovered by SAR-AC and SAR-C

5 结束语

针对现有的基于随机游走的社区搜索方法忽略了属性信息的问题，本文提出了一种融合了结构-属性交互二部图随机游走的社区搜索方法。首先通过节点与属性的关系构造结构-属性交互二部图，重构转移矩阵；然后通过改进后的重启随机游走得到查询节点的得分向量；最后基于融合属性的电导率定位查询节点所在的社区。通过在4个数据集上的实验表明了本文方法的有效性。