改进的节点覆盖方法在社团划分中的研究

发布时间：2020-07-11 14:19

【摘要】：复杂网络存在于世界上各个角落,深入研究复杂网络的结构特性具有十分重要的应用前景。社团结构是复杂网络的重要性质之一,近年来,划分复杂网络中的社团结构受到了各个领域学者们的广泛关注,并迅速成为了热门研究方向之一。本文针对基于节点覆盖的社团划分(Community Detection Based On Node Coverage,NCA)算法存在的不足,主要做了以下工作:(1)首先介绍了复杂网络的研究背景和意义,阐述了研究复杂网络的重要性,然后介绍了复杂网络的国内外研究现状和复杂网络相关的理论知识,并详细分析了一些经典的复杂网络社团划分算法的优缺点。(2)研究基于层次覆盖的社团发现算法,针对NCA算法需要预知网络全局拓扑结构的问题,本文算法采用了随机挑选初始节点的方法,降低了算法的复杂度;针对网络中没有直接相连节点之间的相似性问题,本文算法引入了 RA(Resource Allocation)算法,RA算法是一种基于资源分配的算法,该算法能够更准确的计算节点间的相似度,预测节点之间隐藏的规律。(3)针对NCA算法会遇到异常节点的问题,本文算法增加了判断条件,通过比较节点之间的拓扑结构信息来判断节点是否能增加社团的紧密性,在划分过程中,会将异常节点找出,并对它们做出准确判断。实验结果表明,相比经典算法和NCA算法,基于层次覆盖的社团发现算法不用预知网络中的聚类核心,使得本文算法能够应用于大规模网络中。另外,RA算法的引入和判断条件的增加,都提高了社团划分的准确性,使得到的社团结构更加紧密。
【学位授予单位】：西安理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;TP301.6
【图文】：

节点模,出度,节点,源节点

图 2-2 一个简单的节点模型图Fig.2-2 Asimple node model节点对可能是不同的出发节点和目的节值即节点的入度和出度，出度是源节点如下：outi ijjk a度定义为指向该节点的边的数量，用ini jijk a 的度值ik 可以用公式(2.6)表示：out ini i ik k k同类型的节点度分布，了解节点的度分

示意图,聚类系数,示意图,社交

图 2-3 一个简单网络示意图ig.2-3 Schematic of a simple netwo 5 个节点和 5 条边，即 N 3，由公式(2.9)可知该网络的密程度，聚类系数越大的网见，尤其在社交网络中表现的识。设某网络中节点i的度数数可以定义为：2( 1)iSCk k 络中，聚类系数的定义是这 11NiiC CN

规则网络,复杂网络

即 C 1，当网络为各个节点互无连接时， C 0，网络的聚类系数表明了网的拓扑结构特征，即网络不是完全随机的网络。1.3 复杂网络结构特征在现实世界里，复杂网络在人们身边随处可见【56】。比如用网络中的边代表关注者与关注者之间的关系，那么就会构成一个个体的社交网络；人体本身是由各类元素组成边来表示各类元素之间的关系，这就构成了能够表示人体本身的复杂网络；如果将蚁王其它蚂蚁之间的关系用边表示，那么会得到一个蚂蚁的种群网络。下面介绍复杂网络的构特征。则网络在复杂网络理论中，规则网络是一种相对简单的网络模型，该网络模型中的节点连接很有规律，它的拓扑特性也相对好分析，根据网络中节点之间的连接情况，规则网络可分为：全局耦合网络、最近邻耦合网络和星形网络，如图 2-4 所示是三种规则网络的模图：

【相似文献】