现实生活中普遍存在着各式各样的复杂系统,它们都能够用不同的复杂网络来表示,例如万维网、社交网络和城市道路交通网络等。在这些复杂网络中,都存在一个重要的结构特性,即社团结构,它是指网络由多个社团组成,社团内部的节点联系紧密而社团之间的节点联系相对稀疏。挖掘复杂网络中的社团结构对于复杂网络的研究和分析具有十分重要的意义。复杂网络中的社团结构根据社团中是否含有重叠节点可以分为重叠社团结构和非重叠社团结构,与重叠社团结构相比,非重叠社团结构在一些实际应用中更有助于分析网络的潜在规律和功能。因此,对非重叠社团结构的发现具有重要的现实意义和应用价值。由于在社团发现过程中经常会出现重叠社团,为了获得非重叠的社团结构,需要对社团的重叠部分进行有效地划分。三支决策(TWD)为解决不确定性问题提供了思路,它拓展了传统的二支决策理论。与传统的二支决策相比,三支决策增加了第三种不承诺决策(或延迟决策)作为信息不足以做出接受或拒绝决策时的决策行为。三支决策将一个论域划分成三个部分:正域、负域和边界域,划分在正域中的对象采取接受决策,划分在负域中的对象采取拒绝决策,划分在边界域中的对象采取延迟决策。对于边界域中的对象,通过获取足够的信息后再对其完成最终的决策。三支决策的决策方式更符合人类的决策模式,在现实生活中有很好的适用性,如医疗诊断、文本分类、电子邮件信息过滤等方面得到广泛应用。近年来,一些基于三支决策的非重叠社团发现算法被提出,这类方法在处理重叠社团方面具有一定的优势,但仍然存在两方面的问题,分别为层次聚类过程中社团的合并问题和边界域节点的划分问题。针对这两方面问题,本文提出了基于变粒度的三支决策社团发现方法。本文的主要工作如下:1、针对层次聚类过程中社团的合并问题,本文提出了基于变粒度层次聚类的社团发现方法(VGHC)。该方法首先利用变粒度层次聚类构建网络的层次结构,然后以扩展的模块度为衡量标准选取目标层。根据三支决策理论,对目标层中的重叠社团进行三支定义,即将社团的非重叠部分定义为正域或负域,社团的重叠部分定义为边界域。再利用局部模块度优化方法对边界域中的节点进行划分,最终实现非重叠社团发现。在公用数据集上的实验结果表明,该方法能够获得更好的分层效果,且得到的非重叠社团结构质量较高。2、针对边界域节点的划分问题,本文提出了基于随机游走边界域处理的社团发现方法,该方法包含随机游走和加权随机游走两种方式来对边界域部分进行有效地划分,分别为基于随机游走的三支决策社团发现算法(RW-TWD)和基于加权图表示的三支决策社团发现算法(WGR-TWD)。对于RW-TWD算法,首先根据VGHC算法获取目标层,然后在目标层上结合三支决策思想对边界域中的节点利用随机游走算法进行划分,得到最终的非重叠社团结构。对于WGR-TWD算法,首先也是根据VGHC算法获取目标层,然后根据目标层的社团划分信息给网络的边添加权重,对加权后的网络进行网络嵌入,得到网络中所有节点的向量表示,最后在目标层上结合三支决策思想对边界域中的节点利用余弦相似度进行划分,从而获得非重叠社团结构。实验结果表明所提的两种算法均取得了较好的性能。