基于图熵聚类的重叠社区发现算法.docVIP

基于图熵聚类的重叠社区发现算法 　　摘要：图聚类算法是数据挖掘和复杂网络研究中的一个关键环节。基于密度、层次划分的方法已经被广泛应用于流行病学、新陈代谢和科学引文写作中。尽管上述的聚类方法适用于复杂网络的社区发现，但精度受到限制，其中一个最大的挑战是重叠社区的生成。为填补这?缺口，提出了一种利用图熵有哪些信誉好的足球投注网站局部最优的聚类方法。与传统的基于密度的种子生长式方法不同，在每一次迭代中，引入图熵来衡量图结构的模块度，并为种子的选择提供了随机选择、基于节点的度和基于节点的聚类系数3种方案。经过自下而上迭代的聚类，引入准确率和召回率等评价指标评估聚类结果的精确度，证明了算法的有效性。 　　关键词：图聚类算法；图熵；复杂网络；重叠社区 　　复杂网络在当今社会随处可见，往往蕴含着重要的信息。复杂网络规模庞大，节点连接复杂，直接对其进行研究比较困难。对复杂网络中的社区结构进行研究，已成为当下的流行趋势。社区结构经常重叠，存在同属于几个社区的节点。与此同时，许多社区结构会递归组合成一个层次结构。现存的方法忽视了社区的相互关系及其重叠，然而对于这部分的研究具有重要的实际意义。无论是寻找热门的微博话题，还是医学上对功能相关蛋白质组的寻觅，对社区结构的关系及重叠社区的深入探究都将影响巨大。 　　文章首先借鉴信息论中信息熵的概念，根据信息熵的公式定义节点熵和图熵的公式。图熵是节点熵的总和，作为聚类的模块度的度量，图熵越低则表明图中模块度越高。据此文章提出一种基于图熵聚类的重叠社区发现算法，把图熵作为种子生长的聚类过程中添加或删除节点的依据。实验部分，为种子的选择提供了随机选择、基于节点的度和基于节点的聚类系数3种解决方案，并对实验结果进行分析对比。 　　1 相关工作 　　很多聚类算法被运用到复杂网络的社区发现中，可以被总结为三大类：基于密度的方法、层次方法和基于划分的方法。 　　1.1 基于密度的方法 　　基于密度的方法发掘网络中内部连接密集的子图，根据对象周围的密度不断增长聚类。典型的例子是发现完全子图的最大团算法。相对密集的子图通过使用密度阀值或者结合渗透的小规模团被确定。选取种子作为初始节点，通过可替换的密度函数扩张这些种子。Mc0DE通过计算每个节点v的核心聚类系数给v设置权重，核心聚类系数是节点v和v的k个核心邻居的密度，能够放大内部连接密切的区域。算法选取权重最高的节点，通过递归地纳入不违背阀值的邻居节点扩大聚类。该方法需要预先设定阀值，这是基于密度的种子生长方法的缺陷。 　　1.2 层次方法 　　层次聚类方法创建层次以分解网络，能够帮助了解整个网络功能组织的结构，因此被广泛运用到复杂网络的分析中。自底向上的凝聚算法初始时把每个节点都看作一个独立的聚类，通过迭代合并两个最近或最相似的集合完成最终的聚类。与之相反，自顶向下的分裂算法把整个图看成一个聚类，然后递归地将单个大聚类分割成众多小聚类。凝聚算法中两个聚类的距离或相似度需要严格计算。分裂算法的挑战是找到精确的分割点，其中使用最广泛的是GN算法。 　　1.3 基于划分的方法 　　划分方法首先创建k个划分，然后利用循环定位技术将对象从一个划分移到另一个划分来帮助改善划分质量。为了达到全局最优，基于划分的方法需要穷举所有可能的分区。最常见的是k均值算法，每个聚类都用该聚类中对象的均值表示。 　　2 问题定义 　　尽管上述的聚类方法适用于复杂网络的社区发现，但精度受到限制，其中一个最大的挑战是重叠社区的生成。一个节点可能属于不同的社区，所以要求聚类方法能够分配节点到多个不同的聚类中。但一般的基于划分的方法和层次方法总是产生不相交的集合，因此只有基于密度的方法适用于挖掘重叠聚类。与传统的基于密度的方法不同，文章引入图熵来衡量图结构的模块度。把熵的概念运用到图中，可以定义每个节点的节点熵并计算整个图的图熵度量图的模块度。图熵越低表示模块度越高，因此图熵可以作为在种子生长的聚类过程中添加或删除节点的依据。 　　对于无向图G=（V，E），假设G’是由一群聚类组成，其中一个聚类是G’=（y’，E’）。G’内部节点连接密集，G’外部节点连接稀疏。对于G’中任意一个节点v，v有在y’内的邻居和在y’外的邻居，定义v的内连接为从v到V’内邻居节点的边数，定义v的外连接为从v到V’外邻居节点的边数。定义pi（D为节点v的内连接率，公式表达为：（1） 　　其中|N（v）|为节点v的所有邻居节点数，n为节点v的内连接数。则v的外连接率p0（v）公式表达为： 　　p0（v）=1-pi（v） （2） 　　对于节点v，它的熵值取决于它的内连接和外连接的分布概率，参考信息熵，定义v的节点熵公式为： 　　e（v）=-pi（v）long2pi（v）-p0（v）long2p0（v） （3）