复杂网络社团结构探测方法及社团内节点层次关系研究.pdf

《复杂网络社团结构探测方法及社团内节点层次关系研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、复杂网络社团结构探测方法及社团内节点层次关系研究庞垠2015年6月中图分类号：TP391.1UDC分类号：004.62复杂网络社团结构探测及社团内部节点层次关系研究作者姓名庞垠学院名称计算机学院指导教师李侃教授答辩委员会主席涂序彦教授申请学位工学博士学科专业计算机科学与技术学位授予单位北京理工大学论文答辩日期2015年6月CommunityDetectioninComplexNetworksandTheHierachicalRelationshipofTheCommunityCandidateName:YinPangSchoo

2、lorDepartment:SchoolofComputerFacultyMentor:Prof.KanLiChair,ThesisCommittee:Prof.XuyanTuDegreeApplied:DoctorofEngineeringMajor:ComputerofScienceandTechnologyDegreeby:BeijingInstituteofTechnologyTheDateofDefence：June，2015研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作获得的研究

3、成果。尽我所知，文中除特别标注和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。签名：日期：北京理工大学博士学位论文摘要社团结构普遍存在于复杂网络中，社团结构探测是复杂网络分析的重要内容。准确地找到网络中的社团结构可以更好地了解复杂网络特征、理解网络功能以及寻找隐藏模式。复杂网络可以分为整体网络和二部网络两类结构特征不同的网络。然而，目前的研究方

4、法通常针对某一种网络类型进行社团结构探测，或者根据网络结构类型来选择不同的参数进行社团探测。在网络结构特征未知条件下，无法进行社团探测。因此，本文提出一种能量理论来衡量整体网络和二部网络节点间关系，建立能量模型，它同时适用于整体网络和二部网络。能量模型研究社团数已知的和未知的非重叠、重叠社团探测方法，以及社团内部节点层次结构探测方法，可以解决模块化等方法中普遍存在的分辨率极限问题以及重叠社团探测方法无法识别社团中大部分节点为重叠节点的问题。本文分析了社团定义，提出了基于复杂网络结构特征的能量理论，它可同时衡量整体网络和二部网络

5、节点间关系。任意两个节点间存在正能量和负能量两种能量，节点间能量为节点间正能量与负能量之和，能量越大，性质越相似，越趋于在同一个社团。针对如何在社团数已知情况下进行社团探测问题，提出社团数确定的非重叠社团探测方法。给定社团数，利用能量矩阵的特征值和特征向量，为每一个节点确定能量矢量用于计算社团内的最大能量。特别地，利用能量矩阵最大特征值对应的特征向量能直接确定两个社团的划分结果。实验表明，不同于传统的根据网络结构类型选择社团探测方法，确定个数的非重叠社团探测方法可以在网络结构未知情况下进行两个或两个以上社团探测。针对如何确定稳

6、定社团结构问题，提出能量最大化的非重叠社团结构探测方法。通过确定正能量大于0的节点，寻找性质相似的节点，并将与一个节点能量最大的节点加入到该节点所在社团中。实验证明，能量最大化的非重叠社团探测方法无需事先确定社团个数，并同时适用于不同的网络类型。针对社团内节点重要性问题，提出社团内节点排序分层方法。通过确定社团内中心节点，按照节点在社团内归属系数排序进行某个社团内层次结构探测。实验表明，社团内部节点分层比传统的寻找整个网络中心节点并进行层次划分更有意义，社团内I北京理工大学博士学位论文节点分层方法能够解决非重叠社团探测方法中可

7、能出现的分辨率极限问题，并且避免了面对整个网络的传统层次结构算法计算效率低的问题。针对节点具有多个社团性质问题，提出基于节点能量的重叠社团探测方法。根据节点与非其所在社团的能量关系和连接关系，按照社团内层次结构探测方法中的归属系数从低到高排序，可以迅速找到网络中重叠节点。实验表明，不同于传统的重叠社团探测方法，基于能量理论的重叠社团探测方法在社团中大部分甚至所有节点都是重叠节点情况下可以进行准确社团探测，将所有具有相同性质的节点划分在同一社团中。关键词：复杂网络；社团结构探测；非重叠社团；重叠社团；层次结构II北京理工大学博士

8、学位论文AbstractCommunitystructureiswidespreadincomplexnetworks.Communitydetectionisanimportantanalysisdirectioninthecomplexnetwork.Findingcom