二分网络社区挖掘的研究

发布时间：2017-10-04 10:18

  本文关键词：二分网络社区挖掘的研究

  更多相关文章： 复杂网络 社区结构 二分网络 单分网络 社区挖掘 二分模块度 社区划分

【摘要】：在自然界与人类社会活动中,各种复杂类型的系统都可以转化成相应的复杂网络,比如经济系统、生物系统、群体生态系统以及其他领域内系统。复杂网络分析领域的一个重要研究方向是社区结构及其社区挖掘。一个复杂网络的社区结构大致可描述为：在这个社区内部里,顶点连接比较紧密,而这个社区连接外部社区的联系是比较稀疏的。在结构上,一个社区往往是相对独立的,通常它们各自对应一些基本的功能单元。例如,在生物基因遗传网络中,一个社区往往包含具有类似功能的基因模块;在万维网中,一个社区对应着相同类型主题或者资源的网页。从复杂的网络中挖掘和分析这样的社区结构,为复杂网络的功能解析和揭示网络的组织原则提供了一种创新的研究方法。相对于单分网络,二分网络不仅是复杂网络中重要的表现形式之一,而且在现实社会复杂网络中具有普遍性,已经成为复杂网络的重要研究对象。在现实社会中,许多复杂网络都自然地呈现出二分结构。譬如：作者与文章的合作网络、演员与影视作品的合作网络、投资者与股份制公司的股份合作网络、疾病与基因的作用网络、俱乐部成员与俱乐部举办活动的参与网络、观众与歌曲的喜好网络、P2P系统中终端计算与交互数据的网络等。因此,二分网络社区挖掘对于研究复杂网络有非常重要的理论意义和实用价值。譬如,在学术圈的探测、功能分析、推荐系统、疾病诊断以及链接预测等方面都有很多重要的应用。在最近的二分网络社区挖掘研究中,学者们提出了许多的社区挖掘算法和二分模块度指标。为了评估网络社区挖掘结果的质量,Newman介绍了一种量化的方法,称为模块度。Guimera等人提出了一种基于同质顶点共同邻居的二分模块度,只针对一种类型的顶点划分的社区。Barber拓展了Newman的单分网络的模块度,提出了异质社区间一一对应的二分模块度,同时提出了adaptive BRIM算法用来社区挖掘通过最大化获得二分模块度。Murata基于Newman的单分网络模块度提出了异质社区间一对多关系的二分模块度,对于单分网络,该模块度和Newman的单分网络模块度一致。Suzuki和Liu Xin等人基于异质社区间多关系对应分别提出了两种不同的二分模块度。Raghavan等人介绍了一种标号传播算法用于社区挖掘。Murata还对标签传播算法(LPA)做了改进,提出一种更加适合二分网络的算法。同时,Murata等人提出了LPRRIM算法,该算法是对BRIM算法和LPA算法的整合和改进。针对二分网络社区挖掘的研究,本文中的主要工作以及研究成果有：(1)我们提出了基于蚁群优化的二分网络社区挖掘算法。首先,我们先将二分网络社区挖掘问题转化成二分网络顶点组合优化问题。其次,我们以蚁群优化算法为基础,结合二分网络的统计特性,重新定义了信息素和启发式信息,设计了新颖的蚂蚁觅食的社区划分模型。最后,我们选择适当的二分模块度衡量社区划分的质量。通过实验验证发现,我们的算法不仅准确地识别二分网络的社区个数,还可以获得很好的划分效果。该算法的另一个优点是它不需要预先制定社区的个数,而是在优化过程中形成最优的个数。(2)针对二分网络中多关系社区的挖掘问题,我们提出了一种多关系社区的二分网络社区挖掘算法。该算法以异质社区之间多对多对应关系为基础,以同类型顶点的共同邻居数作为启发式信息。该启发式信息表示同类型顶点的相似程度,以多关系异质社区的二分模块度为量化标准,结合蚁群优化策略进行二分网络社区挖掘,对二分网络进行多关系异质社区划分。通过实验验证发现,我们的算法能较准确地对实际二分网络进行多关系异质社区划分。(3)针对现有二分网络的模块度的局限性,我们提出了一种基于密度的二分模块度,用来量化二分网络社区结构划分的质量。在二分网络中,学者们根据对二分网络社区定义的不同理解,提出了多种二分模块度。然而,这些二分模块度往往取决于网络社区中连接的数量而忽略二分网络中顶点的数量,无法识别规模较小的社区结构,存在一定的局限性。我们通过几个数据集以及理论上和数学公式的逻辑证明,我们提出的基于密度的二分网络模块度不存在类似的局限性,还可以作为目标函数进行优化,也可归结为一个数值的非线性规划问题。通过实验验证发现,基于密度的二分模块度是非常可靠的和准确的。
【关键词】：复杂网络 社区结构 二分网络 单分网络 社区挖掘 二分模块度 社区划分
【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-6
• Abstract6-8
• 第一章 引言8-14
• 1.1 研究背景与意义8-10
• 1.2 研究现状10-12
• 1.3 研究内容与组织结构12-14
• 第二章 二分网络及其社区挖掘14-24
• 2.1 二分网络及其社区结构14-17
• 2.2 模块度17-20
• 2.3 二分网络的社区挖掘20-23
• 2.4 本章小结23-24
• 第三章 基于蚁群优化算法的二分网络社区挖掘24-35
• 3.1 二分网络的社区挖掘24-25
• 3.2 二分网络模块度25-26
• 3.3 蚁群算法26-27
• 3.4 算法的框架27-30
• 3.5 实验结果与分析30-34
• 3.6 本章小结34-35
• 第四章 多关系社区的二分网络社区挖掘35-48
• 4.1 多关系社区35-36
• 4.2 多关系社区的二分模块度36-38
• 4.3 算法的框架38-42
• 4.4 实验结果及分析42-47
• 4.5 本章小结47-48
• 第五章 基于密度的二分网络模块度48-70
• 5.1 二分网络模块度48-50
• 5.2 二分网络模块度的局限性50-55
• 5.3 基于密度的二分网络模块度55-56
• 5.4 可靠性与数值非线性规划问题56-61
• 5.5 二分模块度的对比61-62
• 5.6 实验结果及分析62-69
• 5.7 本章小结69-70
• 第六章 总结与展望70-72
• 6.1 研究总结70-71
• 6.2 研究展望71-72
• 参考文献72-76
• 致谢76-77
• 攻读学位期间发表的学术论文目录77-78

【相似文献】

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

1 徐永成;二分网络社区挖掘的研究[D];扬州大学;2015年

，

本文编号：970089