复杂网络社区结构划分算法研究

大连理工大学硕士学位论文复杂网络社区结构划分算法研究姓名：张娜申请学位级别：硕士专业：运筹学与控制论指导教师：郭崇慧20090622://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/://info.3dou.com/复杂网络社区结构划分算法研究作者：张娜学位授予单位：大连理工大学相似文献(10条)1.期刊论文胡健.董跃华.杨炳儒.HUJian.DONGYue-hua.YANGBing-ru大型复杂网络中的社区结构发现算法-计算机工程2008,34(19)在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值.该文把超图模型以及基于此的聚类算法应用到社区结构发现的领域.对于简单图的社区结构发现,引入边聚集系数的概念,提出基于边聚集系数的社区发现算法.将安然邮件数据集作为测试数据集,通过算法对比分析,证明该算法在时间复杂度上可以提高一个数量级.2.学位论文张亮复杂网络增长模型及社区结构划分方法2008近年来，随着WS小世界网络模型和BA无标度网络模型的提出，国内外掀起了研究复杂网络的热潮。复杂网络的研究以系统学的观点来看待真实系统，如Internet网络、电力网、新陈代谢网络等。这些大规模网络在社会系统中的广泛存在，促使人们对这些网络的拓扑结构以及网络上发生的动力学行为展开了广泛的研究。本文采用PageRank算法的思想对复杂网络的增长模型进行了研究，并从多元统计分析的角度来探讨了复杂网络中社区结构的分析方法。主要工作如下：1.提出了一种基于PageRank算法的网络模型。经典的BA无标度网络模型在考虑网络的优先链接机制时，主要把节点的度作为确定链接概率的决定性因素，而忽略了网络结构中的其它一些关键信息的影响。而Google搜索引擎的良好性能表明，PageRank比度能更好地刻画节点在网络中的重要性。本文基于Google搜索引擎的PageRank的概念，并以节点的PageRank值为标准来确定优先链接的概率，从而建立了新的增长网络模型并分析了该模型的性质。数值模拟结果表明，该模型能很好地反映实际网络中的一些重要性质。2.提出了一种新的复杂网络社区结构分析方法。揭示复杂网络中的社区结构，对于了解网络结构与分析网络特性有重要意义。将一个网络划分为几个不同的社区，其本质也就是在一定程度上最大化提取网络本身的主要信息，同时略去一些相对次要的信息。主成分分析(PrincipleComponentAnalysis，PCA)方法，正是这样一种从事物中提取主要信息，而忽略相对次要信息的多元统计分析方法。本文从PCA的思想出发，提出了一种分析复杂网络社区结构的新方法，并将其应用于分析空手道俱乐部网络(Zachary网络)、海豚网络(Lusseau网络)等网络的社区结构。数值实验结果表明：文中提出的方法是可行且有效的。3.期刊论文巩军.刘鲁.周里.GONGJun.LIULu.ZHOULi基于IRC日志的分享型社区结构的研究-计算机工程与应用2008,44(23)用户为导向的在线分享型社区近几年发展迅速,而这些社区与以文字信息为基础的传统社区有较大的不同.利用IRC音乐频道从2001年到2006年的用户日志数据,构建了此共享型社区的用户网络.在对此网络的特点分析之后,将该网络的结构由有向的加权图转换为单向的二部图,从而利用层级聚类的方法,对网络中的用户群落进行了发掘.在此基础上,进一步分析了用户群落的大小,形状和分布的情况.最后根据研究的结果,提出了针对该社区提高服务的方法.4.学位论文王旭涛基于复杂网络的病毒传播和社区查找研究2007复杂网络研究正渗透到数理学科、生命学科和工程学科等众多不同的领域，对复杂网络的研究已成为网络时代科学研究的一个极其重要的挑战性课题。近年来随着计算机技术快速发展和网络应用范围越来越广泛，对复杂网络的研究已提出了更高的要求。目前，复杂网络的研究已在复杂网络的拓朴结构及建模、复杂网络中的同步等方面取得了不错的进展，但是在这些方面仍然存在许多问题有待解决。本文针对其中的（1）权值网络建模问题上，（2）scale-free网络中的病毒传播问题，（3）复杂网络中的社区分析与查找问题行了研究。本文的主要贡献包括以下几个方面：（1）进一步分析了复杂权值网络的演化机制，并建立了一个新的数据模型，使其不仅能反映网络拓朴和权值动态增加对网络演化过程的影响，而且也能够反映网络中权值动态减少对网络演化过程影响。（2）针对网络中不同的节点对病毒入侵的抵抗力不同，且越重要的节点其保护措施越完善，因而拥有更强的抵抗力这一现象，改进了病毒传播模型，使其能够反映这一现象，并对此模型进行了详细的研究，得出了一些有用的结论。（3）提出了一个运用网络局部信息分析网络的社区结构的算法。此算法不仅能够为任一给定节点抽取其在网络中所属的社区结构，而且能够分析整个网络的社区结构，并取得了不错的效果。（4）改进了（3）中提出的算法，使其保留它的优点但极大的降低了算法的时间复杂度，使其分析整个网络的社区结构时所花费的时间代价近似与网络的规模呈线性增长关系，因而能够应用于大规模的网络中。本文在计算机模拟的网络和现实网络上做了大量的实验，结果表明能够很好的解决本文所提出的问题，并得到比较好的效果。5.期刊论文郭崇慧.张娜.GUOChong-hui.ZHANGNa基于共邻矩阵的复杂网络社区结构划分方法-系统工程理论与实践2010,30(6)提出了一种基于共邻矩阵和增益函数的划分算法来发现复杂网络中的社区结构.共邻矩阵中元素的含义为结点对之间拥有相同邻居的数目.以增益函数作为网络社区结构划分的目标函数,进一步推导出基于增益矩阵和增量矩阵的特征值和特征向量的社区结构划分方法.最后把这种算法应用于三个常用的实际网络数据中,并和Newman基于模块度矩阵的谱算法结果做了比较,以验证该算法的可行性和有效性.6.期刊论文郭崇慧.张亮.GUOChong-hui.ZHANGLiang基于PCA的复杂网络社区结构分析方法-运筹与管理2008,17(6)揭示复杂网络的社区结构,对于了解网络结构与分析网络特性有重要意义.将一个网络划分为几个不同的社区,其本质也就是在一定程度上最大化提取网络本身的主要信息,同时略去一些相对次要的信息.主成分分析(PrincipleComponentAnalysis,PCA)方法,正是一种从对象中提取主要信息,而忽略相对次要信息的多元统计分析方法.本文基于PCA的信息压缩思想,提出了一种分析复杂网络杜区结构的新方法,并将其应用于分析空手道俱乐部网络(Zachary网络)、海豚网络(Lusseau网络)、政治书籍网络(Krebs网络)等网络的社区结构,并且与基于模块度矩阵的谱方法划分结果进行了比较,数值实验结果表明本文提出的方法是可行且有效的.7.期刊论文王林.戴冠中.WANGLin.DAIGuan-zhong基于复杂网络社区结构的论坛热点主题发现-计算机工程2008,34(11)社区结构是复杂网络的重要特征之一,该文通过构造基于兴趣的论坛用户网络,成功地将社区结构发现的理论与方法应用于论坛热点主题的自动发现,提出了极大社区的概念和反复挖掘极大社区的方法,发现网络结构和论坛主题在反复挖掘过程中均几乎保持不变.仿真结果表明,提取效果令人满意.8.学位论文李耀华基于复杂网络结构特征的股市研究2009复杂网络理论是近几年新兴起来的研究热点，其应用性研究也具有广泛的领域，金融证券市场就是复杂网络的一个重要研究领域。始于2007年的美国次贷危机引发了国际性的金融危机，导致国际股市普遍暴跌，并且严重影响了实体经济的发展。为促进经济增长，包括中国在内的世界各国政府采取了不同的经济刺激措施，这使得股市在金融危机与经济刺激下变化无常。为了进一步研究国际金融危机的发生，并给投资者以具体的科学性的投资指导，在此，我们利用复杂网络的理论方法做了以下工作：br　　1.当前有不少专家利用复杂网络来研究股市，但都是研究具体某一股市的内部结构或指数动力学，还没有人从国际角度出发，对国际股市问的关系进行研究。应该相信各国股市间是存在一定关系的。在国际金融危机发生的今天，本文以国际股市为研究对象，以各国股市为网络节点，通过各股市代表性指数波动的相关性，分别利用阈值法和MST算法，建立了各国股市之间的网络模型。通过分析所建网络的结构特征和抗毁性，并对网络进行社区划分，以从股市网络的角度来研究分析当前金融危机的爆发。通过对所建立的各股市间的三重最小生成树网络研究分析，并利用Matlab编程进行模拟仿真，发现该国际股市网络对随机攻击具有鲁棒性，对蓄意攻击则显示出脆弱性，且具有明显的社区结构。通过利用改进的GN算法对网络进行社区划分，发现国际股市网络中的社区结构与当前世界经济发展区域化特征相吻合。最后利用中心化指标对沪市在国际股市网络中所处的位置进行了分析，发现沪市与国际股市网络之间的相互影响力比较弱。br　　2.在股市走向不确定性增强，投资股市风险增大的情况下，通过计算各股票价格波动的相关性，分别利用阈值法和MST算法建立了沪市股票间的网络模型。通过逐步提高阈值，发现网络最大连通子网的规模随阈值的提高而变小，组成网络的子网数目和孤立节点数目也随之增大。并挖掘出了股票网络的核心子网，为获得稳定收益，根据“不把鸡蛋放在一个篮子里”的分散风险的投资原理，给出投资者投资股市的具体建议。然后利用Matlab编程进行模拟仿真，通过对股票间的三重最小生成树网络进行抗毁性分析，发现沪市的股票网络对随机攻击具有鲁棒性，而对蓄意攻击显示出脆弱性。9.期刊论文戴飞飞.唐普英.DAIFei-fei.TANGPu-ying基于PSO微粒群算法的复杂网络社区结构发现-计算机工程与应用2008,44(22)复杂网络社区结构划分日益成为近年来复杂网络的研究热点,到目前为止,已经提出了很多分析复杂网络社区结构的算法.但是大部分算法还存在一定的缺陷,而且有些算法由于其时间复杂度的过高导致其不适合应用于对大型网络的分析.提出了一种基于PSO微粒群算法的复杂网络社区结构分析方法.此方法无需预先知道组成该复杂网络的社区数量、社区内的节点数以及任何门限值.该算法的可行性用ZacharyKarateClub和CollegeFootballNetwork模型进行验证.10.学位论文任伟复杂网络中的社区结构研究及其扩展2009近年来，对于复杂网络的研究已经成为数学、计算机、物理等多学科交叉的热点研究领域之一。通过研究发现，复杂网络具有一些重要的性质比如小世界性质(SmallWorld)、度序列幂率分布(Power-LawDistribution)、具有高的聚系度(HighClust