现实世界的网络里自然地包含了很多社团结构,它们已经成为网络系统中一个重要的统计特征。例如,在社会网络中,它们可能代表着一组俱乐部成员;生物网络里,或许是一组功能相关的基因组;在语意网络中,它们是一些与某个主题相关的网页。通常来讲,社团结构是一些联系紧密的实体,结构内部节点之间的联系相对网络中其它节点更紧密。如何高效地挖掘出这些结构对理解和分析网络结构来说是一个很重要的问题。尽管在网络社团的发现方面已经取得不少研究成果,但仍然存在许多问题有待解决。比如,有些算法的效率不是很高,社团结构的度量机制不够完善;很少有工作去关注重叠的社团结构,虽然重叠的结构在现实的网络中更普遍存在,也更能反映出真实世界的本质。针对这些问题,本文借助一些经典的算法来产生社团结构的种子,然后以拓展种子的方式来挖掘网络中重叠和非重叠的社团结构。本文的主要贡献如下:1.结合多层次策略,文中运用经典的图谱划分方法产生了种子集合,并对种子的特征进行了分析。多层次策略使得算法在计算最粗糙图的Fiedler向量时具有很好的划分速度;谱平分方法帮助算法过程找到很好的图划分线索。这些种子集合抓住了社团结构的主体,反映出了目标社团的特征,具有很好的性能。在真实的网络数据上,文中也对种子选取的合理性做出了验证。2.运用种子拓展的方式提出了一种新颖的社团识别算法。该算法基于模块函数和节点的传递概率。模块函数是由Newman和Cirvan来定义的,它已经成为度量社团结构的一种主流标准。算法用它的改变值来评估新扩展节点对当前种子集合的贡献。传递概率在算法中被用来推断相邻节点之间的联系,反映扩展到新节点的权重。传递概率的源头是种子集合中节点的初始概率(初始权重)。新节点得到的概率决定了计算节点贡献值的次序,贡献值又决定了节点是否具有进一步扩展的机会。第4章对算法过程做出了详细的描述,同时也对扩展过程中节点的删除操作和扩展步上逃逸的概率做出了分析。3.对网络中普遍存在的而又很少被关注的重叠社团结构,文中提出一种识别算法。对解决重叠问题,它开辟了一条新的途径。该算法仍然基于种子扩展。在得到种子集合之后,算法结合随机行走技术给出了一种合理的扩展过程,它用时间步来刻化。在扩展的每个时间步,算法首先计算出所有标准化后的节点概率。按照概率值的降序,所有的节点依次被扫描。然后,确定哪些节点在接下来的时间步里作进一步的扩展。通过节点扫描,算法还要对新扩展的节点作出是否为当前的种子集合贡献者的判断。这些判断主要用于寻找候选社团在当前时间步最优的结构。运用贡献节点的性质,文中给出了一些定理。基于性质定理,一些无用的扩展节点在寻找候选社团的最优结构时可以被安全地删除。扩展过程执行上述步骤直到社团结构之间的重叠率超过了用户的忍受范围或者到达了随机扩展的收敛时间。第5章不仅介绍了算法步骤,也对扩展过程给出了理论分析。分析表明,提出的方法使得候选社团在每个时间步上都能找到最优的结构,基于懒惰随机行走的整个扩展过程也能给种子集合带来好的扩展结构。4.在六个网络数据集上,对上述提出的算法作出了验证。数据集来自真实的网络,规模大小不等,内容涉及多个领域。在实验分析上,文中从多个角度运用多种机制来评估算法。评估内容包括种子选取方式上的对比,算法与相关工作的比较以及时间分析等。对重叠的社团结构,还给出了在著名的网络里发现的实例。实验结果表明文中提出的方法具有一定的优越性,同时也证明了重叠方式对识别完善的社团结构是非常重要的,让大家认识到重叠社团在真实网络中的研究意义。综上所述,本文针对网络中的社团发现问题提出了几种新算法。这些算法采用了种子扩展的方式,扩展过程基于随机行走技术,扩展结构选用了模块函数来度量。文中用理论分析和大量的实验验证了这些算法。结果表明提出的方法能识别出结构完善的社团结构,具有很好的性能。