复杂网络是一种拓扑特征极其复杂的网络,它的元素之间的连接方式既不是随机的也不具有非常明显的规律。许多现实世界的网络,例如交通运输网络、社会交际网络和基因调控网络,都是非常复杂的。复杂网络的研究是一门年轻且有活力的科学研究领域,引起了学者们的的极大关注。社团结构是众多现实网络中共有的特性,也是复杂网络中最重要的特征结构之一。社团结构通常对应实际网络中的功能模块,比如网络中具有相同主题的网页或者代谢网络中的微循环模块。因此研究复杂网络中的社团结构具有很大的应用价值。为了探索复杂网络中的社团结构,学者们从不同的角度提出了很多划分效果很好的算法。常见的社团结构划分方法有基于相似度度量的凝聚算法、基于信息论的算法、基于主成分分析的最大化模块性的算法等。本文基于相似度度量的方法,通过构造节点之间的相似度,利用节点的属性,判断两个节点是否属于同一个社团,提出了两种新的社团结构划分算法:(1)基于节点相似度的社团划分算法。首先针对RA度量方法的缺点提出了改进的节点相似度的计算方法;其次结合无权无向图的特点提出了基于凝聚思想的社团结构划分算法;最后利用准确率和模块度作为衡量社团划分效果优劣的标准。通过用一些真实网络对算法的性能进行评估,结果表明,本文算法能准确的划分复杂网络中的社团结构。(2)基于节点相对距离的社团结构划分算法。首先基于NGD(normalized Google distance),改进了计算节点相对距离的方法。然后借鉴聚类思想筛选出核心节点集。最后,基于相对距离对余下节点进行划分,直至社团结构划分完成。通过模块度、F值和标准化互信息三个标准对算法进行评价,与其它算法相比,该算法划分结果较好,同时该算法的时间复杂度也较低。综上所述,本文是基于相似度度量,通过定义节点之间的相似度的计算方式来发现复杂网络中的社团结构。两个节点之间的相似度越大,属于同一个社团的概率越大,本文利用节点之间的相似性,提出了基于节点相似度的社团划分算法。