复杂网络中的社区内部结构研究

发布时间：2018-04-04 23:04

本文选题：复杂网络　切入点：社区结构　出处：《山东大学》2017年博士论文

【摘要】：许多真实系统,比如工程中的电力网络,生物学中的基因调控网络,像Facebook 一样的社会网络等,都可以用图或者网络来描述,其中节点代表一个实体,若两个实体之间有联系则连一条边。复杂系统不是随机的,而是有许多局部的或者整体的特征。一个重要的特征就是许多网络中都存在的社区结构,即社区内部节点连接稠密,社区与社区之间连接稀疏。社区结构是一个非常重要的性质,因为他们形成了网络的功能模块。例如,社会网络中的各个群体拥有他们自己的标准、方向和文化。在一个细胞中,一些蛋白质相互作用形成了蛋白质复合体发挥它们的作用。我们的主要研究对象就是复杂网络中的社区结构,尤其是内部结构。本文总共分为六章,第一章为绪论,简单介绍了复杂网络的相关概念及主要研究方向,尤其是社区结构。第二章至第五章为文章的主体部分,也是本文的主要创新点。第六章中我们首先对我们所做的工作做了总结,其次给出了在我们的研究基础上还有哪些问题值得进一步研究。首先,我们引入领导者社区与自组织社区的概念,并研究了社区中领导者节点的重要作用。社区结构对于复杂网络的特性及动力系统起着重要的作用。然而,据我们所知,很少有学者对社区的内部结构进行研究。本文第二章中,我们用十种社区划分算法对二十种真实世界网络进行社区划分,发现大部分社区内都含有少数几个领导者,即几个度数特别大的节点。我们用一个统计参数,即方差,来区分领导者社区与自组织社区。其中,领导者社区内部含有几个度数特别大的节点,几乎连接了社区中其余节点;而自组织社区是指社区内部节点的度数都差不多,不存在哪个节点在社区中具有控制作用。我们发现,在社会网络及引文网络中,领导者社区要多于自组织社区。在领导者社区内,我们定义度数最大的前10%的节点为领导者节点。在我们的实验中,我们将领导者节点去掉之后,社区内部的连边数平均意义上减少了 40%,社区与社区之间的边数平均意义上减少了 20%以上。另外,社区的平均聚类系数有所下降。这些现象说明,领导者节点在保持社区稠密与聚类中起着重要作用,并且,领导者节点相对于其他节点更倾向于与其他社区连边。最后,我们发现在几种随机网络上可以得到相似的结果并给出了一个删除了领导者节点社区内部边丢失的理论下界。我们的研究为社区内部结构的研究与应用提供了新的思路。其次,我们提出一种新的指标,即度方差比ρ,用来准确区分复杂网络中的领导者社区与自组织社区。不久前,领导者社区与自组织社区已经被提出来,可以用来研究社区的生成机制。然而,如何有效识别自组织社区与领导者社区在技术上还是一个挑战,因为目前还没有一个很好的度量可以区分两种社区。我们提出一种新的度量,称为度方差比,来区分两种社区结构,并给出了一个随机模型来解释我们的度量的合理性。通过在多个真实世界网络中以及在多个社区划分算法下的实验,我们验证了用度方差比来识别自组织社区与领导者社区的有效性与稳定性。我们发现社会网络与引文网络中的领导者社区要多于自组织社区,而在技术网络如电力网络中自组织社区要多于领导者社区。另外,我们的结果还显示自组织社区的节点个数往往要小于领导者社区的节点个数。该项工作为研究社区的内部结构与社区的生成机制提供了新的思路。再次,我们研究了社区与社区之间的关系。社区结构和核与外围结构是复杂网络的两个普遍存在的特征,两种结构的独立研究都已有十几年的历史,但是很少有学者将两者结合起来研究。我们首先探索了社区中的核与外围结构,提出一种在社区内部划分核与外围的线性时间算法,即将一个社区划分成一个内部连接稠密的核与一个内部连接非常稀疏的外围。基于社区内部的核与外围结构,我们定量分析了社区之间的连边并提出两种社区关系,即统一化与多极化。两个社区被称为是统一的如果两个社区的连边中核与核之间的连边多于外围与外围之间的连边,否则两个社区被称为是多极化的。我们还提出了一种随机模型,称为广义的GN(Girvan-Newman)模型,不仅可以生成社区是多极化的社区网络,还可以生成社区是统一化的社区网络。该项工作也为研究网络的多核与多外围结构提出了一个新的思路。最后,我们也给出一种划分社区的算法。社区结构发现对于理解社会学、生物学、工程技术领域的真实世界网络的结构和动力系统是非常关键的一步。我们提出一种深度随机模型,并基于非负矩阵分解得到一种新的社区划分算法。该模型中含有两组参数,一组是社区成员矩阵,它的一行中的每个元素代表这个节点分别属于每个社区的概率;另外一组是社区-社区连接矩阵,第i行第j列元素代表分别从i社区与j社区中随机取一个节点,它们之间有连边的概率。这两组参数可以通过一个有效的迭代算法得到,并且该迭代算法是收敛的。我们算法中的社区-社区连接矩阵比传统的基于非负矩阵分解的算法的社区-社区连接矩阵要更加精确。另外,非负矩阵分解算法可以看成我们模型的一种特殊情况。最后,在人造网络与真实世界网络上面的实验验证了我们算法的有效性。
[Abstract]:......
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】