《数据挖掘基础及其应用》课件第11章

第11章社交网络图聚类11.1引言11.2社团结构11.3半监督学习11.4社团挖掘11.5实验结果本章小结

11.1引言

复杂系统在自然界中广泛存在,而揭示复杂系统的统计结构特性、演化机制、整体行为与功能及它们之间的关联有着广泛的研究前景和巨大的应用价值。复杂网络是一种描述、分析复杂性系统的有力工具,很多现实系统皆可抽象成网络模型,其中节点对应系统中的实体,边对应实体间的关系。

尽管复杂网络备受关注,但对复杂网络尚无严格的定义。钱学森院士认为具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络可称为复杂网络,主要表现在以下方面:

(1)结构复杂性:网络规模巨大,同时网络连接结构随时间而改变。

(2)元素复杂性:网络节点可能具有混沌等非线性行为。

(3)相互作用复杂性:多重因素相互影响引发非线性集体行为并导致了网络的复杂性。

11.2社团结构

从图的观点看来,社团是网络的子图,其内部节点之间的连接相对紧密,但与社团外节点的连接相对稀疏。图11-1包含三个社团,分别对应图中三个大圈内的部分。这些社团内的连接相对紧密,而社团间的连接相对稀疏得多。图11-1社团网络结构示意

11.2.1社团度量标准

社团结构检测通常用社团模块度函数Q来衡量,Q的值越大,对应的社团结构越明显。详言之,给定网络G=(V,E),社团数m,Q函数定义为

式中:ci表示节点vi所属社团标记。函数δ定义为

11.2.2社团检测算法

该算法的关键步骤是定义节点间的相似性,然后利用已有算法进行社团提取。其基本框架可定义为算法11.1。

其中,典型的相似性度量包括以下几种:

(1)欧氏距离。给定节点对(vi,vj),该距离定义为

式中:A是图的邻接矩阵。该标准的基本原理是两点之间公共邻居节点越多,两个节点的相似性越高。

(2)邻域距离。节点u和v的邻域距离为

式中:N(u)为节点u的邻域节点集合;du

表示节点u的度。

此外,还有另外四个版本的邻域距离可供选择:

式中:N+(u)=u∪N(u)是节点u与其邻居节点集组成的。

(3)聚类系数。边(u,v)的聚类系数为

式中:zuv为网络中实际包含该边的三角形的个数;max(du-1,dv-1)为包含该边的最大可能的三角形个数。

(4)介数相似性。边(u,v)的最短路径介数为

式中:Luv为通过边(u,v)的最短路径的条数;LG

为网络中所有最短路径的条数。

11.3半监督学习

半监督聚类方法可分为以下几种:(1)基于模型的方法:假定每个类都隐含一个模型,根据模型发现相应的数据对象。其优点是可通过构建数据点空间分布的密度函数来确定分类,同时可利用标准统计工具来处理噪声与异常数据,自动确定聚类数。(2)基于约束的方法:结合了用户指定或面向应用的约束进行聚类。

(3)基于数据集空间结构的方法:与核优化算法有一个共同点,即借助于辅助空间,但不同的是,该方法并不抛弃原空间信息,而是通过投影技术将主空间信息映射到辅助空间,在新空间中完成迭代过程。

11.4社团挖掘

11.4.1算法框架给定网络G=(V,E),构建节点间的相似性矩阵K,依据相似性与不相似性分别构建必连矩阵CML和必分矩阵CCL,其中元素(i;j)∈CML表示节点vi

与节点vj隶属于同类,而(i;j)∈CCL隶属于异类的约束(下一节将详述构建方法)。为了融合相似性与半监督成分,定义新相似性矩阵:

非负矩阵分解的目标函数为

在通非负矩阵分解的基础上,基于公式(11-1)的非负矩阵分解算法被称为SS-NMF,与社团结构之间的关系为:

定理11-1半监督非负矩阵分解算法与模块密度是等价的。

11.4.2参数优化

本小节主要解决社团分类数的确定与半监督矩阵构建。确定数据集的聚类数问题目前仍是聚类分析研究中的基础性难题之一。目前有两种确定聚类数的方法:枚举法与拓扑结构性质方法。

枚举法的原理是通过使用不同的输入参数(如聚类数m)运行特定的聚类算法,对数据集进行不同的划分,并计算每种划分的聚类有效性指标,最后比较各个指标值的大小或变化情况,符合预定条件的指标值所对应的算法参数m被认为是最佳的聚类数。该策略的最大优势在于其将一个参数估计问题成功转化为了一个无参数优化问题。

11.5实验结果

11.5.1检测性能1.GN标准测试集GN标准测试集是Girvan与Newman提出的,由128个节点、4个规模为32(每个社团有32个节点)的社团组成,每个节点的度为16。为了有效控制社团结构的变化,引入两个参数Zin、Zout,分别表示每个节点与社团内部连边数和与社团外部连边数,即Zin+Zout=16。

选择GN算法、谱聚类算法、NMF算法进行性能对比。图11-2是算法在GN标准测试网络上的性能对比,横坐标表示Zout的值,纵坐标表示准确率。从图中可看出,当Zout≤8时,NMF、谱聚类算法和SS-NMF算法的性能优于GN算法的,其原因是边数不足以刻画社团的网络拓扑结构。当Zout≥9时,SS-NMF算法的性能明显优于NMF算法的,其主要原因是所采用的半监督策略可更好地刻画网络拓扑结构。图11-2GN标准测试网络上的算法性能

GN网络的高度对称性不能全面衡量算法的性能,因此对GN测试网络进行相应的扰动:对称地合并社团,即将原来4个社团合并成2个等同规模的社团;非对称地合并社团,即合并3个社团为一个大社团。为了进一步检验SS-NMF算法的性能,将该算法应用于改进的GN网络。表11-1包含了SS-NMF算法、压缩算法、Q-优化算法、D-优化算法在非对称GN网络中的性能对照结果。从表中可以看出,D-优化算法的性能最好,Q-优化算法的效果最差,SS-NMF算法拥有与D-优化算法相近的性能。

2.跆拳道俱乐部网络

Zachary俱乐部网络是经典的社会网络,来源于Zachary的分析研究,包含34个成员(节点)和78对关系(边)。由于管理者和指导教师对费用问题发生了分歧,俱乐部分成分别以管理者和指导教师为中心的两个子俱乐部,如图11-3(a)所示。图11-3俱乐部网络上的划分结果

11.5.2分辨极限容忍性分析

1.LFR标准测试集

由于GN测试网络的社团规模与节点度保持严格的一致性,无法评价算法对分辨极限的容忍性。为解决这一缺陷,Lancichinetti、Fortunato与Radicchi(LFR)提出新的LFR标

准测试集。与GN网络不同,LFR可构建规模大小可变的社团结构,社团结构规模与节点的度都服从于某个参数的指数分布。

LFR利用一个参数μ来控制网络噪声。当μ=1时,

所有的边都属于社团内部;随着μ的减小,社团之间的边数越来越多,社团结构越来越模糊,这增加了社团检测的难度。图11-4给出了LFR标准测试网络示意图。因此,算法能否准确地识别出规模不一致的社团是容忍分辨极限的一项重要指标。图11-4LFR网络示意图

为了有效量化算法的准确性,本章引入标准化互信息指标(NormalizedMutualInformation,NMI)。给定两个关于节点的划分P与P',标准互信息指标定义为

式中:N是一个|P|×|P'|矩阵,其元素Nij表示划分P中第i个社团与划分P'中第j个社团的公共节点数;Ni·表示矩阵N第i行元素之和;N·j表示矩阵N第j列元素之和。

图11-5为LFR网络上的算法性能,其横坐标表示参数μ,纵坐标表示标准互信息。从图中可以看出,SS-NMF算法的性能明显优于谱聚类与GN算法的;在μ>0.65时,谱聚类算法的性能明显优于NMF算法,但当μ<0.65时,其性能急剧下降。可能的原因在于当网络较大时社团结构十分明显,网络矩阵所对应的谱足够刻画社团结构。随着μ的减小,谱不足够刻画与提取网络的拓扑结构信息。这表明SS-NMF算法在提取不同规模的社团结构上有明显的优势。图11-5LFR网络上的算法性能

除了分类的准确性,算法所检测的社团规模分布也是研究分辨极限的重要指标。图11-6是社团规模累计分布率与社团规模之间的关系图,其横坐标表示社团规模,纵坐标表示累

计分布率。图中星形的点表示目标社团规模的累积分布率与社团规模之间的关系。图11-6累计概率分布率与社团规模之间的关系图

SS-NMF算法是偏离目标社团规模最小的算法,这充分

说明SS-NMF算法可在很大程度上容忍分辨极限问题,而NMF算法虽然不及SS-NMF算法,但远优于谱聚类算法,可能的原因有:

①算法不是模块度驱动函数,算法结果只取决于矩阵分解;

②SS-NMF算法同时采用多种拓扑结构,可更加有效地从多尺度、多层次刻画社团结构。

2.科学家协作网

SS-NMF算法提取出28个社团,分类数与模块密度之间的关系包含在图11-7(a)中。可以看出,SS-NMF算法在取得28个社团时,模块密度值达到最大。为了更进一步研究分辨极限问题,最大模块密度值所对应的社团规模与结构示意图包含在图11-7(b)中,其中社团的规模与圆的直径成正比,即社团规模越大,所对应圆的直径就越大;社团间连接边的粗细与连接边数成正比,即边数越多,边越粗。由图可以看出,SS-NMF算法能同时发现大规模社团与小规模社团,表明该算法对分辨极限问题有一定的免疫性。图11-7社团分布

本章小结

本章介绍了一种基于半监督非负矩阵分解的社团结构检测算法,该算法将半监督策略融入非负矩阵分解算法中。与传统算法相比,该算法同时采用多种拓扑相似性,从多层次、多尺度方面刻画社团结构,因此具有更好的预测效果。同时,该算法是非模块度函数驱动算法,对分辨极限问题有较强的容忍性。将该算法同时应用于人工计算机网络与真实世界网络,实验结果表明该算法具有更高的准确性,能更好地处理分辨极限问题。

尽管该算法具有高准确性、容忍分辨极限能力强等特点,但仍有一些需要改进的地方:

(1)时间复杂度问题。分析表明