论文部分内容阅读
社交网络可以用来描述现实社会中的实际网络,它包括人与人之间的社会关系,物种之间的捕食关系,科学研究中的合作关系等。大量研究已经表明在真实世界中各种不同的社交网络具有许多共同的结构特征,例如小世界性质、无标度性、社团结构等。而其中对于社团结构这一性质的研究受到了来各种学科的研究者的广泛关注,通过研究发现任一学科领域中各知识点、概念以及学科领域之间具有明显的层次关系,同一概念中的知识点、同一学科的概念等联系比较紧密,而与其它不同领域的知识联系比较稀疏。本文所研究的重点就是社团结构,它的性质可以帮助了解网络结构与分析网络特性,探测分析网络的社团结构对我们认识和理解真实复杂网络的结构以及功能有着重要意义。目前,已经有许多研究者投身到社团结构探测的研究当中并提出了各种各样的算法以便能够快速而准确的找到网络中的社团结构,比较经典的算法如GN算法,谱平分法,Kernighan-Lin算法等。但是划分社团的算法时间复杂度和准确性之间的矛盾仍然是大规模网络的社团结构分析面临的重要问题。在本文中,系统分析了已研究出的社团结构划分算法,比较了各几种算法的优缺点,在此基础上我们提出了两种改进的社团划分算法。本文主要做了以下几方面的工作:(1)研究了社交网络理论的基本知识,介绍了社交网络一些表示方法和一些基本概念,以后寻找社团划分算法奠定了理论基础。然后又介绍了几种比较经典的算法,并总结出了它们的优点和缺点。(2)利用相邻节点之间的距离差值构造了一种新的社团划分算法—基于相邻节点聚类的社团划分算法。首先要找到每个社团的初始聚类中心,以M个节点作为初始社团,计算与初节点距离最小的节点并入到相应社团中,以此类推直到网络中的所有节点都聚类到社团中,算法完成。把本文中的算法应用在网络实例上,通过检测本算法具有很高的正确率。(3)通过计算节点之间的相似性系数判断节点之间相似度,利用相似度大的节点在同一个社团的可能性大,相似度小的节点可能处于不同的社团来进行层次聚类。层次聚类按节点之间的相似性进行分组,采用自底向上的策略首先将每个节点作为一个社团,然后合并这些原子社团成为越来越大的社团,用模块度Q来判断在算法何时停止。本文的创新点:(1)相邻节点聚类的社团划分算法定义了相邻节点的距离差值,用这个参数定量的表示出了不同社团节点之间的差异程度。(2)把网络中的两个节点的相似度,层次聚类算法和模块度相结合构造了一种算法,这个算法有了较高的准确率。本论文提出的社团划分算法肯定还有许多不完善的地方,相关工作还有待进一步研究。