08-社会网络分析与算法研究

社会网络中的社团挖掘问题 社团结构挖掘研究现状 ¢ 现有的社团挖掘算法主要分为两类：计算机科学中的图形分割算法和社会学中的分级聚类算法。¢ 图像分割算法主要包括Kernighan-Lin算法、谱平分法、派系过滤算法等；¢ 分级聚类算法是寻找社会网络中社团结构的一类传统算法，它基于各个节点之间连接的相似性，把网络自然地划分为各个子群，根据加边或者去边，该类算法又可以分为两类：分裂方法和凝聚算法。¢ 从其他不同的角度分析社团结构的算法还包括：基于相似度度量的凝聚算法、基于信息论的算法、基于矩阵分解的算法、最大化模块性的算法等。社团结构的定义 ¢ 网络社团结构的定义有多种，最为常见的定义有两种：一种是基于网络节点的相对连接频数，另一种是以网络连通性为评判标准。¢ 根据节点的相对连接频数将网络中的节点划分为不同的社团时，网络呈现出社团内连接稠密而社团间连接稀疏的特点。¢ 一般来讲，有强社团和弱社团两种定义：强社团是指子图H中任何一个节点与H内部节点连接的度大于其与H外部节点连接的度；弱社团是指子图H中所有节点与H内部节点的度之和大于H中所有节点和H外部节点连接的度之和。社团结构的定义 ¢ 以连通性为标准定义的社团也称为派系，一个派系是指由3个或者3个以上的节点组成的全连通子图，即任何两个节点之间均有连接。在社团的各种定义中，派系的定义最为严格，但是也可以通过弱化连接条件进行拓展，形成n－派系，这里的n是指子图中的任意两个节点之间不必直接相连，但最多通过n－1个节点能够连通。¢ 上述两种方法均可以用于定义社团，但是基于网络连通性的定义方式允许社团间存在重叠性。经典检验网络 ¢ 目前用于检验和比较的经典网络主要有两类：人造网络和实际网络。¢ 常用的人造网是由128个节点构成的网络，该网络包含4个社团，每个社团内部包含32个节点。¢ 人造网的检验虽然在一定程度上验证了划分算法的有效性，但是由于人们比较感兴趣的网络大多是实际网络，因此仍需要用实际网络对划分算法进行进一步的检验。选择用作检验的实际网络时，需要注意一下三点：¢ 1）保证构建网络的数据是方便易得的；¢ 2）保证网络有实际的意义，从而可以判断社团划分的结果是否具有可解释性；¢ 3）为了方便不同划分算法之间的比较，宜采用已被广泛使用的实际网络。经典检验网络 ¢ 空手道俱乐部网络也称为Zachary网络，是检验不同社团发现算法的一个经典实际网络。¢ 其它比较常用的实际网络有：①美国大学橄榄球比赛网；②物理学家合作网；③桑塔菲研究所科学家合作网；④经济学家合作网。常见社团挖掘方法 ¢ K-means算法¢ Kernighan－Lin算法¢ 谱平分法¢ 基于NMF的聚类算法¢ 派系过滤算法¢ 分裂算法¢ 凝聚算法K-MEANS算法 ¢ k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的社团聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点。¢ 算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。对数据集进行k－means聚类时包括如下三个要点：（1）选定某种距离作为数据样本间的相似性度量¢ k-means聚类算法在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。¢ 假设给定的数据集X={x1,x2,x3......xm}，X中的样本用n个描述属性w1,w2…wd来表示，并且n个描述属性都是连续型属性。数据样本xi=(wi1,wi2,…win),xj=(wj1,wj2,…wjn)其中，wi1,wi2,…win和wj1,wj2,…wjn分别是样本xi和xj对应n个描述属性W1,W2,…Wn的具体取值。样本xi和xj之间的相似度通常用它们之间的距离d(xi,xj)来表示，距离越小，样本xi和xj越相似，差异度越小；距离越大，样本xi和xj越不相似，差异度越大。（2）选择评价聚类性能的准则函数¢ k-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X，其中只包含描述属性，不包含类别属性。假设X包含k个聚类子集X1,X2,…XK；各个聚类子集中的样本数量分别为n1，n2,…,nk;各个聚类子集的均值代表点（也称聚类中心）分别为m1，m2,…,mk。则误差平方和准则函数公式为：（3）相似度的计算根据一个聚类中对象的平均值来进行。¢ 1)   将所有对象随机分配到k个非空的聚类中。¢ 2)   计算每个聚类的平均值，并用该平均值代表相应的聚类。¢ 3) 根据每个对象与各个聚类中心的距离，分配给距离最近的聚类。¢ 4)   然后转2），重新计算每个聚类的平均值。这个过程不断重复直到满足某个准则函数的条件才停止。算法流程¢ 输入：聚类的数目k和包含n个对象的数据样本集合。¢ 输出：k个聚类，使平方误差准则最小。¢ 算法步骤：¢ 1.为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心。¢ 2.将样本集中的样本按照最小距离原则分配到最邻近聚类。¢ 3.使用每个聚类中的样本均值作为新的聚类中心。¢ 4.重复步骤2.3步直到聚类中心不再变化。¢ 5.结束，得到K个聚类示例 ¢ 数据对象集合S见表1，作为一个聚类分析的二维样本，要求聚类的个数k=2。k-means算法的优缺点主要优点：¢ 1.  是解决聚类问题的一种经典算法，简单、快速。¢ 2.  对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度是0(nkt),其中,n是所有对象的数目,k是簇的数目,t是迭代的次数。通常kn且tn。¢ 3.  当结果聚类内部节点是密集的，而聚类与聚类之间区别明显时,它的效果较好。主要缺点¢ 1.  必须事先给出k（要生成的聚类的数目），而且对初始值敏感，对于不同的初始值，可能会导致不同结果。¢ 2.  它对于“躁声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。KERNIGHAN－LIN算法 ¢ 1970年，Kernighan和Lin提出了一种试探优化法，简称K－L算法。该算法是一种采用贪婪算法原理将网络划分为两个大小已知的社团的二分法，其基本思想在于在网络划分时引入一个增益函数Q，通过交换节点对使Q值达到最大从而获得最优的社团结构划分结果。其中，增益函数Q定义为两个社团内部的边数减去连接两个社团之间的边数所得差值。¢ 具体执行过程可以描述为：（1）初始化：人为设定社团的大小（节点数目）以及两个社团的最初配置（可以按照指定的社团大小将节点随机划分到两个社团中）。KERNIGHAN－LIN算法 ¢ （2）交换及计算：首先尝试交换所有分别取自不同社团的两个节点并计算交换前后增益函数Q的变化量，然后交换变化量最大的两个节点并记录交换后网络的Q值。不断重复上述两个操作，直到一个社团内的所有节点均被交换过。¢ （3）最优选择：考察步骤2中的所有交换后得到的Q值，找到Q最大的一次交换，该次交换所对应社团分布便认为是网络社团结构的最佳分割。¢ 需要注意：在交换的过程中，每一个节点只能被交换一次；在整个交换过程中，Q值可能不是一直单调递增的，在某次交换后Q值可能会降低。不过，这不影响在随后的过程中可能得到一个更大的Q值。KERNIGHAN－LIN算法 ¢ 该算法的缺点是算法本身没有利用网络的全局结构等信息进行分析，并且必须事先指定社团的大小，如果指定值和实际值不一致就会出现错误划分。谱平分法 ¢ 谱分析的主要思想是通过对拉普拉斯矩阵的特征值、特征向量的分析，挖掘网络中的社团结构。¢ 此处采用另外一种拉普拉斯矩阵的表示方法：L＝K－A，其中A是邻接矩阵，K是对角线元素为各节点度的对角阵。矩阵L对角线上的元素lii为节点vi的度，非对角线上的元素lij表示节点vi和节点vj的连接关系。如果节点vi和vj之间有边连接，则lij值为－1，否则为0。¢ 谱平分法的主要研究对象是网络的Laplace矩阵的谱特征，因此网络的Laplace矩阵特点会对算法的执行结果有比较大的影响。由于网络结构不同，其对应的Laplace矩阵的特点也有所不同，因此这里将从下面三种情况对算法本身进行简单描述。谱平分法 ¢ 首先考虑网络可以被划分为g个互不重叠的社团Gk，且社团之间没有边相互连接，那么此时网络的Laplace矩阵就是一个可以分为g块的对角矩阵。其中，对角矩阵的每一块对应着一个社团，同时都具有特征值为零的特征向量e（u），u＝1，2，…，g。此时，网络的Laplace矩阵共有g个特征值为零的特征向量。如果节点vi属于社团u时，则第u个特征向量的第i个元素ei（u）＝1，否则等于零。¢ 简单的一种情况：网络中只存在两个社团，但是社团间有少量连线，则此时网络的Laplace矩阵L对应两个近似对角矩阵块。在这种情况下，L只有一个特征值是零，其余特征值都大于零。谱平分法 ¢ 因为实对称矩阵非零特征值对应的特征向量是正交的，因此除了零特征值对应的特征向量之外，其它特征值对应的特征向量同时具有正元素和负元素。这样，对于只具有两个社团的网络来说，可以根据Laplace矩阵中大于零的特征值对应的特征向量的元素的正负来划分社团：正元素对应的节点属于一个社团，而负元素对应的节点属于另一个社团。¢ 一般情况：网络具有g个明显的社团结构，但社团之间有少量边的连接，此时Laplace矩阵不再是分块的对角矩阵。图的Laplace矩阵的所有特征值均是非负时，该矩阵只有一个特征值为零，其它g－1个特征值都大于零。这时，网络相应的特征向量可以大致看作是前面极端情形的特征向量e（u）的线性组合。谱平分法的性能分析 ¢ 该算法的复杂度为О（N3），用Lanczos快速算法来计算，此时算法复杂度将大约降至M／（λ3－λ2）。谱平分法的最大缺陷就是：它只能将网络划分为两个部分；如果网络有多个社团，就需要多次重复使用该算法。基于NMF的聚类方法nmR×∈V2min−VWHrnR×∈WmrR×∈HV:Datamatrix.W:MixingmatrixH:EncodingmatrixOnlyADDITIVE,notsubtractive,combinationsareallowedTheonlyconstraintisNON-NEGATIVIYofthematricesPARTS-BASEDrepresentationsofdata[1]Lee,D.D.,Seung,H.S.:LearningthePartsofObjectsbyNonnegativeMatrixFactorization.Nature,Vol.401.(1999)788-791WHV≈DEmonstrationOfNMFv1v2v3v4v5v6Datamatrix:Vnx6Wnx3H3x6,n:#ofpixelsinaframew1w2w3Mixingmatrix:Wnx30.03280.03210.38580.37750.00020.00010.31050.31230.00110.00440.00420.00220.00120.00130.03450.03540.27380.2525EncodingMatrix:H3x6≈Cluster2Cluster1Cluster3DEmonstrationOfNMFDatamatrix:Vnx6Wnx3H3x6,n:#ofpixelsinaframe≈ReconstructedImagesØ ColumnsofthemixingmatrixWcanbeconsideredasclustercentroids.Ø EachcolumnoftheencodingmatrixHisaclusterindicatorforthecorr