基于传播动力学的复杂网络社团检测方法研究

发布时间：2019-02-18 07:43

【摘要】：网络科学为解决现实生活中各种各样的复杂问题带来了新的视角。真实网络系统通常具有一些非平凡的拓扑特性,如重尾度分布、高聚集系数、同配异配性、社团结构和层级组织等。其中,社团结构是复杂网络最突出的特性之一,即网络中存在一些内部连接紧密的群组,而群组与群组之间的连接较为稀疏。社团结构的检测在物理学、生物学、社会学和计算机科学等领域具有重要的理论意义和广阔的应用前景,近年来吸引了很多不同领域研究者的关注。本文介绍了社团检测的基本概念和方法,探讨了聚类意义以及如何测试和比较各种方法,讨论了社团检测在真实网络中的应用,并深入研究了三种基于传播动力学的社团检测方法。具有创新性的研究成果有以下三个方面:1.基于网络随机游走动力学特征和信息熵最小化,提出了一种新的社团检测方法-LPAf。它基于以下思想:如果按照网络的社团结构对其节点进行二级编码,则网络上随机游走的平均描述长度(加权信息熵)将会显著减小。平均描述长度是网络划分的函数,对于同一个网络,较好的划分对应较短的平均描述长度。通过改进原始标签算法的多数投票规则,使平均描述长度在标签扩散过程中逐渐减小,可以精确且有效地检测社团结构。在合成网络和真实网络上的测试结果表明,LPAf具有较强的鲁棒性、较高的精确度,以及较低的时间复杂度。2.基于社团内节点互相相似且连接紧密的特征,提出了一种高效的多分辨率社团检测方法-MLPA。在MLPA中,相似的节点首先聚集到一起形成许多元社团。然后,这些元社团通过比较其内部凝聚力与外部吸引力,决定是否与其它元社团进行合并,这个过程一直进行直到所有元社团都满足定义。MLPA既不需要知道社团结构的任何先验信息,也不需要优化任何目标函数。在合成网络和真实网络上的测试结果表明,与其它几种流行的算法相比,MLPA具有较高的准确度和极低的时间复杂度。通过调节分辨率参数,可以观察不同尺度的社团,进而揭示网络的层级结构。为了进一步验证MLPA的有效性,利用它对大肠杆菌的转录调控网络进行了详细的分析,结果表明检测到的模块具有很强的结构和功能的一致性。3.基于局域标签传播过程,提出了一种高效的动态社团检测方法-ALPA。许多真实网络是随时间演化的,而传统方法将它们视为静态的,即通过聚合一段时间内的数据而构建的,这种处理方式会丢失网络及社团的演化信息。如果希望实时跟踪网络的社团,静态方法通常非常耗时,因为即使网络的结构发生极小的改变,它们也必须重新计算整个社团结构。网络演化愈快,静态方法的耗时缺陷愈发明显。与传统方法不同,ALPA通过一个局域的标签传播过程来更新当前的社团结构。局域的标签传播过程有效利用了社团结构的历史信息,因此通常只会影响网络中很小一部分节点,这使得ALPA能够快速地响应网络结构的变化。在合成网络和真实网络上的测试结果表明,ALPA能够成功地识别并且追踪动态网络中的社团。此外,和其它常用方法相比,ALPA拥有更高的准确度和更低的时间复杂度。
[Abstract]:......
【学位授予单位】：华中师范大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 刘微;张大为;嵇敏;谢福鼎;;基于共享邻居数的社团结构发现算法[J];计算机工程;2011年06期

2 刘晋霞;曾建潮;薛耀文;;复杂网络强社团结构探测[J];小型微型计算机系统;2011年04期

3 贾宁宁;封筠;;复杂网络的社团结构发现[J];河北省科学院学报;2013年02期

4 宣照国;苗静;党延忠;刘建国;;科研领域关联网络的社团结构分析[J];上海理工大学学报;2008年02期

5 王伊蕾;王远志;李涛;田生文;;伪度优先演化网络的社团结构研究[J];计算机工程与应用;2009年20期

6 汪小帆;刘亚冰;;复杂网络中的社团结构算法综述[J];电子科技大学学报;2009年05期

7 司夏萌;刘云;丁飞;熊菲;;具有社团结构的有界信任舆论涌现模型研究[J];系统仿真学报;2009年23期

8 谢军;;复杂网络中分析社团结构算法研究概述[J];信息通信;2010年04期

9 朱大勇;张新丽;李树全;;利用局部拓扑信息发现模糊社团结构[J];电子科技大学学报;2011年01期

10 邵斐;蒋国平;;基于社团结构的负载传输优化策略研究[J];物理学报;2011年07期

相关会议论文 前6条

1 苗清影;汪小帆;;基于社团结构的复杂网络可控性研究[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

2 李晓佳;张鹏;狄增如;樊瑛;;复杂网络中的社团结构[A];第四届全国网络科学学术论坛暨研究生暑期学校论文集[C];2008年

3 胡延庆;赵尔波;张丹;狄增如;樊瑛;;社团结构的局域和自适应比较性定义及其相应探测方法[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

4 吴文涛;肖仰华;何震瀛;汪卫;余韬;;基于权重信息挖掘社会网络中的隐含社团[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

5 樊瑛;李梦辉;张鹏;吴金闪;狄增如;;权重对网络结构和性质的影响——社团结构中权重的作用[A];2006全国复杂网络学术会议论文集[C];2006年

6 郑伟;王朝坤;刘璋;王建民;;一种基于随机游走模型的多标签分类算法[A];NDBC2010第27届中国数据库学术会议论文集A辑一[C];2010年

相关博士学位论文 前10条

1 程建军;复杂网络中的社团检测方法研究[D];兰州大学;2015年

2 李琳;基于多元统计分析的社团挖掘算法研究[D];上海交通大学;2014年

3 王文军;飞机驾驶舱人机工效设计与综合评估关键技术[D];西北工业大学;2015年

4 崔耀祖;基于复杂网络边的密度探索社团结构算法研究[D];大连理工大学;2016年

5 谢家荣;复杂网络中基于已知分组的社团探测方法[D];中国科学技术大学;2017年

6 武志昊;复杂网络中的重叠社团发现问题研究[D];北京交通大学;2013年

7 韩继辉;基于传播动力学的复杂网络社团检测方法研究[D];华中师范大学;2017年

8 魏芳;基于图挖掘的网络社团结构发现[D];复旦大学;2008年

9 刘传建;复杂网络中的社团结构划分及分析应用[D];山东大学;2014年

10 何东晓;复杂网络社团结构发现方法研究[D];吉林大学;2014年

相关硕士学位论文 前10条

1 刘微;复杂网络中社团结构的发现[D];辽宁师范大学;2011年

2 王大军;基于标签传播的社团检测算法研究[D];辽宁大学;2015年

3 杨强;微博社交网络模型的建立及其性质研究[D];北京化工大学;2015年

4 付世海;基于社团结构的网络多传播源定位算法研究[D];东北大学;2013年

5 马骁骑;复杂网络中社团检测技术研究[D];黑龙江大学;2015年

6 张献鹏;基于P4结构的社团挖掘方法[D];西安电子科技大学;2014年

7 陈奔燕;复杂网络的社团探测[D];湘潭大学;2015年

8 杜梅;基于半监督的社团结构发现方法研究[D];合肥工业大学;2014年

9 董哲;复杂网络中的社团发现算法研究[D];解放军信息工程大学;2014年

10 王彭;基于地理位置的网络加权化社团发现算法[D];东北大学;2014年

，

本文编号：2425625