检索结果-南通市图书馆

复杂系统与复杂性科学 2016年第1期13卷 102-106,110页

作者：任成磊韩定定蒲鹏张嘉诚华东师范大学信息科学技术学院上海200241

基于当前复杂网络中社团划分算法普遍存在算法复杂度过高以及重叠节点挖掘不准确的局限性,提出了一种高效、快速、准确的社团划分算法。基于贪婪算法,建立最大模块度矩阵,并采用堆数据结构,划分非邻域重叠社团。通过分析局部网络的连边... 详细信息

基于当前复杂网络中社团划分算法普遍存在算法复杂度过高以及重叠节点挖掘不准确的局限性,提出了一种高效、快速、准确的社团划分算法。基于贪婪算法,建立最大模块度矩阵,并采用堆数据结构,划分非邻域重叠社团。通过分析局部网络的连边情况,计算邻域社团的划分密度,以准确挖掘社团间的重叠节点。新算法经过仿真分析和实证研究表明,算法复杂度降到近线性。

关键词：社团挖掘邻域重叠模块度划分密度时间复杂度

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

基于连边相似度的重叠社区发现算法研究

引用

计算机应用研究 2013年第1期30卷 221-223页

作者：施伟傅鹤岗张程重庆大学计算机学院重庆400044

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,... 详细信息

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。

关键词：社区发现重叠社区相似度划分密度

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

社会网络的邻域重叠社团划分

社会网络的邻域重叠社团划分

引用

作者：任成磊华东师范大学

学位级别：硕士

在复杂系统中,邻域重叠社团是网络普遍存在的一种特性。因为邻域重叠社团可以直观形象地揭示网络内部的组织结构以及各个社团之间的关系,所以邻域重叠社团的探测研究对网络拓扑结构的分析、功能的理解以及动力学行为的预测等有着重要的... 详细信息

在复杂系统中,邻域重叠社团是网络普遍存在的一种特性。因为邻域重叠社团可以直观形象地揭示网络内部的组织结构以及各个社团之间的关系,所以邻域重叠社团的探测研究对网络拓扑结构的分析、功能的理解以及动力学行为的预测等有着重要的意义。目前,大多数的邻域重叠社团划分算法时间复杂度较高,难以准确地实现网络的社团划分。针对以上问题,本文主要贡献如下：1.提出了一种改进型派系过滤算法,通过优化派系搜索过程,加快网络邻域重叠社团划分。基于网络中的完全子图,通过缩小节点搜索范围,采用由大到小、迭代回归的方式挖掘网络中的派系,快速地实现网络的邻域重叠社团划分。将改进型派系过滤算法应用到模拟网络和实证网络中,准确地实现了网络的邻域重叠社团划分。2.基于社团的划分测度,提出了一种时间复杂度近线性的邻域重叠社团划分算法。首先,利用堆数据结构,通过更新模块度增量矩阵,合并使网络模块度值增益最大的社团,完成社团成员矩阵的初始化;其次,逐条分析网络中的连边,结合划分密度,准确地挖掘网络中的重叠节点;最后,将基于社团划分测度的邻域重叠社团划分算法应用到模拟网络中,检验算法的准确性,并从理论上分析算法的时间复杂度近线性。3.选取经典的社会网络数据集,验证基于社团划分测度的邻域重叠社团划分算法的准确性与高效性。基于社团划分测度,对已知社团结构的空手道俱乐部网和海豚网进行社团划分,实验结果与实际情况一致,证实了算法的准确性;对未知网络结构的悲惨世界角色网和科学家合作网进行社团划分,实验结果揭示了网络内部拓扑特性,反映了小说主要人物的作用以及科学家之间的合作模式。通过分析以上四个网络的耗时情况,发现新方法可以快速地实现网络的邻域重叠社团划分。

关键词：社团划分派系模块度划分密度时间复杂度

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

复杂网络中层次重叠社区发现算法研究

复杂网络中层次重叠社区发现算法研究

引用

作者：施伟重庆大学

学位级别：硕士

社区结构是复杂网络研究中最近被发现的一个重要特征。社区是指根据网络中节点之间的关系，将关系密切的节点划分为一个群组。社区内部节点连接紧密，而社区之间节点连接稀疏。社区结构能够更加形象地组织网络，使得研究真实的网络更具... 详细信息

社区结构是复杂网络研究中最近被发现的一个重要特征。社区是指根据网络中节点之间的关系，将关系密切的节点划分为一个群组。社区内部节点连接紧密，而社区之间节点连接稀疏。社区结构能够更加形象地组织网络，使得研究真实的网络更具有实际意义，并为研究网络的群体特征提供了有效的理论依据。许多真实网络的社区结构通常呈现出层次结构和重叠结构，即：一个大的社区可以细分为多个小的社区，一个节点由于多重作用同时属于多个社区。在社会网络中，社区的层次和重叠结构尤为明显。传统的复杂网络社区发现算法是以节点集为研究对象，采用层次聚类算法较好地发现社区的层次结构，但是，该算法较难发现社区的重叠结构。为此本文从另外一个角度出发，以网络的连边集为研究对象，将原网络图转换为以连边为节点的线图，从而将节点社区转换为连边社区。对线图采用层次聚类算法构建线图的层次树状图，树中每一层对应线图的社区结构，从而发现网络社区的层次结构。聚类过程使得原图中每一条连边只属于一个独立社区，而一个节点可以与多条连边关联，因此可以使得某些节点可能同时属于多个社区，从而进一步发现社区的重叠结构。本文目的在于同时发现社区的层次结构和重叠结构，提出了一种基于线图节点相似度的层次重叠社区发现算法。社区发现过程分为三个步骤： ①将网络原图转换为线图，给出节点相似度的定义及计算公式，针对线图节点提出了节点广泛邻居的概念，用于计算线图节点的相似度，并进一步推广到加权网络图对应线图的节点相似度。 ②依据线图节点相似度采用single-linkage方法进行凝聚层次聚类，构建线图的层次树状图。 ③经典的衡量节点社区的模块度标准对于以连边社区不再适用，因此本文针对连边社区，根据社区内部连边的密度，提出了一种基于连边密度的划分密度函数，用来划分层次树状图，评估最终的社区结构的质量，寻找出最优的社区。除此之外，本文最后采用了真实数据集进行实验，并分析了实验结果。实验结果表明本文提出的基于线图节点相似度层次重叠社区发现算法，可以很好的发现社区的层次结构和重叠结构，且与Newman快速算法和CPM算法实验结果进行对比可得：本文算法在发现社区层次结构和重叠结构的性能及效果上更好，准确度与Newman算法相当，比CPM算法要高。此外，在算法时间复杂度上也有明显改进，一定程度上解决了传统算法效率低下的问题。

关键词：网络社区层次结构重叠结构相似度划分密度

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：