基于点距离和聚类的社区发现算法研究

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

1、分类号：TP39单位代码：10183研究生学号：2013534016密级：公开研吉林大学硕士学位论文（专业学位）基于点距离和聚类的社区发现算法研究ResearchonCommunityDetectionAlgorithmsBasedonVertexDistanceandClusteringMethods作者姓名：李玉类别：工程硕士领域（方向）：计算机技术指导教师：黄岚教授培养单位：计算机科学与技术学院2016年4月———————————————————————基于点距离和聚类的社区发现算法研究———————————————————————ResearchonCommunityDet

2、ectionAlgorithmsBasedonVertexDistanceandClusteringMethods作者姓名：李玉领域（方向）：计算机技术指导教师：黄岚教授类别：工程硕士答辩日期：2016年5月25日未经本论女作者的书面授权，化法收存和保管本论文书面版本、电子版本的任何单位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行、出租、改编等有碍作者著作权的商业性使用（但纯学术性使用不在此限）。否则，应承担侵权的法律责任。吉林大学硕：ｔ学位论文原创性声明本人郑重声明：所呈交学位论文，是本人在指导教师的指导下，独立进行研巧工作所取

3、得的成果。除文中己经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：２０化年夕月乂日摘要摘要基于点距离和聚类的社区发现算法研究社会网络是指由于个体之间发生交互而产生的一种关系网络。随着近些年互联网的飞速发展，社会网络的类型也越来越多样，其中蕴含的有价值信息也越来越多，挖掘社会网络中的社区结构也成为了近些年研究的热门问题。由于社区发现能够发现社会网络中节点间的共性信息，使得其在蛋白质功能分析、用户行为分析、

4、网络异常检测等诸多领域得到了广泛的应用。通常认为，社区是由一些相互联系紧密的个体所构成的集合，并且社区间的个体相对社区内部的个体联系稀疏。社会网络通常被抽象为图，其中节点代表个体，节点间的边代表个体之间发生的交互关系。挖掘社会网路中的社区结构可以被理解为根据节点之间的交互关系将图划分为多个子图，各个子图中的节点相似度高而子图之间的节点相似度低，即将社会网络中的社区发现问题看作一个图中的聚类问题。针对聚类方法的特点，本文的主要工作难点如下：1.如何有效的度量网络中节点间的距离。2.根据网络中节点间的距离，利用何种聚类算法对节点进行聚类。针对以上两个问题，文本通过以下方法解决：1.针对

5、网络中节点间距离的度量问题，本文分析了余弦距离和Jaccard距离的不足之处，并通过引入网络中节点间最短路径的距离，分别与余弦距离、Jaccard距离相结合，提出了改进的余弦距离和改进的Jaccard距离，从而更好的度量了网络中节点间的距离。2.针对聚类算法的选择问题，本文选取了两个基于距离的聚类方法来对节点进行聚类，分别为密度峰值聚类方法和凝聚层次聚类方法。其中密度峰值聚类方法仅根据节点间的距离就能选取出聚类中心和聚类数目，无需参数选择过程。凝聚层次聚类方法能够根据节点的距离对节点不断合并，发现网络的层次结构。综上所述，本文所做的主要工作如下：1.本文提出了两种基于改进的点距离和

6、密度峰值聚类的社区发现方法—CSDPC和I摘要JSDPC。其中CSDPC和JSDPC分别采用改进的余弦距离和改进的Jaccard距离度量节点间的距离。CSDPC和JSDPC能够根据节点间的距离选取网络的关键节点并确定网络中存在的社区数目，这与其他传统的社区发现算法相比存在很大的优势。2.本文提出了一种基于改进的点距离和凝聚层次聚类的社区发现方法—CSAHC。CSAHC采用改进的余弦距离度量节点间的距离，利用凝聚层次聚类方法不断对节点进行合并，构建网络的社区层次结构，并根据网络结构的不同制定了相应的社区结果选择策略。3.在真实网络数据集和人工合成网络数据集上的实验证明了所提算法的可行

7、性和有效性。关键词：社区发现，节点距离，密度峰值聚类，凝聚层次聚类IIAbstractAbstractResearchonCommunityDetectionAlgorithmsBasedonVertexDistanceandClusteringMethodsSocialnetworksareinteractivenetworkofrelationshipsbetweenindividuals.WiththerapiddevelopmentofInternetinre