基于复杂网络的社区发现算法研究

《基于复杂网络的社区发现算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于复杂网络的社区发现算法研究CommunityDetectionAlgorithmBasedonComplexNetwork学科专业：信息与通信工程作者姓名：徐珮轩指导教师：金志刚教授天津大学电气自动化与信息工程学院二零一七年十一月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表

2、示了谢意。学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）摘要摘要通过复杂网络的社区发现研究可以揭示复杂网络结构特点和一些网络现象的成因，发现其隐含模式、预测其行为，在社会网、生物分子网和互联网中具有广泛应用价值。但由于复杂网络种类繁多且结构复杂，降低了算法的普适性和划分结果的准

3、确性；网络的动态变化也会破坏原本社区结构，重新划分社区结构会产生大量的计算开销。因此在保证精度的同时提高算法效率是该领域迫切解决的技术难题。本文基于社区发现算法的研究现状，首先提出了一种密度峰值聚类的自适应社区发现算法KDED，其基于密度峰值聚类思想，保证高效性，结合热扩散模型增加自适应性；针对于网络动态变化的场景，本文提出了一种基于局部增量的动态社区发现算法D-KDED，其基于短时平滑性假设，使用增量式算法思想对社区进行划分，降低时间开销。实验结果表明，本文提出的KDED算法，在真实数据集和人工数据集上均具有非常高的模块度指

4、标，此外可以在社区结构比较模糊的稀疏网络具有出色的社区划分结构，同时在对比的几种算法中具有最高的稳定度和准确率；在动态场景下，本文提出的D-KDED算法在真实的动态网络中具有较好的模块度指标和最高的计算效率，在网络结构稀疏的大型网络中可以有效发现社区结构，同时具有最低的时间开销。关键词：社区发现，复杂网络，自适应，密度峰值聚类，增量式IABSTRACTABSTRACTThecharacteristicsofcomplexnetworkstructureandthecausesofsomenetworkphenomenacanb

5、erevealedthroughthestudyofcommunitydiscoveryincomplexnetworks,andfindingitsimplicitmodelandpredictitsbehaviorhavewideapplicationvalueinsocialnetwork,biomoleculenetworkandInternet.However,duetothecomplexandcomplexstructureofthenetwork,theuniversalityofthealgorithmand

6、theaccuracyoftheresultsarereduced.Thedynamicchangesofthenetworkwilldestroytheoriginalcommunitystructureandre-dividethecommunitystructurewillproducealotofcomputationaloverhead.Therefore,toensuretheaccuracyofthealgorithmwhileimprovingtheefficiencyofthefieldisanurgents

7、olutiontothetechnicalproblems.Basedontheresearchstatusofcommunitydiscoveryalgorithm,anadaptivecommunitydiscoveryalgorithmKDEDisproposed,whichisbasedontheideaofdensitypeakclustering,guaranteesthehighefficiencyandincreasestheadaptabilitywiththethermaldiffusionmodel.Me

8、anwhile,adynamiccommunitydiscoveryalgorithmD-KDEDbasedonlocalincrementisproposed,basedontheassumptionofshort-termsmoothness.Theincremental