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

发布时间：2017-11-03 17:33

  本文关键词：社会网络的邻域重叠社团划分

  更多相关文章： 社团划分 派系 模块度 划分密度 时间复杂度

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

【相似文献】

中国期刊全文数据库 前10条

1 饶正婵;范林柏;;基于二分排序法时间复杂度的求解过程[J];铜仁学院学报;2011年03期

2 武鹏;李美安;;具有O(n)时间复杂度的分布式请求集生成算法[J];计算机应用;2013年02期

3 隆永红;;关于在W签名方案中伪造签名的时间复杂度[J];通信保密;1993年01期

4 李之棠,程鹏,李汉菊;时间复杂度为O(N)的联接算法[J];计算机工程与科学;1997年01期

5 明仲;利用双堆栈降低时间复杂度的新算法[J];深圳大学学报;1998年Z1期

6 殷超;;删除值相同元素的时间复杂度的改进算法[J];科技信息;2011年21期

7 霍锡真;网络灵敏度的拓扑分析和算法的时间复杂度[J];电子学报;1992年02期

8 余新国,黄文奇,赖楚生;多元整系数多项式因式分解（Ⅱ）——关于时间复杂度算法的讨论[J];华中理工大学学报;1996年S2期

9 黄杰;运用简化法则估算算法的时间复杂度[J];雁北师范学院学报;2000年04期

10 战俊伟;李美安;裴喜春;申二威;;基于时间复杂度优化的分布式互斥请求集生成算法[J];微计算机信息;2010年27期

中国重要会议论文全文数据库 前1条

1 宋旭东;纪秀花;;稳定婚姻问题的研究[A];全国第19届计算机技术与应用（CACIS）学术会议论文集（下册）[C];2008年

中国重要报纸全文数据库 前1条

1 陈智罡;算法复杂度的分析方法及其运用[N];中国电脑教育报;2002年

中国硕士学位论文全文数据库 前10条

1 李仁杰;零抽样断点距离的一个改进算法[D];山东大学;2015年

2 黄磊;WSN中基于时间信道的溯源数据安全节能传输[D];江苏大学;2016年

3 任成磊;社会网络的邻域重叠社团划分[D];华东师范大学;2016年

4 李彬;三个图修改问题的固定参数可解算法研究[D];山东大学;2013年

5 马振宇;加权分治技术在Set Packing问题中的应用与研究[D];中南大学;2007年

6 郝勇;计算生物学中有关基因组移位—删除排序问题的研究[D];山东大学;2011年

7 吕旭光;基因组断点标本字符串联提取算法[D];山东大学;2011年

8 朱泓丞;设施选址问题的研究与应用[D];中国科学技术大学;2009年

9 申佳丽;复杂网络节点影响力及影响力传播相关问题研究[D];燕山大学;2015年

10 许宝亮;用于异常检测的进化非选择算法性能分析[D];中国科学技术大学;2010年

，

本文编号：1137250