基于聚类分析的社会网络社团划分方法研究.pdf

《基于聚类分析的社会网络社团划分方法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、’二Ｉ．：单位代码：１０２９３密级巧女＃化给Ａｒ论文题目：基于聚类分析的社会网络社团划分方法研究．１０１２０４１１０７学号节＾繁，姓名；一－‘＇？－罢一．Ｉ、李玲娟＇去藝蒼．导师＼叫裴，■Ｊ计算机软件与理论片真学科专业机软件应用技术：：鸣研究方向基于网络的计算工学硕七申请学位类别论文提交日期２０１５年３月々南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导Ｆ进巧前研光工作

2、及取得的研究成巧。尽我所知，除了文中特别加货标注和致谢的地方外，论文中不包含其他人已经发表或撰写过。的研宛成巧，也不包含为获得南京邮电大学或其它教育机构的学位或巧书而使用过的材料－－与我同工作的同志对本研巧所做的巧何贡献均已在论文中作了明确的说明并表示了谢意。一。本人学位论文及涉及化关资科若打不实，愿怠承担切相关的法律责任研巧生签名：４．成日期：对斗岭南京邮电大学学位论文使用授权声明本人授权南京邮电大学可保留并向国家有关部口或机构送交论文的复印件和电子文巧；允许论文被爸阅和借阁；可蒋学

3、位论文的余部或部分巧容编入有关数据库进行检索；－、。汇编本学位论文了的和纸采用影印、缩印或扫描等复制手段保存文本电义挡内容质一理。（论的内容相数。论文的公包括刊登）授权邮电大学研究化院办文布南巧涉密论义在解密。学位后适用本授权书．：：：．签名签名Ｎ期，研巧生＾导师鴻＞ｆ少雌私ResearchonSocialNetworkCommunityDivisionMethodBasedonClusteringAnalysisThesisSubmittedtoNanjingUniversityofPosts

4、andTelecommunicationsfortheDegreeofMasterofEngineeringByWeiWangSupervisor:Prof.LingjuanLiMarch2015I摘要近年来，随着Web2.0的发展，社会网络越来越受到更多学者们的关注和研究。在社会网络的众多性质中，社团结构是其最重要同时也是最具有研究意义的性质之一。通过社团的划分，我们不仅能够了解和分析网络的结构特点，也能够挖掘出表面数据关系之中的隐性信息。在目前的研究中已经有了很多经典的社团划分算法，比如Girvan-Newman算

5、法，Keinighan-Lin算法等，但是准确度和时间复杂度之间的平衡仍然是社团划分算法的主要问题之一。本文对社会网络的社团划分方法进行了研究，首先系统地分析比较了现有划分算法的优缺点，然后基于聚类分析的思想，提出了两种改进的社团划分方法：基于节点相似度系数聚类的社团划分方法（CommunityDivisionMethodBasedonNodeSimilarityClustering,NSCCDM）和基于遗传算法聚类的社团划分方法（GeneticAlgorithmClusteringBasedCommunityDivi

6、sionMethod,GACCDM）。NSCCDM方法首先通过欧几里得公式和最短路径构造了一种新的相似度系数度量方法，并生成相似度系数矩阵，然后通过比较节点之间的相似度系数，进行节点的聚类，最后再使用模块度函数Q对被重复划分的节点进行最优社团选择。GACCDM方法主要采用了遗传算法的思想。该方法使用了模块度函数Q作为适应度函数来控制遗传算法的进化过程；采用指向性的变异策略代替随机变异策略加快算法的收敛速度；并结合网络的拓扑结构和节点之间的相似度系数关系进行遗传聚类，从而完成对社团的划分。本文使用java语言对以上的两种

7、方法进行编码实现，并将它们分别应用于真实社会网络：Zachary空手道俱乐部网络、海豚网络以及美国足球网络。实验得出的划分结果与实际情况相符，从而表明了本文算法的准确性和可用性。关键词:社会网络，社团划分，聚类分析，相似度系数，遗传算法IIIAbstractInrecentyears,withthedevelopmentofWeb2.0,thesocialnetworkhasattractedmoreandmorescholarstopayattentionandstudy.Amongthemanyproperties

8、,communitystructureisbutalsooneofthemostimportantbutalsothemostsignificantproperties.Communitydivisioncannotonlyhelpustounderstandandanalyzestructurecharacteristicsof