基于局部扩充的重叠社区发现算法研究和改进

《基于局部扩充的重叠社区发现算法研究和改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于局部扩充的重叠社区发现算法研究和改进重庆大学硕士学位论文（学术学位）学生姓名：龙渊指导教师：王茜教授专业：计算机软件与理论学科门类：工学重庆大学计算机学院二O一六年四月StudyandImprovementofOverlappingCommunityDiscoveryBasedonLocalExpansionAThesisSubmittedtoChongqingUniversityinPartialFulfillmentoftheRequirementfortheMaster’sDegreeofEngine

2、eringByLongYuanSupervisedbyProf.WangQianSpecialty：ComputerSoftwareandTheoryCollegeofcomputerscienceofChongqingUniversity,Chongqing,ChinaApril,2016重庆大学硕士学位论文中文摘要摘要随着网络的飞速发展以及社交媒体的广泛应用，使得人与人之间的联系尤为密切。这种错综复杂的关系组成一个庞大的社交网络，因此吸引了众多学者致力于复杂网络的研究，从复杂网络中发现并抽取其中的模块结构这

3、就是所谓的社区发现。以前学者都致力于非重叠网络的研究，然后这在现实生活中是不实用的，由此引发了大家对重叠网络的研究，近几年来取得了不小的进展。本文即针对重叠社区发现算法进行改进。重叠社区即网络中包含的节点不止属于一个社区，能够有效地识别这些重叠节点是本文算法研究的重点。比较有名的算法有LFM算法和GCE算法，它们都是利用网络的局部信息，对单个种子节点进行成长的理念。本文鉴于局部扩充的核心思想，对种子选择、社区扩充剪枝、相似度判断、并行化模型等提出了自己的改进方案。①由于LFM算法选择种子节点过于随机，影响算法准

4、确性；而GCE算法需要找到网络图的所有团结构，影响算法效率；本文采取折中策略，通过删除网络中影响力较小的节点来得到核心结构。主要基于度数较多的点在社团结构中是比较重要的节点，如果一个节点的影响力较大那么它邻居节点也是重要的。②LFM算法和GCE算法在对一个种子进行扩充时并未对其候选集进行判断，这严重影响了算法性能。本文对扩充过程进行了细致的推导和严格的数学证明，对社区扩充过程产生的候选集进行了剪枝处理，以进一步的提升算法效率。③种子扩充后生成的社区存在一定的相似性，如果不加以判断会对结果准确性产生影响。本文提到

5、的相似度度量公式除了考虑社区节点集合还考虑了社区邻居节点的影响，更具有实际意义。④对扩充过程进行并行化处理。并行化是提高算法性能的一个很重要的手段，通过分析本文算法过程，可以方便的解除数据依赖，并且引入生产者消费者模型来解决线程通信问题。由于硬件环境限制实验在多核CPU上进行操作。⑤通过应用到实际网络图中验证了种子选择策略在一定范围之内的可行性，以及综合改进算法ISA对于社区发现的准确性以及时间损耗。准确性用NMI（标准互信息量）进行度量，发现本文算法对于混淆参数以及社区结构敏感，总体性能优于LFM算法，且不逊

6、于GCE算法。关键词：重叠社区发现，节点影响力，局部优化，并行计算I重庆大学硕士学位论文英文摘要ABSTRACTWiththerapiddevelopmentofthenetworkandthewideuseofsocialmedia,itmakespeopleclosethanever.Alargesocialnetworkconsistsofthecomplexrelationship,whichattractstheattentionofmanyscholarswhoarededicatedtothest

7、udyofcomplexnetworks.Findingandextractingmodularstructurefromcomplexnetworkswhichiscalledthecommunitydetection.Previousscholarsworkedonnon-overlappingnetworkswhichinreallifeisnotpractical.Sotheresearchonoverlappingnetworkshasbeenstudiedandhasmadegreatprogres

8、sinrecentyears.Inthispaper,Iproposeanimprovedschemefortheoverlappingcommunitydetectionalgorithm.Overlappingcommunityisthatnodesbelongtomorethanonecommunity.Effectivelyidentifytheoverlappingnodes