基于聚类算法的社团发现算法研究

2016-10-13深圳压寨网络有限公司王唐云

电子世界 2016年17期

深圳压寨网络有限公司王唐云

基于聚类算法的社团发现算法研究

深圳压寨网络有限公司王唐云

互联网、云计算、大数据技术的快速发展，使人类社会加速进入信息化时代。复杂网络是信息发展的产物之一，其可以描述人类社会的各种系统，比如电力网络、通信网络、社交网络等，利用复杂网络可以帮助人们分享智慧信息带带来的便捷性，比如Twitter、Facebook、微信、QQ、微博等社团应用工具促进人类社交，满足人们多样化、兴趣化、智能化交友需求。社团发现作为复杂网络处理的重要手段，其可以提高信息利用精准性。经过多年研究和发展，社团发现引入了先进的聚类技术，采用谱聚类、K均值、信息论等多种聚类算法，更好的从复杂网络搜寻人们期望的模型和信息，具有重要的作用和意义。

聚类算法；社团发现；谱聚类；K均值；信息论

1.引言

复杂网络是社会交际、电力工业、基因组织等复杂系统的一个具体表现形式，复杂网络中的节点可以描述复杂系统中的实体，节点之间的边可以描述实体之间的关系［1］。复杂网络可以描述现实世界中的许多系统，比如生物系统中的蛋白质交互网络、神经元网络、基因调控网络，社会系统中的人际关系网络、流行病传播网络、科学家合作网络，计算机系统中的万维网、电子商务网、朋友圈网，电力系统中的电力通信网络等，复杂网络研究涉及多个学科，包括社会学、计算机学、心理学、统计学、图形学、生物学等，随着对复杂网络的进一步研究，在小世界现象和无标度性之后，人们发现复杂网络存在另外一个特性，就是其拓扑结构呈现出社团结构，也即是复杂网络社团之间的联系是相对稀疏的，社团内部的连接相对稠密［2］。社团发现可以积极的利用算法寻找复杂网络中的社团结构，这样就可以研究整个网络的功能，更好的组织复杂系统，具有十分重要的意义。

2.社团发现及其应用

复杂网络中的社团发现是指在一个网络中，使用某种技术可以将联系较为紧密的节点划分为一个社团中，也可以把联系较少的节点划分为不同的社团中，也即是尽可能的保持社团内部节点结构紧密和社团之间的节点逻辑独立。社团发现可以准确的揭示复杂网络中节点的组织关系，比如具有共同的爱好和兴趣，属于一个工作种类，属于同一个省市县区域等；社团发现也可以提高网络的搜索性能，实现信息过滤、追踪热点话题、采集和分析网络舆情；社团发现也可以发现复杂网络系统中相关的结构单一等［3］。复杂网络社团结构如图1所示。

图1 复杂网络社团结构

社团应用领域非常多，最为常见的应用就是社交网络、基因组织、客户关系管理等方面。比如，在电子商务领域，如果根据每一个客户购买同类型商品的兴趣进行划分和组织，可以很快的识别出这些客户的群体，同时发现这些客户归属的朋友圈，像这些客户及其朋友推荐商品，可以更好的提高电商营销的精准程度，提高电商网站的成交率［4］。

3.基于聚类的社团发现算法研究

3.1谱聚类算法

社团网络是一个图结构，谱聚类算法主要思想来源与谱图划分。假设G是一个拥有N个节点的复杂网络，则G可以使用一个N×N的拉普拉斯矩阵L进行描述，lii表示矩阵节点Vi的度，规定Vi与Vj连通，则lij=-1，否则lij=0，因此矩阵L与邻接矩阵A的关系为L=K-A，矩阵K只能描述对角线节点对应的连通度值，其余元素规定为0.由于矩阵L每一行或每一列元素之和均为0，则L存在一个零特征值和一个全为1的特征向量。如果G可以被划分为M个费重叠社团Gm，则这些社团之间不存在连接，则网络G的拉普拉斯矩阵可以划分为M个对角矩阵，每一个对角矩阵表示一个社团。

3.2K均值算法

K均值也是社团发现常用的算法，其可以将复杂网络建模为一个矩阵S，假设该矩阵包括了h个社团，首先初始化矩阵S的m个特征值为社团的核心节点，也即是聚类中心，则h个社团的K均值算法矩阵如公式（1）所示：

在K均值算法聚类执行过程中，可以设置不同的特征权重，一般能够优化突出较为重要的特征贡献，特征权重向量如公式（2）所示：

通过分析，K均值聚类的目标函数如公式（3）所示：

在复杂网络社团发现过程中，K均值算法可以迭代执行，直到获取最优解或次优解，满足人们的需求。

图2 社团发现原理

3.3信息论算法

假设复杂网络X包含T个社团，每一个社团都存在Y个相关变量进行度量，因此社团发现可以使用信息论进行形式化描述：给定变量X和相关变量Y及其联合概率分布P（X，Y），在将变量X中的节点压缩到T个社团中时，需要尽可能的保存相关变量Y的信息，也即是尽可能的最小化互信息I（X；T）且最大化保存互信息I（Y；T），社团发现过程如图2所示。

利用互信息开展社团发现的目标函数可以设置为公式（4）。