现实世界中的很多信息都是以网络的形式存在,比如人际交往关系网、生物学中的蛋白质网、论文著作中的合作关系网等等。社区结构是复杂网络中的一个重要特征,它可以揭示社会网络的隐藏规律和行为特征。和社区结构密切相关的社区检测问题被提出后就成为国内外学者的研究热点,和社区检测相关但不相同的社区搜索问题是本文所研究的问题。社区搜索就是输入一个图和一个查询顶点,然后找到包含这个查询节点的一个密集子图。首先,本文针对非属性图的社区搜索问题,提出了三角图密度的概念,在三角图密度的基础上,本文介绍了一种发现社区的新方法即基于三角图的密集子图问题(简称TGDS)。给定一个输入图,其三角图是根据输入图构建的新图,其中新图的每个顶点对应于输入图的一个三角形,并且如果输入图中有两个三角形共享同一条边,那么在新图中的两个顶点之间就有一条边。本文定义了三角图密度函数的概念,目的是为了提取一个高质量的子图,而这个高质量的子图就代表一个社区。其次,本文针对属性图中的社区搜索问题提出了一个查询属性函数的概念,用于计算图中每个顶点属性的属性值。属性社区搜索是输入一个图,一个查询节点和一组查询属性,会得到包含这个查询节点及这个节点属性的一个子图,并且这个子图中的每个节点都含有查询属性。然后再根据前面计算的每个顶点的属性得分来删除得到的子图中属性分数值少的节点,最后得到的这个子图就是我们所需要的社区。