在位置社交网络（Location-Based Social Network,LBSN）中,邻居节点搜索问题是一个基本问题,并且已被学者们广泛研究。然而现有的大多数工作在进行此类查询时只关注节点本身的地理位置属性,而忽视了用户之间的社交关系。研究表明,在更多情况下,用户更倾向于和关系亲近的人参与某些社会活动,例如:相比于单独出行,用户更喜欢与朋友一起去酒吧或购物。出于这个考虑,本文提出了基于位置社交网络的邻近社区搜索问题。邻近社区搜索是帮助人们组织社交活动的重要手段,在广告投放、组织聚会等场景具有很大的市场应用潜力,但同时该课题面临了以下两个挑战:海量数据问题和动态数据问题。针对上述问题,本文提出了三种算法:基于指数扩张的局部搜索算法、基于剪枝策略的局部搜索算法和近似搜索算法,以此来提高社区搜索的效率,提升用户体验。第一,提出了基于位置的社交网络的NCS问题,针对NCS问题提出了一种局部搜索策略,并设计了一种实现该搜索方法的算法NCSLocal。与全局搜索算法不同,局部搜索算法不需要遍历整张图就能完成搜索任务,从而大大提高搜索效率,此外,NCSLocal算法采用了指数扩张的策略,以查询节点为中心逐步扩大搜索范围,该方法可以快速确定搜索范围,从而帮助我们更快地找到邻近社区。最后,本文对算法进行了详细的时间复杂度分析。第二,在NCS问题的基础上,又对空间紧密度提出了要求,提出了NGCS问题。通过一种局部搜索策略来解决NGCS问题,并设计了一种实现该搜索方法的NGCSProgressive算法。通过观察我们发现,在NGCS问题中,所有的目标社区只可能存在于某个受限区域内,于是我们利用剪枝的思想,巧妙地避开了无用的网络空间,通过缩小搜索范围从而提高算法的搜索效率。最后,本文对算法进行了了详细的时间复杂度分析。第三,在算法NGCSLocal的基础上,为了提高效率本文提出了另外一种解决NGCS问题的高效的近似算法,即NGCSApproximate,该算法用规格为γ*γ的网格根据节点的位置进行划分,并巧妙地设计了一个搜索近似最小覆盖圆的方法,通过二分搜索的思想快速确定最小覆盖圆,解决了NGCSProgressive算法的痛点,在牺牲了一定精确度的情况下极大地提高搜索的性能和效率。最后,本文对算法进行了了详细的时间复杂度分析。真实社交网络上的广泛实验结果表明了我们算法的有效性,也证明了我们提出的搜索方法的算法明显优于基础算法。