层次聚类社区算法研究综述

龙源期刊网层次聚类社区算法研究综述作者：赵巍来源：《无线互联科技》2015年第19期摘要：文章主要分析了社区发现算法的基本发展情况，研究了由于不同分析对象形成的4类社区发现方法：基于边图思想方法、矩阵谱分析方法、基于极大团思想方法、层次聚类方法。详述其中具备最优越性能的层次聚类方式，对比分析典型算法，提出合理研究社区发现算法的方向，为以后进一步分析提供参考。关键词：层次；聚类社区算法；研究综述社区发现实际上就是依据社区根本特点，利用相应措施来发现复杂网络实际结构。可以发现社区网络结构的方式叫作社区发现算法，上述方式可以发现潜在的复杂网络社区关系结构，从而对于分析网络层次结构以及拓扑结构具有重要意义。一般来说，由于复杂网络中存在边和节点以及复杂结构，不能依据普通图形分析方式来研究，依据社区发现方式可以及时得到实际层次结构，依据不同层次来获得分析网络数据信息，从而为进一步研究层次聚类社区算法提供依据。1社区发现算法1.1矩阵谱分析方法最早应用在社会发现中的方式是矩阵谱分析方法，分析行谱时，依据模块度矩阵或者Laplace矩阵获得网络中社区，对于任意矩阵来说，非退化特征值中相对的特征向量基本上都是正交，因此，非零特征值相对的特征向量存在正负两种因素，社区发现中的矩阵谱分析方式主要就是据此提出的，在Laplace矩阵中合理映射复杂网络，以此合理计算矩阵的特征向量以及特征值，发现次小特征值相对的特征向量，依据正负特征向量有效区分社区，在相同社区中划分正元素相应节点，另外区域中划分负元素节点，从而达到最简单网络划分的目的。一次划分仅仅只能区分邻近的2个社区，如果要真实、有效地发现社区结构，需要合理迭代上述方式步骤，以便发现最真实的社区结构形式。1.2层次聚类思想方法脱离社区发现方式的分析矩阵方式就是层次聚类思想方法，计算节点相似性质来有效分析迭代聚类，从而能够得到层次聚类树，分析树的时候需要依据模块度函数，以便能够获得最优方式划分社区，Girvan和Newman提出的模块度函数，基本定义：如果社区被当作子图，那么相对的应随机模型变数应该不超过实际图中的变数，也就是存在越好的结构，就具备越大模块度函数值。龙源期刊网边图思想方法边图思想方法主要就是用来分析重叠区域中适当增加社区发现，不相同的分析聚类层次方式，存在不同的发现形式，上述方式依据合理计算邻近边介数来达到发现社区的目的，在不同社区的邻近边，重叠部分就是2个社会交点。依据边图思想方式、有机集合群优化粒子思想，提出一种边图优化粒子的方式，并且可以把原图变为边图，划分非重叠边图部分，发现最优划分粒子群优化形似。1.4极大团思想方法依据边图思想方式和层次聚类方式分析社区发现的时候，比较注重网络中的边或者节点，极大团思想方法相对比较注重网络中完全子图，据此来有效分析完全和划分完全子图。极大团思想方法中，定义社区的时候，主要就是相邻k完全图集合，k完全图就是存在节点k个的完全图，在2个完全图中可以适当共享k-1节点，此时是相邻的k完全图。最早的极大团思想就是极大团过滤算法（CPM）。上述算法基本理念实际上是，利用k个完全图构成社区，并且能够在邻近的k个完全图中进行滚动。优化极大团过滤算法形成时序性极大团过滤算法（CPM，SCP），此方式不但可以提高算法速度，还能在加权网络中合理应用上述算法。龙源期刊网