论文部分内容阅读
现实世界中的各种关系均可以抽象成不同的网络形式,如社交网、合作网、生物网等。而社团结构是复杂网络具有的重要结构特性之一。社团将网络中具有相似功能或属性的节点划分在一起,每个社团内部的节点之间连接相对紧密而社团间的连接比较稀疏。根据网络中节点间的相互关系将具有紧密联系的节点划分在一起的过程称之社团划分。社团划分后根据是否含有重叠节点可以将其分为重叠社团和非重叠社团。面对特定应用场景,非重叠社团结构更有助于发现社团内存在的规律,并预测网络的行为和功能,如:电子商务中的商品推荐、广告精准投放等。然而在社团划分过程中,往往会形成重叠的社团结构,因此,如何将社团重叠部分划分到单个社团,从而获取非重叠社团结构具有重要的应用价值和广泛的应用前景。三支决策(3WD)将传统的二支语义决策拓展为三支决策,增加了一个不承诺决策,也就是说,在信息不充分的情况下人们能够采取不承诺决策的方式进行决策,即延迟决策。三支决策理论中的正域中的对象代表对事物做出接受决策;负域中的对象代表对事物做出拒绝决策;而边界域中的对象代表对事物做出延迟决策。延迟决策将通过引入更多信息,对边界域中的对象进行二次划分,进一步做出接受决策或拒绝决策,从而实现最终的二支决策。这种三支决策的方式与人类的认知方式相似,是现实生活中解决实际决策问题常用的策略之一。三支决策模型在各个学科领域中都有广泛应用,尤其适用于处理不确定、不完整信息的分析判别,通过延迟决策,能够更好地分析和解决这类问题。目前诸多的社团划分算法从不同角度和应用层面实现了非重叠社团划分,并取得了一定的研究成果。本文采用层次粒化社团划分方法获取非重叠社团。但是层次粒化划分社团过程中会出现重叠部分社团,重叠部分社团的出现往往因为当前重叠节点信息量不足无法决定其归属。因此本文将三支决策思想应用于重叠节点划分的研究中,针对层次粒化过程中出现的重叠部分社团进行三支划分,最终获得非重叠社团结构。本文的主要工作如下:1、本文首先对非重叠社团划分算法的研究意义和国内外研究现状进行了阐述,重点分析了基于层次粒化获取社团结构的优势以及存在的问题。然后对三支决策理论的提出、发展、应用进行了简要概述,并给出了将三支决策思想引入层次粒化社团划分获取非重叠社团结构的意义。2、针对层次粒化后出现的重叠节点的处理,本文提出基于归属度的三支决策社团划分算法(DB-TWD)获取非重叠社团结构。该算法将三支决策思想引入到社团划分处理问题的研究中,针对层次聚类形成的有重叠的社团结构,将两个存在重叠的社团的左边社团中非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。然后,针对边界域中的节点,分别计算边界域中节点与正域和负域的社团归属度BP,BN进行三支划分。对于三支划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属,最终获得非重叠的社团结构。实验结果表明该算法可以合理地划分非重叠社团结构,相较于其他对比算法能获得较高的模块度值。3、针对DB-TWD算法形成的初始粒子结构松散问题,本文提出了基于局部子图信息的三支决策社团划分算法(LSI-TWD)。该算法通过节点的局部信息构建初始粒子。在初始粒化阶段,以一个节点为中心,找出该中心点的邻居集合,将邻居集合中有可到达边的节点划分在一起从而形成子社团。经过局部信息初始化后出现的子社团充分考虑了初始粒子的结构信息,获得的子社团内部节点联系更为紧密,更符合实际情况。然后在层次粒化社团划分算法的基础上,结合三支决策思想对重叠部分节点进行划分获得的非重叠社团的结构更为合理,模块度值更高。