1、第 5 期2023 年5 月电子学报ACTA ELECTRONICA SINICAVol.51 No.5May 2023规模受限的影响力社区搜索杜明，宋嘉祎，周军锋（东华大学计算机科学与技术学院，上海 201620）摘要：社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前，大部分已有社区搜索方法主要关注社区的结构，没有考虑到特定应用中资源受限的情况，且忽略了社区的属性特征，无法满足用户对社区搜索的个性化要求.针对该问题，本文提出了规模受限的影响力社区搜索（Size-Constrained Influential Community search，SCIC），设计了基于深度优先搜
2、索的基础算法，在此基础上进一步提出了基于结点预处理、剪枝规则和贪心策略的优化算法，用于减少冗余计算，加速枚举过程.在10个不同规模的数据集上进行实验，实验结果表明基础算法在搜索获得的社区规模和影响力上均优于已有算法，同时，本文提出的优化算法能够显著提升搜索效率，将响应时间缩减至基础算法的1%.关键词：数据图；社区搜索；k-核；加权图；规模受限社区；影响力社区搜索基金项目：上海市自然基金项目（No.20ZR1402700）；国家自然基金项目（No.61472339，No.61873337）中图分类号：O157.5；TP301文献标识码：A文章编号：0372-2112(2023)05-1207-0
3、8电子学报URL:http:/DOI:10.12263/DZXB.20220538Size-Constrained Influential Community SearchDU Ming，SONG Jia-yi，ZHOU Jun-feng（School of Computer Science and Technology，Donghua University，Shanghai 201620，China）Abstract:Community search is used to find a densely connected subgraph containing the given query
4、 vertex.Currently,most existing community search approaches do not consider the resource constraints and the attributes of the community,and they mainly focus on the structure of the community and cannot meet the personalized demands for users community search.For this problem,we propose size-constr
5、ained influential community search(SCIC).We design a baseline enumeration algorithm based on depth-first search.Further,we show three optimization techniques to reduce the redundant computation and accelerate the enumeration procedure,including node preprocessing,pruning rules and greedy strategies.
6、The experimental results on 10 real datasets with different sizes demonstrate that comparing with the existing algorithms,our baseline enumeration algorithm has better performance on community size and influence score.At the same time,the experimental results also show that our optimized algorithm c
7、an significantly improve the search efficiency and shorten the response time to 1%comparing with the baseline enumeration algorithm.Key words:data graph;community search;k-core;weighted graph;size-constrained community;influential community searchFoundation Item(s):National Natural Science Foundatio
8、n of Shanghai(No.20ZR1402700);National Natural Science Foundation of China(No.61472339,No.61873337)1引言社区是由紧密连接的结点构成的子图.在社交网络中，社区由积极互动的用户组成1，2；在万维网中，社区由主题相似的页面构成3.社区搜索的目的是寻找一个包含查询结点且结点紧密连接的子图.社区搜索关注局部网络结构，返回个性化的社区；例如：构建个性化研究小组4，蛋白质功能检测5等.目前，有两类社区搜索问题得到了广泛的关注.第一类是无结点数量限制的社区搜索问题，如：异构图上的社区搜索6、结点位置限制的社区搜
9、索7等.这类问题主要关注社区的紧密度，没有考虑到社区搜索中存在资源限制情况.第二类是结点数量受限的社区搜索问题，如：结点数量上界受限的社区搜索8、限制上下界的社区搜索9等.相较于无结点数量限制的社区搜索，这类问收稿日期：2022-08-29；修回日期：2022-09-29；责任编辑：覃怀银电子学报2023 年题考虑到了资源限制，但是与第一类社区搜索问题相似，仅考虑社区的结构特征，忽略了社区的属性特征10.例如，在构建服务集群问题中，除了需要考虑服务器数量和服务结点关联度两个因素之外，还需要考虑性能瓶颈因素才能构建最优服务集群.以上三个因素分别对应规模、结构以及属性约束，而现有社区搜索仅考虑前两
10、个因素，无法提供面向多约束问题的有效解决方案.本文针对现有社区搜索技术存在的问题，提出规模受限的影响力社区搜索（Size-Constrained Influential Community search，SCIC）问题.该问题不仅考虑了社区规模，还能够兼顾社区的结构特征和属性特征约束.在此基础上，本文设计了一种基于枚举的解决方案，并提出三种优化策略，包括结点筛选、剪枝策略以及贪心优化，从而可以高效求解满足结构、规模约束且影响力最大的有效社区.2背景知识和相关工作2.1背景知识给定无向图G=（VG，EG，），其中VG为结点集，EG为边集；：V R+表示图中结点到影响力的映射，（u）表示结点u的影
11、响力.结点u在图G中的邻居结点集合记作NG(u)=v|(uv)EG；结点u的度记作dG（u）=|NG（u）|.定义1 给定图G的子图S=（VS，ES，），S为G的诱导子图，则对uvVS(uv)ES，当且仅当(uv)EG.定义2 给定图G的诱导子图S=（VS，ES，），S的影响力inf（S）为S中所有结点影响力的最小值.定义3 给定图G的诱导子图S=（VS，ES，），S的最小度为S中结点的度的最小值，用minD（S）表示.定义 4 给定图 G=（VG，EG，），查询结点 qVG，内聚度阈值k，以及结点数量范围 l，h，若诱导子图S满足以下条件：（1）S 连通且包含查询结点 q；（2）l|VS|h
12、；（3）minD（S）k；则称S是一个可行社区.定义 5 给定图 G=（VG，EG，），查询结点 qVG，内聚度阈值k，以及结点数量范围 l，h，影响力最大的可行社区称为结果社区.值得注意的是，在可行社区集合中可能存在多个影响力相同的社区，因此结果社区不具有唯一性.问题定义（结点数量限制的影响力社区搜索）：给定图G=（VG，EG，），查询结点qVG，内聚度阈值k，以及结点数量范围 l，h，结点数量范围限制的影响力社区搜索SCIC从图G中找到查询点q的一个结果社区H.例1 考虑图1，设查询结点为v3，l，h =4，6，k=3.结点集合 v1，v2，v3，v4，v5 是一个可行社区，其影响力为20
13、；结点集合 v3，v5，v6，v7 是另一个可行社区，其影响力为70，同时该社区也是影响力最大的可行社区，因此它是结果社区.表1是本文内容涉及到的重要符号及其意义.2.2相关工作2.2.1结点数量范围限制的社区搜索目前，结点数量限制的社区搜索主要有两类算法：只限制结点数量上界的ES（Evolution Strategy）算法8以及同时限制结点数量上下界的 SC-BRB（Self-Centering Buckling-Restrained Brace）算法9.ES算法8分为向社区内添加结点的Expand算法以及从图 G 中删除结点的 Shrink 算法.ES 算法使用 ktruss11作为子图紧
14、密度模型，根据结点数量上界选择不同策略搜索符合条件的社区，并提出了一种结点紧密度计算方法.SC-BRB算法9能够解决同时限制社区数量上下界的社区搜索.该算法使用k-core12，13模型作为子图紧密度的衡量标准.在枚举社区的过程中，SC-BRB算法使用剪枝算法和贪心算法来提升查询效率.ES算法与SC-BRB算法都没有考虑图中结点的权值，因此无法作为SCIC问题的解决方案.2.2.2影响力社区搜索在影响力社区搜索的研究中，Li14提出了 DFS（Depth First Search）搜索算法以及离线的 ICP（Index Condition Pushdown）索引查询方法.DFS搜索使用了贪心思
15、想从图中迭代删除影响力最小的结点，直到返回影响力最大社区.ICP索引使用k-core模型对图进行分解13，建立从k=1到k最大的索引森林.查询时根据给定内聚度阈值k首先找到对应索引树；而后根据给定的查询结点，找到索引树中的节点及其子孙，由节点中的结点集合构成的诱导子图即为最终影响力最大社区.这些方法在SCIC问题中不具有可行性.除了上述两类社区搜索外，还有在异构图上进行社区搜索6、基于属性相似度的社区搜索10，15、基于空间的社区搜索7等问题.这些社区搜索问题在不同类v8v2v3v6v9v4v5v7v1206560809025957055图1结点带权的无向图G示例表1本文所用符号及其意义符号i
16、nf(G)(u)dG(u)NG(u)disG(u,v)意义图G的影响力结点u的影响力结点u在图G中的度结点u在图G中的邻居结点集结点u和结点v在图G中的最小距离1208第 5 期杜明:规模受限的影响力社区搜索型的图上，根据对应限制条件，搜索符合条件的子图.这些社区搜索问题没有考虑到结点数量限制以及影响力最大16的要求，因此不再详述.3基于状态的枚举算法针对SCIC问题，需要能够兼顾结点数量和社区影响力的算法.本文提出一种基于枚举的方法BasicEnum算法，其基本思想如下：使用深度优先搜索算法穷举社区的枚举状态，获得所有包含查询结点的子图，从子图集合中找到所有可行社区，并选择影响力最大的可行社区作为结果社区输出.算法1给出了BasicEnum算法的主要过程.第15行为算法的主流程，第 69 行展示了预处理流程，第1018行展示了BasicEnum算法的枚举过程：使用深度优先搜索穷举子图的构成状态.最后输出ResultC作为SCIC问题的最优解.算法将复杂的子图穷举转化为递归搜索枚举状态.枚举状态将VG划分为候选集C以及结果集R：候选集C表示后续枚举过程中可能加入社区的结点集合，R表示目
