网络中的社区是指具有相似连接模式的结点组成的集合,好的社区发现算法需要考虑以下几点:一是算法划分社区的准确度要高,评价指标通常是算法划分结果与标准划分之间的相似度;二是算法的适用性要广,比如既可以发现传统的基于密度的社区,又可以发现基于连接模式的广义社区;三是算法的时间效率要尽可能高。由于大规模的网络往往较为稀疏,算法的时间复杂度要尽可能正比于网络中结点数或是边数。本文的研究方向是基于概率图模型的社区发现算法研究,用图模型解决社区发现问题首先是要对网络建模,即通过图模型解释网络的生成过程。传统的用于对网络建模的图模型大多存在局限,比如有些只能够发现基于密度定义的社区,有些算法的时间效率比较低等等。本文在模型的创新,算法的提出和改进上主要做了如下工作:1.创新地提出了一种基于泊松分布和伽马分布的图模型,模型假设网络中结点间的连接数服从泊松分布,结点在每个社区内的隶属度服从伽马分布。和传统的对网络建模的图模型相比,本文的模型可以更合理地解释网络中边的形成原因,并可以应用在广义的社区发现中。2.用吉布斯采样算法对模型中的变量进行推断,本文详细地推导了吉布斯采样的公式,并且从理论上证明了算法的时间复杂度随网络中的边数目正比增长,从而模型可以更好地适用于大规模稀疏网络。3.对算法从时间和空间的角度做了进一步优化,并将算法同时应用在了有向网络和无向网络中,同时创新地提出了一种处理网络中缺失数据的方法。本文通过实验验证了模型的准确性,并且在数据集中与一些传统图模型进行了对比,进一步验证了模型的优势。