基于变粒度的三支决策社团发现研究
发布时间：2021-09-28 05:53
现实生活中普遍存在着各式各样的复杂系统,它们都能够用不同的复杂网络来表示,例如万维网、社交网络和城市道路交通网络等。在这些复杂网络中,都存在一个重要的结构特性,即社团结构,它是指网络由多个社团组成,社团内部的节点联系紧密而社团之间的节点联系相对稀疏。挖掘复杂网络中的社团结构对于复杂网络的研究和分析具有十分重要的意义。复杂网络中的社团结构根据社团中是否含有重叠节点可以分为重叠社团结构和非重叠社团结构,与重叠社团结构相比,非重叠社团结构在一些实际应用中更有助于分析网络的潜在规律和功能。因此,对非重叠社团结构的发现具有重要的现实意义和应用价值。由于在社团发现过程中经常会出现重叠社团,为了获得非重叠的社团结构,需要对社团的重叠部分进行有效地划分。三支决策（TWD）为解决不确定性问题提供了思路,它拓展了传统的二支决策理论。与传统的二支决策相比,三支决策增加了第三种不承诺决策（或延迟决策）作为信息不足以做出接受或拒绝决策时的决策行为。三支决策将一个论域划分成三个部分:正域、负域和边界域,划分在正域中的对象采取接受决策,划分在负域中的对象采取拒绝决策,划分在边界域中的对象采取延迟决策。对于边界域中的...
【文章来源】：安徽大学安徽省 211工程院校
【文章页数】：60 页
【学位级别】：硕士
【部分图文】：
图2.1两种方法的层次聚类过程
第二章相关理论知识10（1）将两个社团的重叠部分节点定义为边界域，即=∩；（2）将社团的非重叠部分节点定义为正域，即=∩；（3）将社团的非重叠部分节点定义为负域，即=∩。在上述定义中，正域和负域只是相对的概念，也可以将社团的非重叠部分节点定义为负域，社团的非重叠部分节点定义为正域。图2.2给出了重叠社团中三个域的划分示例。由图可知，边界域为图中阴影部分节点，即={8,9}，正域为社团的非重叠部分节点，即={5,6,7}，负域为社团的非重叠部分节点，即={1,2,3,4}。对于边界域中的节点，通过进一步挖掘网络中更多的信息后，再对其进行二次划分，最终实现了网络的非重叠社团发现。因此，如何对边界域中的节点进行划分（即边界域的处理方法）是该类方法重点研究的问题。图2.2重叠社团中三个域的定义Figure2.2Thedefinitionofthreeregionsinoverlappingcommunities2.3社团发现的评价指标模块度和标准化互信息是两种常用的社团发现评价指标。复杂网络分为社团结构未知和社团结构已知两种情况，模块度常用于评价社团结构未知的网络，标准化互信息常用于评价社团结构已知的网络。而这两种情况下的网络，都可以用模块度进行评价。2.3.1模块度模块度函数（Modularity）[1]是由Girvan和Newman在2004年提出来的，它用来定量地评价网络中社团结构划分的优劣。模块度是最常用的社团发现评价指标，它适用于所有的复杂网络，许多算法都是在该指标的基础上提出来的。模块度的定义如下所示：=12∑[2],(,)(2.1)
安徽大学硕士学位论文179：for=1:do10：′←()；11：′←′+{′}；12：endfor13：计算′中每一层的值；14：′←找出最大值所对应的层；15：输出′；16：endif算法3.2VGHC算法流程Algorithm3.2TheflowdiagramofalgorithmVGHC综上所述，为了获得更好的分层效果，本章提出了一种基于变粒度层次聚类的社团发现方法（VGHC）。该方法首先以重要节点为粒子中心构造初始粒子，然后选择下层的中值聚类系数作为聚类阈值，这样下层就可以聚类到上层，最后以扩展的模块度（）为衡量标准，在层次结构中选择某一层作为目标层。由于聚类机制的原因，目标层中存在一些重叠社团。为了获得非重叠的社团结构，利用三支决策思想对目标层中的重叠社团进行三支定义，再采用局部模块度优化方法对边界域中的节点进行划分，最终实现非重叠社团发现。图3.1展示了所提方法的整体框架（以空手道俱乐部网络示例）。图3.1空手道俱乐部网络的划分过程Figure3.1ThepartitionprocessofKarateclubnetwork
【参考文献】：
期刊论文
[1]基于商空间的多层粒化社区发现方法[J]. 段震,闵星,王倩倩,陈洁,张燕平,赵姝. 南京大学学报(自然科学). 2017(04)
[2]基于三支决策的非重叠社团划分[J]. 方莲娣,张燕平,陈洁,王倩倩,刘峰,王刚. 智能系统学报. 2017(03)
[3]复杂网络中的层次结构挖掘[J]. 余成进,赵姝,陈洁,张燕平,段震. 南京大学学报(自然科学). 2016(05)
[4]Tolerance Granulation Based Community Detection Algorithm[J]. Shu Zhao,Wang Ke,Jie Chen,Feng Liu,Menghan Huang,Yanping Zhang,Jie Tang. Tsinghua Science and Technology. 2015(06)
[5]基于主题与三支决策的文本情感分析[J]. 王磊,黄河笑,吴兵,郑任儿. 计算机科学. 2015(06)
[6]基于聚类粒化的社团发现算法[J]. 赵姝,柯望,陈洁,张燕平. 计算机应用. 2014(10)
[7]人脸识别中的多粒度代价敏感三支决策[J]. 张里博,李华雄,周献中,黄兵. 山东大学学报(理学版). 2014(08)
[8]基于局部探测的快速复杂网络聚类算法[J]. 金弟,刘大有,杨博,刘杰,何东晓,田野. 电子学报. 2011(11)
[9]粒计算未来发展方向探讨[J]. 张钹,张铃. 重庆邮电大学学报(自然科学版). 2010(05)
[10]粒计算研究现状及基于Rough逻辑语义的粒计算研究[J]. 刘清,孙辉,王洪发. 计算机学报. 2008(04)
本文编号：3411363
【文章来源】：安徽大学安徽省 211工程院校
【文章页数】：60 页
【学位级别】：硕士
【部分图文】：
图2.1两种方法的层次聚类过程
第二章相关理论知识10（1）将两个社团的重叠部分节点定义为边界域，即=∩；（2）将社团的非重叠部分节点定义为正域，即=∩；（3）将社团的非重叠部分节点定义为负域，即=∩。在上述定义中，正域和负域只是相对的概念，也可以将社团的非重叠部分节点定义为负域，社团的非重叠部分节点定义为正域。图2.2给出了重叠社团中三个域的划分示例。由图可知，边界域为图中阴影部分节点，即={8,9}，正域为社团的非重叠部分节点，即={5,6,7}，负域为社团的非重叠部分节点，即={1,2,3,4}。对于边界域中的节点，通过进一步挖掘网络中更多的信息后，再对其进行二次划分，最终实现了网络的非重叠社团发现。因此，如何对边界域中的节点进行划分（即边界域的处理方法）是该类方法重点研究的问题。图2.2重叠社团中三个域的定义Figure2.2Thedefinitionofthreeregionsinoverlappingcommunities2.3社团发现的评价指标模块度和标准化互信息是两种常用的社团发现评价指标。复杂网络分为社团结构未知和社团结构已知两种情况，模块度常用于评价社团结构未知的网络，标准化互信息常用于评价社团结构已知的网络。而这两种情况下的网络，都可以用模块度进行评价。2.3.1模块度模块度函数（Modularity）[1]是由Girvan和Newman在2004年提出来的，它用来定量地评价网络中社团结构划分的优劣。模块度是最常用的社团发现评价指标，它适用于所有的复杂网络，许多算法都是在该指标的基础上提出来的。模块度的定义如下所示：=12∑[2],(,)(2.1)
安徽大学硕士学位论文179：for=1:do10：′←()；11：′←′+{′}；12：endfor13：计算′中每一层的值；14：′←找出最大值所对应的层；15：输出′；16：endif算法3.2VGHC算法流程Algorithm3.2TheflowdiagramofalgorithmVGHC综上所述，为了获得更好的分层效果，本章提出了一种基于变粒度层次聚类的社团发现方法（VGHC）。该方法首先以重要节点为粒子中心构造初始粒子，然后选择下层的中值聚类系数作为聚类阈值，这样下层就可以聚类到上层，最后以扩展的模块度（）为衡量标准，在层次结构中选择某一层作为目标层。由于聚类机制的原因，目标层中存在一些重叠社团。为了获得非重叠的社团结构，利用三支决策思想对目标层中的重叠社团进行三支定义，再采用局部模块度优化方法对边界域中的节点进行划分，最终实现非重叠社团发现。图3.1展示了所提方法的整体框架（以空手道俱乐部网络示例）。图3.1空手道俱乐部网络的划分过程Figure3.1ThepartitionprocessofKarateclubnetwork
【参考文献】：
期刊论文
[1]基于商空间的多层粒化社区发现方法[J]. 段震,闵星,王倩倩,陈洁,张燕平,赵姝. 南京大学学报(自然科学). 2017(04)
[2]基于三支决策的非重叠社团划分[J]. 方莲娣,张燕平,陈洁,王倩倩,刘峰,王刚. 智能系统学报. 2017(03)
[3]复杂网络中的层次结构挖掘[J]. 余成进,赵姝,陈洁,张燕平,段震. 南京大学学报(自然科学). 2016(05)
[4]Tolerance Granulation Based Community Detection Algorithm[J]. Shu Zhao,Wang Ke,Jie Chen,Feng Liu,Menghan Huang,Yanping Zhang,Jie Tang. Tsinghua Science and Technology. 2015(06)
[5]基于主题与三支决策的文本情感分析[J]. 王磊,黄河笑,吴兵,郑任儿. 计算机科学. 2015(06)
[6]基于聚类粒化的社团发现算法[J]. 赵姝,柯望,陈洁,张燕平. 计算机应用. 2014(10)
[7]人脸识别中的多粒度代价敏感三支决策[J]. 张里博,李华雄,周献中,黄兵. 山东大学学报(理学版). 2014(08)
[8]基于局部探测的快速复杂网络聚类算法[J]. 金弟,刘大有,杨博,刘杰,何东晓,田野. 电子学报. 2011(11)
[9]粒计算未来发展方向探讨[J]. 张钹,张铃. 重庆邮电大学学报(自然科学版). 2010(05)
[10]粒计算研究现状及基于Rough逻辑语义的粒计算研究[J]. 刘清,孙辉,王洪发. 计算机学报. 2008(04)
本文编号：3411363
本文链接：https://www.wllwen.com/guanlilunwen/lindaojc/3411363.html
