社区是一组内部紧密连接的结点,用于描述对象间存在的密切关系。社区搜索是在图上寻找一个符合查询条件且结点紧密连接的子图。例如在科研社交网络中组建个性化科研小组,在服务网络搭建中构建高性能服务器集群等等。目前大部分社区搜索问题从社区的结构角度开展研究,这类传统问题主要关注社区的紧密度,没有考虑到社区搜索中存在的资源限制情况以及社区的属性特征。针对上述问题,本文研究规模受限的影响力社区搜索问题,具体研究内容如下:首先,本文定义了规模受限的影响力社区搜索问题:给定内聚度阈值与结点数量上下界,搜索符合条件的影响力最大稠密子图;并提出了基于枚举的基础方法——Basic Enum算法。其基本思想是通过深度优先搜索算法枚举所有可能的社区,将复杂的枚举过程转化为搜索树构建过程。此外,针对基础算法冗余枚举多、时间效率差的问题,提出了预处理方法与剪枝优化。预处理方法通过社区直径公式删除不参与搜索的结点,减少枚举次数;剪枝优化则通过多样的剪枝规则减小搜索树的宽度,提升搜索效率。其次,提出基于贪心思想的搜索策略来降低搜索树深度,在此基础上设计了右子树约减以及结点选择策略来提升效率。右子树约减通过减少递归搜索的分支,减少遍历右子树的次数,从而降低递归的深度;结点选择策略通过结点权重公式,优先向社区加入权重较大结点,可以更快找到影响力最大的社区,降低搜索树的深度。最后,本文基于10个真实带权数据集进行实验,将社区的规模、影响力以及查询响应时间作为评价指标,对比已有的Greedy D算法、Greedy F算法、SC-BRB算法以及本文提出的Basic Enum算法和优化后GRE算法。实验结果表明,相较于传统社区搜索算法,本文提出的算法能够缩短响应时间,提升搜索效率。