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

发布时间：2017-10-23 12:15

  本文关键词：基于点距离和聚类的社区发现算法研究

  更多相关文章： 社区发现 节点距离 密度峰值聚类 凝聚层次聚类

【摘要】：社会网络是指由于个体之间发生交互而产生的一种关系网络。随着近些年互联网的飞速发展,社会网络的类型也越来越多样,其中蕴含的有价值信息也越来越多,挖掘社会网络中的社区结构也成为了近些年研究的热门问题。由于社区发现能够发现社会网络中节点间的共性信息,使得其在蛋白质功能分析、用户行为分析、网络异常检测等诸多领域得到了广泛的应用。通常认为,社区是由一些相互联系紧密的个体所构成的集合,并且社区间的个体相对社区内部的个体联系稀疏。社会网络通常被抽象为图,其中节点代表个体,节点间的边代表个体之间发生的交互关系。挖掘社会网路中的社区结构可以被理解为根据节点之间的交互关系将图划分为多个子图,各个子图中的节点相似度高而子图之间的节点相似度低,即将社会网络中的社区发现问题看作一个图中的聚类问题。针对聚类方法的特点,本文的主要工作难点如下:1.如何有效的度量网络中节点间的距离。2.根据网络中节点间的距离,利用何种聚类算法对节点进行聚类。针对以上两个问题,文本通过以下方法解决:1.针对网络中节点间距离的度量问题,本文分析了余弦距离和Jaccard距离的不足之处,并通过引入网络中节点间最短路径的距离,分别与余弦距离、Jaccard距离相结合,提出了改进的余弦距离和改进的Jaccard距离,从而更好的度量了网络中节点间的距离。2.针对聚类算法的选择问题,本文选取了两个基于距离的聚类方法来对节点进行聚类,分别为密度峰值聚类方法和凝聚层次聚类方法。其中密度峰值聚类方法仅根据节点间的距离就能选取出聚类中心和聚类数目,无需参数选择过程。凝聚层次聚类方法能够根据节点的距离对节点不断合并,发现网络的层次结构。综上所述,本文所做的主要工作如下:1.本文提出了两种基于改进的点距离和密度峰值聚类的社区发现方法—CSDPC和JSDPC。其中CSDPC和JSDPC分别采用改进的余弦距离和改进的Jaccard距离度量节点间的距离。CSDPC和JSDPC能够根据节点间的距离选取网络的关键节点并确定网络中存在的社区数目,这与其他传统的社区发现算法相比存在很大的优势。2.本文提出了一种基于改进的点距离和凝聚层次聚类的社区发现方法—CSAHC。CSAHC采用改进的余弦距离度量节点间的距离,利用凝聚层次聚类方法不断对节点进行合并,构建网络的社区层次结构,并根据网络结构的不同制定了相应的社区结果选择策略。3.在真实网络数据集和人工合成网络数据集上的实验证明了所提算法的可行性和有效性。
【关键词】：社区发现 节点距离 密度峰值聚类 凝聚层次聚类
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13
【目录】：

• 摘要4-6
• Abstract6-11
• 第1章 绪论11-16
• 1.1 研究背景11-12
• 1.2 研究现状12-14
• 1.3 本文工作14
• 1.4 本文组织结构14-16
• 第2章 社区发现相关理论与技术16-22
• 2.1 社区的定义16
• 2.2 节点相似度及距离度量16-19
• 2.2.1 余弦相似度和余弦距离17-18
• 2.2.2 Jaccard相关系数和Jaccard距离18-19
• 2.3 社区发现的评价指标19-21
• 2.3.1 归一化互信息19-20
• 2.3.2 模块度20-21
• 2.4 本章小结21-22
• 第3章 基于点距离和密度峰值聚类的社区发现方法22-40
• 3.1 节点距离度量22-24
• 3.1.1 改进的余弦距离度量22-23
• 3.1.2 改进的Jaccard距离度量23-24
• 3.2 密度峰值聚类方法24-25
• 3.3 基于点距离和密度峰值聚类的社区发现方法25-27
• 3.3.1 基于改进的余弦距离和密度峰值聚类的社区发现方法—CSDPC . 1525-26
• 3.3.2 基于改进的Jaccard距离和密度峰值聚类的社区发现方法—JSDPC26-27
• 3.4 实验与结果分析27-39
• 3.4.1 真实网络数据集27-35
• 3.4.1.1 数据集描述28
• 3.4.1.2 实验结果与分析28-35
• 3.4.2 人工网络数据集35-39
• 3.4.2.1 数据集描述35
• 3.4.2.2 实验结果与分析35-39
• 3.5 本章小结39-40
• 第4章 基于点距离和凝聚层次聚类的社区发现方法40-54
• 4.1 节点距离度量40
• 4.2 层次聚类方法40-42
• 4.3 基于点距离和凝聚层次聚类的社区发现方法—CSAHC42-43
• 4.4 实验与结果分析43-53
• 4.4.1 真实网络数据集43-49
• 4.4.2 人工网络数据集49-53
• 4.4.2.1 社区数目可以确定49-51
• 4.4.2.2 社区数目无法确定51-53
• 4.5 本章小结53-54
• 第5章 总结54-55
• 参考文献55-59
• 作者简介及在学期间所取得的科研成果59-60
• 致谢60

【相似文献】

中国期刊全文数据库 前5条

1 孙敏;;测速量距很简单[J];电脑迷;2012年11期

2 徐名祝;;SSRR—采用扩展频谱体制的距离和距离变化率测量装置[J];电讯技术;1979年04期

3 孙梅玉;;基于距离和密度的时间序列异常检测方法研究[J];计算机工程与应用;2012年20期

4 ;第五节 距离和距离变化率性能要求[J];电讯技术;1975年04期

5 ;[J];;年期

中国硕士学位论文全文数据库 前4条

1 李玉;基于点距离和聚类的社区发现算法研究[D];吉林大学;2016年

2 张孟;关于树的离心距离和的一些探究[D];华中师范大学;2013年

3 崔娜;关于树的离心距离和的极值[D];中国矿业大学;2015年

4 布威则热古丽·伊斯坎代尔;乘积图的离心连通指标和离心距离和[D];新疆大学;2013年

，

本文编号：1083352