基于密度峰值的标签传播社区发现算法.pdf
《基于密度峰值的标签传播社区发现算法.pdf》由会员分享,可在线阅读,更多相关《基于密度峰值的标签传播社区发现算法.pdf(6页珍藏版)》请在咨信网上搜索。
1、收稿日期:;修回日期:基金项目:国家自然科学基金资助项目(,);陕西省自然科学基础研究计划资助项目(,)作者简介:付立东(),男,陕西临潼人,副教授,硕导,博士,会员,主要研究方向为复杂系统建模及应用();刘佳会(),女,河南商丘人,硕士研究生,主要研究方向为复杂网络分析;王秋红(),女,陕西蒲城人,工程师,主要研究方向为数据通信基于密度峰值的标签传播社区发现算法付立东,刘佳会,王秋红(西安科技大学 计算机科学与技术学院,西安 ;中国电子科技集团有限公司第 所,西安 )摘要:针对标签传播算法中节点启动顺序和更新标签的随机性造成的结果不稳定问题,提出一种新标签传播算法用于复杂网络社区检测(,),
2、包括社区中心的确定和外围节点的标签传播。首先利用大度节点不利指标、指标和度为 节点的结构特性刻画节点局部相似性指标,并用此指标度量节点间距离和解决最大标签相同时的随机选择;然后引入改进的密度峰值聚类算法寻找社区中心,确定社区数量;最后基于社区中心和外围节点的标签传播,得到最终的社区划分结果。通过人工网络和真实网络上的实验,结果表明标准化互信息、模块度和 指标值优于对比算法,所提出的算法可以有效发现复杂网络中的社区结构,且鲁棒性更高。关键词:密度峰值聚类;局部相似度;标签传播;社区发现中图分类号:文献标志码:文章编号:():,(,;,):,(,),、,:;研究复杂网络的社区结构和特征,有助于人们
3、深入了解复杂系统的功能及演化过程 。一般来说,网络中的社区内部节点之间联系紧密,社区之间连接稀疏 。因此,借助社区结构的特征研究网络中成员之间的差异和联系,对于复杂网络分析和实际应用的发展具有重要作用 。标签传播算法(,)是由 等人 提出的,因具有接近线性的时间复杂度且无须任何先验信息而被广泛用于复杂网络社区检测。但由于节点启动顺序和更新标签的随机性,算法的社区划分结果存在不稳定性、易形成较大社区等缺点。密度峰值聚类算法 (,)具有较好的鲁棒性,所选出的中心节点个数决定了最终数据集的聚类数量。这一思想适用于解决标签传播算法性能不稳定的问题。但由于密度峰值聚类算法的局部密度和相对距离是基于坐标进
4、行计算的,所以 算法无法直接应用于复杂网络社区检测。因此,本文提出一种基于密度峰值的标签传播社区发现算法()用于复杂网络社区检测。算法将标签传播过程分为社区中心节点的标签传播和外围节点的标签传播。社区中心节点的标签传播关键在于社区中心的确定。本文通过改进 算法中聚类中心的选择过程来自动选择社区中心节点。外围节点的标签传播是对网络中未更新节点和已在社区中的节点进行标签更新。为避免 算法中的节点启动顺序的随机性,利用 指标 对外围节点进行重要性排序,从 值最高的外围节点进行标签传播。针对传播过程中存在多个最大标签的问题,提出一种新的节点局部相似度指标。该指标综合考虑了节点之间有无共同邻居的情况,在
5、无共同邻居时同时考虑了节点度为 时的节点相似性度量问题。通过社区中心的标签传播形成初始社区,外围节点的标签传播得到最终的社区划分结果。在真实网络数据集和合成网络数据集上与已有的算法进行实验对比,证实了本文算法的有效性。相关工作 标签传播算法 算法不依赖自由参数和目标函数,主要根据网络的拓第 卷第 期 年 月计 算 机 应 用 研 究 扑结构传播节点信息。初始时为网络中的所有节点分配一个唯一的标签,然后逐次迭代将一个节点的标签更新为其邻居的标签。标签传播算法具有简单、高效的优点,但其节点启动顺序和更新标签的随机性易造成社区划分结果不稳定。针对 算法的不足,提出了多种算法。等人 基于 的概念,提出
6、一种基于节点影响力的标签传播算法(,)。该算法根据节点的影响力值确定节点的更新顺序,当存在多个最大标签时,引入标签影响力计算公式来计算各个最大标签的影响力,从而避免随机选择一个标签的问题。()算法 通过亲密度矩阵评估节点的重要性,根据节点的重要性降序更新节点以解决节点启动顺序的随机性问题。对于每个待更新节点,根据其邻居中最有影响力的标签作为其更新标签,以解决多个标签出现频次相同时的随机选择问题。等人 为解决 算法的不稳定性,提出一种基于节点重要性和核心扩展的标签传播算法(,)。该算法在标签传播阶段开始之前,先根据网络的拓扑结构对节点的重要程度进行排序;然后从低重要性节点的标签传播到网络的密集中
7、心;对于多个标签出现频率相同的问题,作者分两种情况来处理以消除随机选择的过程:在标签传播的第一次和第二次迭代中使用 指标确定待更新节点的标签;在其他迭代中,根据每个标签的影响力来更新节点的标签。()算法是由段小虎等人 提出的,用于解决重叠社区检测。该算法指出 算法寻找聚类中心点的思想适用于复杂网络的社区发现,通过结合大度节点有利指标和连接贡献度定义了一种新的节点局部相似性指标用于改进密度峰值聚类算法,使其能直接用于复杂网络社区发现。密度峰值聚类算法 等人 提出的密度峰值聚类算法能够识别任意形状的簇,其提出基于两个假设:)聚类中心点的局部密度高于其他数据点;)各个聚类中心点的距离相对较远。因此,
8、算法需要计算节点的局部密度和到高密度节点的距离,通过绘制决策图来选择样本的聚类中心。在 算法中,节点的局部密度有两种计算方式,对大规模数据集采用截断核计算,小规模数据集则采用高斯核计算,其定义见式()()。()()()()其中:为数据点 与 之间的欧氏距离;为数据点 的截断距离。根据局部密度对每个数据点进行排序,依次计算出每个数据点的最小距离。最小距离 定义为点 与其他密度更高的点之间的最小距离,一般采用欧氏距离度量,其定义见式()。():()()对于局部密度最大的数据点 ,其相对距离为到所有数据点距离的最大值。其他数据点的相对距离为局部密度高于 的节点中与数据点 的最近距离。综上可知,密度峰
9、值算法虽然可以识别任意形状的簇,但存在一些不足,即截断距离需要人为设置和中心点的选择存在主观性 。此外,基于坐标计算节点距离的指标无法直接应用于复杂网络社区检测。一些学者通过改进密度峰值聚类算法将其应用于社区发现。段小虎等人 结合大度节点有利指标与连接贡献度来度量节点距离,为避免人工决策,利用切比雪夫不等式来选择社区中心点,但标准差系数 需人为给定且计算距离的时间复杂度较高。等人 基于 指标定义节点间的相似度,节点间的距离通过相似度的倒数来衡量,该方法虽然减少了计算节点距离的时间复杂度,但设计节点相似度时局部信息利用不全面,只考虑了节点间有共同邻居的情况。基于密度峰值的标签传播社区发现算法针对
10、静态无向网络,本文设计了一种基于密度峰值的标签传播社区发现算法,该算法主要包括:)改进密度峰值聚类算法确定社区中心节点,作为标签传播算法的输入。包括结合改进的 指标、大度节点不利指标和度为 的节点的结构特性来定义节点相似度,用于度量节点间距离和解决多个标签出现频次相同时的随机选择问题。通过网格搜索确定切比雪夫不等式中的标准差系数 ,以解决系数 人为给定的主观性。)提出外围节点的概念和外围节点标签更新的两种规则,并利用 指标度量外围节点的重要性,以解决标签传播中节点启动顺序的随机性。本文算法的流程如图 所示。图 算法流程 社区中心节点的确定本文通过改进密度峰值聚类算法中的局部密度和节点距离度量指
11、标,使其能直接用于复杂网络社区检测。在得到局部密度和节点最小距离的乘积后,通过网络搜索来确定切比雪夫不等式中的标准差系数 ,从而自动筛选出社区中心节点。以下是确定社区中心节点所涉及的相关定义。)节点局部密度在复杂网络中,节点的密度大小不仅与节点领导的邻居数量有关,而且也与邻居节点之间联系的紧密性息息相关。节点计 算 机 应 用 研 究 第 卷领导的邻居数量越多,其影响力就越强,邻居节点之间的连边越多,则该节点凝聚周围节点的能力就越强。因此,本文综合考虑节点在网络中的领导力和凝聚力来设计局部密度指标,即 ()()()()()其中:()表示 的邻居集,包括节点 。)节点局部相似度节点局部相似度同时
12、考虑了节点之间有无共同邻居的情况。共同邻居存在时采用改进的 指标 度量两节点之间的相似性。无共同邻居时需进一步考虑度为 节点的相似性度量问题,对于度为 的节点,定义相似度值为 ,因为该节点的行为只与其直接邻居相关;对于无共同邻居且节点度大于 的两节点,其相似度与节点的度有关,根据大度节点不利指标 可知,节点度越大,其相似度越小。节点局部相似度定义见式()。()()()()()()()(),()()(),()()(),(),()()其中:表示 中元素的个数。)节点距离和最小距离根据社区的一般定义,社区内部节点之间相似度高于社区间节点之间的相似度。因此,将节点距离定义为节点局部相似度的倒数,两节点
13、的局部相似度越小,其距离相对越远,从而保证高相似度的节点位于同一社区中。节点距离的定义为 ()在确定节点距离后,采用式()确定各节点的最小距离。为保证节点局部密度和最小距离同等重要,在计算 与 的乘积时需先对其进行 归一化,将值映射到 ,归一化定义见式()()。()()()()()()()()其中:、分别表示归一化后的节点密度和最小距离;为节点的局部密度集合;为节点的最小距离集合。节点中心值越大,其成为社区中心的可能性越大。在得到各节点的中心值后进行降序排序,并利用切比雪夫不等式自动选出社区中心。节点中心值得定义见式()。()切比雪夫不等式 假设随机变量 的期望为 ,非零标准差为 。对于任意实
14、数 ,满足以下条件:()()通过上式可知,切比雪夫不等式在求概率 ()的估计上限时,只与 有关,与 的分布无关。因此,考虑使用网格搜索的方法确定 值。根据社区中心节点的中心值应大于网络中的其他节点,可得以下关系:()根据式()可知:是否选择该节点为社区中心与 、有关,而 、均为定值,则 值确定之后便可选择出满足式()的社区中心节点。由于 ()值的改变与中心社区个数相关,引起 值改变的 值并不是线性改变的。因此,本文通过改进传统网格搜索的方法,将引起 值改变的 节点值作为网格搜索的每步参数值进行迭代寻优,从而确定社区中心节点个数。具体实现如算法 所示。算法 社区中心节点的确定输入:复杂网络 (,
15、)。输出:社区中心节点。网络中各个节点的标签初始化为节点标号 :利用式()计算节点局部密度 根据密度值 大小降序排列节点在集合 :利用式()计算节点的最小距离 用式()()归一化每个节点的局部密度和最小距离根据式()计算节点中心值,并降序排列在集合 中计算节点中心值的平均值 和标准差 :()反推每选择一个中心节点所需的值将 加入集合 中 降序排列集合 中的值 :此时的 即为最优的标准差系数 值 根据式()和 值确定社区中心节点 社区中心和外围节点的标签传播 初始社区的形成由 节得到的复杂网络社区中心节点形成初始社区。即将各社区中心节点标签传播至其邻居,由各个中心节点及邻居构成初始社区。外围节点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 密度 峰值 标签 传播 社区 发现 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。