一种k均值社团结构挖掘方法及装置的制造方法
一种k均值社团结构挖掘方法及装置的制造方法
【技术领域】
[0001] 本发明设及网络技术领域，尤其设及一种Κ均值社团结构挖掘方法及装置。
【背景技术】
[0002] 现实世界中的许多复杂系统都可W被抽象为由节点和节点间连边组成的复杂网 络。例如，Internet网络中的网页可W看做复杂网络中的节点，页面间的超链接可W被看作 节点间的连边，从而将整个Internet抽象为复杂网络;在线社交网络中，各虚拟用户可W被 抽象为网络节点，虚拟用户之间的关注、互加好友等操作可W被视为网络之间的连边，在此 基础上，整个在线社交网络可W用复杂网络表示；国家公共交通网络中，将各城市之间的站 点作为网络节点，城市之间的交通路线作为连边，可W得到一个国家公共交通网络的抽象 网络图；生物蛋白质网络将不同生物蛋白作为网络节点并用连边掲示不同蛋白之间的相互 影响。因此，作为研究复杂系统的有效工具，复杂网络的各种性质已经引起了各界学者的广 泛关注。
[0003] 诸多科学家研究表明，复杂网络具有诸多拓扑结构性质。其中，社团结构便是复杂 网络的一个重要的拓扑特性。在复杂网络中，社团结构将复杂网络中的节点分为若干个子 集，使得社团内部的节点之间连边较为紧密而社团之间的连边则较为稀疏。运种高内聚的 网络结构可W很好的掲示复杂系统中的结构特点、功能特性W及组织特征。例如在互联网 中的社团结构反应了讨论共同话题的一些网站，而在线社交网络中的社团结构则表示了 拥有共同兴趣爱好的人组成的一个团体。因此，复杂网络中社团结构的挖掘对于分析网络 的特性和功能具有十分重要的现实意义。近些年，面对越来越多的复杂系统被抽象为复杂 网络，高精度的挖掘复杂网络中的社团结构对于分析复杂系统的物理特性具有重要的意 义。但是目前的挖掘社团精度不高，从而影响了后续对系统分析的准确性。
【发明内容】
[0004] 鉴于上述的分析，本发明旨在提供一种K均值社团结构挖掘方法及装置，用W解决 现有技术中挖掘社团精度不高的问题。
[0005] 本发明主要是通过W下技术方案实现的：
[0006] 本发明一方面提供了一种K均值社团结构挖掘方法，该方法包括：
[0007] 基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种子社团的 中屯、节点作为初始种子节点，所述中屯、节点坐标作为K均值聚类种子节点的坐标值，其中，K E[2，N-1];
[000引将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当前K值下的社 团结构划分；
[0009]获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结果的模块度 值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最佳划分结果 中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。
[0010] 优选地，该方法还包括：
[0011] 根据复杂网络G的邻接矩阵A计算各网络节点对之间的相同直接邻居节点的数目 并组成相似度矩阵S，根据相似度矩阵计算网络中各网络节点间的距离矩阵D;
[0012]其中，所述邻接矩阵A为具有N个节点VI的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点Vj之间有边相连时，aij = 1;当节点巧日j之间无直接连边时，aij = 0，其中，aij为 邻接矩阵A中的各元素，具体表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i = j 时，au = 0;所述的相似度矩阵S为具有N个节点vi的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点vj之间有边相连时，sij = (Ai.，Aj.);当节点i和j之间无直接连边时，sij = 0,其 中sij为S中的各元素 ，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i
行元素组成的向量， 所述的离矩阵D为具有N个节点Vi的复杂网络图G，构 造 1'^NXN的矩阵,dij = (sii+sj广2sij)l/2,其中，sij为S中的各兀素 ，i = l,2,...,N,j = l, 2,...,Ν；
[0013] 利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维 标度法MDS具体包括:利用D = UAIJT对矩阵D进行分解，其中，八= diag{Ai，A2, . . .，λΝ}为一 个对角矩阵，且每个元素 λι表示矩阵D的特征值，不失一般性的，令λι含λ2含...含λΝ，即将特 征值按降序排列，矩阵U中的第i列为特征值λι对应的特征向量，若在λι含λ2含...含λΝ中，存 在Ρ个特征值大于零，ρΕ [1 ,Ν]，则选择Ρ个特征值对应的特征向量记为ui，U2,...，叫，并将 其组成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（XI， X2, . . . ,Χν)；
[0014] 所述基于局部扩展的种子筛选法选择Κ个初始种子社团，并计算各个初始种子社 团的中屯、节点作为初始种子节点具体包括：
[0015] 基于局部扩展的种子筛选法选择Κ个初始种子社团，并根据网络节点的欧氏坐标 计算各个初始种子社团的中屯、坐标作为各个初始种子社团的初始种子节点。
[0016] 优选地，所述基于局部扩展的种子筛选法选择Κ个初始种子社团，并根据网络节点 的欧氏坐标计算各个初始种子社团的中屯、坐标作为各个初始种子社团的初始种子节点具 体包括：
[0017]将复杂网络G中的每个节点均设置一个标志位Si(i = l，2, . . .，Ν)，0表示该节点未 被标识，1表示该节点已被标识；
[0018] 查找该网络中的所有完全子图，根据
计算查找到的每个完全子图中 权值的平均值，并按照从大到小的顺序排序，用Gi>G2> . . . >Gm表示；
[0019] 在当前节点标志位为0的节点中选择度数最大的节点，设该节点为a,在Gi，G2, ...， Gm中选择包含节点a的完全子图组成子集{啤，巧，，…，.巧,}:，r为从巧IjM之间的任意自然数，并 在该子集中选取符合条件（1)和条件(2)的完全子图Gi，将其中屯、节点坐标作为一个初始的 种子节点：
[0020] 条件(1) :Gi中的所有节点的标志位均为0;
[0021 ]条件（2) :Gi > Gj，对于任意(J/ 居.Kj,.|?";;
[0022] 初始化节点子集Ω = 0，W选择的初始种子社团G 1作为核屯、，根据
扩展Gi的范围，其中，α和β为取值范围在0至1之间的实数，对于Gi的直接 邻居节点V，设将V加入子图Gi后的子图用Gi+v表示，根据公式
得到的子 图连边紧密度为巧?+，，若，则将节点V加入子图Gi，否则，不将节点V加入子图Gi中， 将凡是能够使得子图Gi的连边密度增大的邻居节点均放入节点子集Ω中，直到公式
不再增大为止，并将集合Ω中的各节点的标志位均设置为1;
[0023] 若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标示的完全子 图，且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余的种子 节点；
[0024] 所述相互距离最远原则具体包括:设当前已查到0/ (0/ Ε[Θ + 1，Κ])个种子节点的 坐标为yi，y2,...，ye'，网络中除种子节点之外的节点的坐标为〇1，〇2,...，〇Ν-θ'，则采用相互 距离最远原则选择的剩余种子节点0的坐标为网络中除了yi，y2,...，ye'之外的节点坐标 中，符合下式
的节点，〇/ E {〇1，〇2, . . .，ΟΝ-θ< }，计算K个种子社团中 各节点通过MDS映射后的中屯、坐标，作为Κ均值的初始种子节点的坐标{χΛκ^，... yd ;
[0025] 所述的各初始种子社团中屯、坐标的计算方式为:对于已查找到的种子社团Gi，i = 1，2, . . .，Κ，设其包含g个节点，各节点坐标为yi，y2, . . .，yg，则种子社团中屯、坐标为
[0026] 优选地，所述将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当 前K值下的社团结构划分具体包括：
[0027] 步骤（1)，将(x/，X2/，...，χ/κ)作为初始聚类中屯、，将K个集合Zi设置为空集，其中 i = 1,2,. . . ,Κ，设置为至集；
[00%]步骤(2)，循环(3巧ΙΚ4)直到每个聚类不再发生变化为止；
[0029] 步骤(3)，在第t次迭代中，对网络中的任一节点坐标X"按如下的方法把它调整到Κ 个类别中的某一类别中去，对于某一类别1，其中1 = 1，2，...，1(，若所有的_]'辛1，其中〇 = 1，2，...，Κ，如果 l<llx"-x/j| I，则 x"EZi，其中，t 为从1 开始的自然数，I |a-b| 为坐标a与b之间的欧氏距离，设a和b均为P维向量；
[0030] 步骤(4)，由第(3)步计算第i类的新中屯、坐标的第j个分量
式中， Zi|为Zi类中元素的数目。则第i类的中屯、坐标为：^/11，义/12，...，义/11()。根据新得到的中屯、 坐标计算J'的值为：
若|户-引<8，则退出程序，输出聚类结果21 (i = l，2,. . .，Κ)，反之，令J = J'，转步骤(3)。
[0031] 优选地，所述获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结 果的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最 佳划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果具体包 括：
[0032] 对复杂网络图G进行社团划分C，记C=ki，C2, . . .，cp}，其中，P为从1开始到N之间 的任意自然数，Cia = l，2，...，p)为复杂网络图G中若干节点组成的集合，计算当前社团划 分下的模块度
为网络节点Vi与网络中 其他节点的连边数目，其中，i = l，2, . . .，N，M为网络连边的数目，Cm和Cn分别为节点VI和Vj 所属的社团的编号，其中，me[l，p]，ne[l，p]，
[0033] 本发明另一方面还提供了一种K均值社团结构挖掘装置，该装置包括：
[0034] 计算单元，用于基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初 始种子社团的中屯、节点作为初始种子节点，所述中屯、节点坐标作为K均值聚类种子节点的 坐标值，其中，Ke[2，N-l];
[0035] 获取单元，用于将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在 当前K值下的社团结构划分；
[0036] 处理单元，用于获取在不同K值下的社团结构划分，计算不同参数值K下社团划分 结果的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将 最佳划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。
[0037] 优选地，该装置还包括:映射单元；
[0038] 所述映射单元，用于根据复杂网络G的邻接矩阵A计算各网络节点对之间的相同直 接邻居节点的数目并组成相似度矩阵S，根据相似度矩阵计算网络中各网络节点间的距离 矩阵D;其中，所述邻接矩阵A为具有N个节点VI的复杂网络图G，构造一个NXN的矩阵，当节 点Vi和节点vj之间有边相连时，au = l;当节点巧Pj之间无直接连边时，au = 0,其中，aij为邻 接矩阵A中的各元素，具体表示节点间的连边关系，i = l，2, ...，N，j = l，2，...，N;当i = j 时，au = 0;所述的相似度矩阵S为具有N个节点VI的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点Vi之间有边相连时，sij = (Ai.，Aj.);当节点i和j之间无直接连边时，sij = 0,其 中sij为S中的各元素 ，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i 行元素组成的向量：
所述的离矩阵D为具有N个节点VI的复杂网络图G，构 造 1'^NXN的矩阵,dij = (sii+sj广2sij)l/2,其中，sij为S中的各兀素 ，i = l,2,...,N,j = l, 2, ...，N;利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维 标度法MDS具体包括:利用D = UAIJT对矩阵D进行分解，其中，八= dia g{Ai，A2, . . .，λΝ}为一 个对角矩阵，且每个元素 λι表示矩阵D的特征值，不失一般性的，令λι含λ2含...含λΝ，即将 特征值按降序排列，矩阵帅的第i列为特征值λι对应的特征向量，若在λι > λ2 > ...含λΝ中， 存在p个特征值大于零，pE[l,N]，则选择p个特征值对应的特征向量记为m，U2,...，叫，并 将其组成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（XI， X2, . . . ,Χν)；
[0039] 所述计算单元具体用于，基于局部扩展的种子筛选法选择Κ个初始种子社团，并根 据网络节点的欧氏坐标计算各个初始种子社团的中屯、坐标作为各个初始种子社团的初始 种子节点。
[0040] 优选地，所述计算单元具体用于，将复杂网络G中的每个节点均设置一个标志位δι (i = l，2,...，Ν)，0表示该节点未被标识，1表示该节点已被标识;查找该网络中的所有完全 子图，根据
计算查找到的每个完全子图中权值的平均值，并按照从大到小的 顺序排序，用Gi含G2含...含Gm表示;在当前节点标志位为0的节点中选择度数最大的节点， 设该节点为曰，在Gi，G2, . . .，Gm中选择包含节点a的完全子图组成子集{吗，巧。，…，砖}，r为从1 到M之间的任意自然数，并在该子集中选取符合条件（1)和条件(2)的完全子图Gi，将其中屯、 节点坐标作为一个初始的种子节点:条件（l):Gi中的所有节点的标志位均为0;条件(2) :Gi >&，对于任意6,.€巧而:..…h初始化节点子集0 = 0，W选择的初始种子社团Gi作为 核屯、，根据
展Gi的范围，其中，α和β为取值范围在0至1之间的实数，对 于Gi的直接邻居节点V，设将V加入子图Gi后的子图用Gi + v表示，根据公式
得到的子图连边紧密度为馬W，若馬+K ^巧;则将节点V加入子图Gi，否 则，不将节点V加入子图Gi中，将凡是能够使得子图Gi的连边密度馬增大的邻居节点均放 入节点子集Ω中，直到公式
不再增大为止，并将集合Ω中的各节点的标 志位均设置为1;若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标示的 完全子图，且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余 的种子节点;所述相互距离最远原则具体包括:设当前已查到Θ/ (0/ Ε[Θ+1，Κ])个种子节点 的坐标为yi，y2,...，ye'，网络中除种子节点之外的节点的坐标为01,02,...，〇Ν-θ'，则采用相 互距离最远原则选择的剩余种子节点0的坐标为网络中除了yi，y2,...，ye'之外的节点坐标 中，符合下iS：
的节点，c/ E {〇1,〇2, . . . ,ΟΝ-θ< }，计算K个种子社团中 各节点通过MDS映射后的中屯、坐标，作为Κ均值的初始种子节点的坐标{χ/，Χ2/，. . .，χ^κ}; 所述的各初始种子社团中屯、坐标的计算方式为:对于已查找到的种子社团Gi，i = l，2,...， K，设其包含g个节点，各节点坐标为y 1，y 2，. . .，y g，则种子社团中屯、坐标为
[0041] 优选地，所述获取单元具体用于，步骤（1)，将(X/，X2/，. . .，χ^κ)作为初始聚类中 屯、，将κ个集合Zi设置为空集，其中1 = 1，2，...，1(，设置为空集;步骤(2)，循环(3巧1](4)直到 每个聚类不再发生变化为止;步骤(3)，在第t次迭代中，对网络中的任一节点坐标X"按如下 的方法把它调整到K个类别中的某一类别中去，对于某一类别i，其中i = l，2，...，Κ，若所有 的占'辛1，其中〇 = 1，2，...，1(，如果|^"-义1/||<|^"-义/^||，则义"￡21，其中，*为从1开始的 自然数，||a-b II为坐标a与b之间的欧氏距离，设a和b均为Ρ维向量;步骤(4)，由第(3)步计 算第i类的新中屯、坐标的第j个分量
式中，I Zi I为Zi类中元素的数目。则第i 类的中屯、坐标为：（χ/ι?，χ/ι2, . . .，χ^ικ)。根据新得到的中屯、坐标计算的值为：
，若lJ'-Jl<S，则退出程序，输出聚类结果Zl(i = l，2，...，K)，反 之，令J = r，转步骤(3)。
[0042] 优选地，所述处理单元具体用于，对复杂网络图G进行社团划分C，记C={ci， C2, . . .，cp}，其中，P为从1开始至阳之间的任意自然数，ci(i = l，2, . . .，p)为复杂网络图G中 若干节点组成的集合，计算当前社团划分下的模块度
，式 中
，，为网络节点Vi与网络中其他节点的连边数目，其中，i = l，2，. . .，N，M为网 络连边的数目，Cm和Cn分别为节点VI和Vj所属的社团的编号，其中，me[l，p]，ne[l，p]，
[0043] 本发明通过合理选择聚类中屯、作为K均值聚类算法中的初始种子节点，最后利用K 均值算法在低维欧氏空间中聚类网络节点，并聚类隶属于同一社团的网络节点，从而提高 了挖掘社团精度，进而提高了后续对系统分析的准确性。
[0044] 本发明的其他特征和优点将在随后的说明书中阐述，并且部分的从说明书中变得 显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在所写的说明书、 权利要求书、W及附图中所特别指出的结构来实现和获得。
【附图说明】
[0045] 图1为本发明实施例的一种K均值社团结构挖掘方法的流程示意图；
[0046] 图2为本发明实施例的另一种K均值社团结构挖掘方法的流程示意图；
[0047] 图3为本发明实施例在空手道俱乐部网络下得到的具有重叠的社区结构示意图； [004引图4为本发明实施例的一种K均值社团结构挖掘装置的结构示意图。
【具体实施方式】
[0049] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完 整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于 本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他 实施例，都属于本发明保护的范围。
[0050] 本发明利用皮尔逊相关系数公式衡量复杂网络各节点之间的相似度，通过多维标 度法将网络节点映射为低维欧氏空间中的节点坐标，在此基础上，根据复杂网络中社团结 构的拓扑特征提出了一种基于局部扩散的K均值改进算法，该算法合理选择聚类中屯、并且 根据社团拓扑结构特点聚类隶属于同一社团的网络节点。与现有技术相比，本发明克服了 传统基于K均值社团挖掘方法中种子节点随机选择从而导致精度较差的局限性，提高了社 团挖掘方法的精确度，很好的解决了复杂网络中社团结构的挖掘问题。为了更好的理解本 发明，下面仅W几个具体的例子对本发明进行详细的说明。
[0051 ]系统实施例
[0052] 本发明实施例提供了一种K均值社团结构挖掘方法，参见图1，该方法包括：
[0053] S101、基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种子社 团的中屯、节点作为初始种子节点，所述中屯、节点坐标作为K均值聚类种子节点的坐标值，其 中，Ke[2，N-l];
[0054] S102、将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当前K值 下的社团结构划分；
[0055] S103、获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结果的模 块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最佳划分 结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。
[0056] 本发明通过合理选择聚类中屯、作为K均值聚类算法中的初始种子节点，最后利用K 均值算法在低维欧氏空间中聚类网络节点，并聚类隶属于同一社团的网络节点，从而提高 了挖掘社团精度，进而提高了后续对系统分析的准确性。
[0057] 本发明实施例所述的方法还包括:根据复杂网络G的邻接矩阵A计算各网络节点对 之间的相同直接邻居节点的数目并组成相似度矩阵S，根据相似度矩阵计算网络中各网络 节点间的距离矩阵D;
[0058] 利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标；
[0059] 其中，所述邻接矩阵A为具有N个节点VI的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点Vj之间有边相连时，aij = 1;当节点巧日j之间无直接连边时，aij = 0，其中，aij为 邻接矩阵A中的各元素，具体表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i = j 时，au = 0;所述的相似度矩阵S为具有N个节点vi的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点vj之间有边相连时，sij = (Ai.，Aj.);当节点i和j之间无直接连边时，sij = 0,其 中sij为S中的各元素 ，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i 行元素组成的向量，
所述的离矩阵D为具有N个节点VI的复杂网络图G，构 造一个NXN的矩阵，dij = (sii+sjj-2sij)l/2，其中，sij为S中的各元素 ，i = l，2，...，N，j = l， 2,...,Ν；
[0060] 利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维 标度法MDS具体包括:利用D = UAIJT对矩阵D进行分解，其中，八=diag{Ai，A2, . . .，λΝ}为一 个对角矩阵，且每个元素 λι表示矩阵D的特征值，不失一般性的，令λι含λ2含...含λΝ，即将特 征值按降序排列，矩阵U中的第i列为特征值、对应的特征向量，若在λι含λ2含...含λΝ中，存 在Ρ个特征值大于零，ρΕ[1，Ν]，则选择Ρ个特征值对应的特征向量记为m，U2,...，叫，并将 其组成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（XI， X2, . . . ,Χν)；
[0061] 本发明实施例所述基于局部扩展的种子筛选法选择Κ个初始种子社团，并计算各 个初始种子社团的中屯、节点作为初始种子节点具体包括：
[0062] 基于局部扩展的种子筛选法选择Κ个初始种子社团，并根据网络节点的欧氏坐标 计算各个初始种子社团的中屯、坐标作为各个初始种子社团的初始种子节点。
[0063] 具体实施时，本发明通过将复杂网络G中的每个节点均设置一个标志位Si(i = l， 2,...，N)，0表示该节点未被标识，1表示该节点已被标识；
[0064] 查找该网络中的所有完全子图，根巧
计算查找到的每个完全子图中 权值的平均值，并按照从大到小的顺序排序，用Gi>G2> . . . >Gm表示；
[0065] 在当前节点标志位为0的节点中选择度数最大的节点，设该节点为a,在Gi，G2, ...， Gm中选择包含节点a的完全子图组成子集!G,,，的，…，(：y，r为从巧IjM之间的任意自然数，并 在该子集中选取符合条件（1)和条件(2)的完全子图Gi，将其中屯、节点坐标作为一个初始的 种子节点：
[0066] 条件(1) :Gi中的所有节点的标志位均为0;
[0067] 条件U):Gi 含 Gj，对于任意巧 €仍,，(;,:，...，6',. h
[006引初始化节点子集Ω = 0，W选择的初始种子社团G 1作为核屯、，根据
扩展Gi的范围，其中，α和β为取值范围在0至1之间的实数，对于Gi的直接 邻居节点V，设将V加入子图Gi后的子图用Gi+v表示，根据公式
得到的子 图连边紧密度为巧，若馬^巧^.，则将节点V加入子图Gi，否则，不将节点V加入子图Gi中， 将凡是能够使得子图Gi的连边密度巧^增大的邻居节点均放入节点子集Ω中，直到公式
不再增大为止，并将集合Ω中的各节点的标志位均设置为1;
[0069] 若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标示的完全子 图，且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余的种子 节点；
[0070] 计算K个种子社团中各节点通过MDS映射后的中屯、坐标，作为K均值的初始种子节 点的坐标(XI'，X2'，. . .，Χ'Κ)。
[0071] 所述相互距离最远原则具体包括:设当前已查到0/(9/ e[9+l ，K])个种子节点的 坐标为yi，y2,...，ye'，网络中除种子节点之外的节点的坐标为〇1，〇2,...，〇Ν-θ'，则采用相互 距离最远原则选择的剩余种子节点0的坐标为网络中除了yi，y2,...，ye'之外的节点坐标 中，符合下王
的节点，c/ E {〇1,〇2, . . . ,ΟΝ-θ< }，计算K个种子社团中 各节点通过MDS映射后的中屯、坐标，作为Κ均值的初始种子节点的坐标{χΛκ^，... yd ;
[0072] 所述的各初始种子社团中屯、坐标的计算方式为:对于已查找到的种子社团Gi，i = 1，2，. . .，Κ，设其包含g个节点，各节点坐标为yi，y2，. . .，yg，则种子社团中屯、坐标为
[0073] 具体来说，本发明实施例所述将所述初始种子节点的坐标作为输入参数进行K均 值聚类，获取在当前K值下的社团结构划分具体包括：
[0074] 步骤（1)，将(χΛχ2^，...，χ/κ)作为初始聚类中屯、，将K个集合Zi设置为空集，其中 i = l，2，...，K，设置为空集；
[0075] 步骤(2)，循环(3巧lj(4)直到每个聚类不再发生变化为止；
[0076] 步骤(3)，在第t次迭代中，对网络中的任一节点坐标X"按如下的方法把它调整到K 个类别中的某一类别中去，对于某一类别i，其中1 = 1，2，...，1(，若所有的_]'辛1，其中〇 = 1， 2, . . .，Κ，如果 I I I I < I I j I I，则X" eZi，其中，t为从1 开始的自然数，I I a-b I I 为 坐标a与b之间的欧氏距离，设a和b均为P维向量；
[0077] 步骤(4)，由第(3)步计算第i类的新中屯、坐标的第j个分量
式中， Zi|为Zi类中元素的数目。则第i类的中屯、坐标为：^/11，义/12，...，义/11()。根据新得到的中屯、 坐标计算J'的值为：
若|户-引<8，则退出程序，输出聚类结果21 (i = l，2,. . .，Κ)，反之，令J = J'，转步骤(3)。
[0078] 具体实施时，本发明实施例所述获取在不同K值下的社团结构划分，计算不同参数 值K下社团划分结果的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最 佳划分结果，将最佳划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终 划分结果具体包括：
[0079] 对复杂网络图G进行社团划分C，记C=レl，C2，...，Cp}，其中，p为从l开始到N之间 的任意自然数，Cia = l，2，...，p)为复杂网络图G中若干节点组成的集合，计算当前社团划 分下的模块度
为网络节点VI与网络 中其他节点的连边数目，其中，i = l，2, ...，N，M为网络连边的数目，Cm和Cn分别为节点VI和 Vj所属的社团的编号，其中，me[l，p]，ne[l，p]，
[0080] 图2为本发明实施例的另一种K均值社团结构挖掘方法的流程示意图，下面将结合 图2对本发明所述的方法进行详细的说明：
[0081] 输入:一个具有N个节点的复杂网络图G的邻接矩阵A。
[0082] 输出：复杂网络G的一个合理的社团结构划分C= ，C2，. .，cm}。
[0083] 步骤1、根据复杂网络的邻接矩阵计算各节点对之间的相同直接邻居节点的数目 并组成相似度矩阵S，根据相似度矩阵计算网络中各节点间的距离矩阵D;
[0084] 所述步骤1，具体如下：
[0085] 1.1获取复杂网络的邻接矩阵A，记A= (aij)NXN;
[0086] 所述的复杂网络图G=(V，E)为具有N个节点vi(i = l，2，. . .，N)，M条连边ek化=1， 2, . . .，M)的网络拓扑图，其中，V=(V1，V2, . . .，VN)表示网络节点的集合，E=(ei，e2, . . .，eM) 表示网络连边的集合，边ek按照其所连接的两个节点vi、vj，记为eij;
[0087] 所述的邻接矩阵A是指对于该具有N个节点VI的复杂网络图G，构造一个NXN的矩 阵，当节点Vi和节点Vj之间有边相连时，aij = 1;当节点i和j之间无直接连边时，aij = 0，其 中，ai功邻接矩阵A中的各元素，表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i =j时，aij = 〇;
[0088] 所述的相似度矩阵S是指对于该具有N个节点vi的复杂网络图G，构造一个NXN的 矩阵，当节点Vi和节点Vj之间有边相连时，Sij= (Ai.，Aj.);当节点巧日j之间无直接连边时， sij = 0,其中3^为5中的各元素 ，i = l，2, . . .，N，j = l，2, . . .，N;当 1 = j时，sij = 0;Ai.表示 矩阵A的第i行元素组成的向量，
[0089] 所述的距离矩阵D是指对于该具有N个节点Vi的复杂网络图G，构造一个NX N的矩 阵，dij = (sii+sjj-2sij)i/2。其中sij为S中的各兀素 ，i = l,2,. . . ,N，j = l,2,. . . ,Ν。
[0090] 步骤2、利用多维标度法(MDS)将各网络节点映射为低维欧氏空间中的节点坐标；
[0091] 所述步骤2,具体如下：
[0092] 2.1利用公式(1)对矩阵D进行分解，公式(1)如下：
[0093] D = U 八 IJT (1)
[0094] 其中，Λ =diag{Ai，A2, . . .，λΝ}为一个对角矩阵，且每个元素、表示矩阵D的特征 值，不失一般性的，令λ? ^ λ2 ^ ^ λΝ，即将特征值按降序排列。矩阵U中的第i列为特征值 Ai对应的特征向量。
[0095] 2.2若在λι > λ2 > . . . > λΝ中，存在P个特征值大于零，pe [1 ,Ν]，则选择P个特征值 对应的特征向量记为m，U2,...，up，并将其组成矩阵Ρ的列。
[0096] 2.3取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（xi，X2, ...， XN)。
[0097] 步骤3、根据基于局部扩展的种子筛选子方法选择K个初始种子社团，并根据网络 节点的欧氏坐标计算该种子社团的中屯、坐标作为K个初始种子节点；
[0098] 所述步骤3,具体如下：
[0099] 所述基于局部扩展的种子筛选子方法，其特点如下：
[0100] 该方法包括W下步骤：
[0101] 输入:一个具有N个节点的复杂网络图G的邻接矩阵AW及种子节点数目K。
[0102] 输出:K个种子节点的坐标。
[0103] 步骤①:为复杂网络G中的每个节点设置一个标志位Si(i = l，2, . . .，N)，该标志位 为取值为0或者1的数字，0表示该节点未被标识，1表示该节点已被标识。
[0104] 步骤②:查找该网络中的所有完全子图，根据公式(4-8)计算查找到的每个完全子 图中权值的平均值，并按照从大到小的顺序排序，用Gi>G2> ...含Gm表示。
[0105]
[0106] 所述的完全子图为具有如下特点的子图，子图G/=(y/，E/)具有沪个节点Vi(i = 1，2，. . .，N')，则其边数Μ' =N' (Ν' -1 )/2。
[0107] 步骤③:在当前节点标志位为0的节点中选择度数最大的节点，设该节点为a。在 Gi，G2, . . .，Gm中选择包含节点a的完全子图组成子集巧,，G,:，…，G, ^ >并在该子集中选取符合 如下条件的完全子图Gi，将其中屯、坐标作为一个初始的种子节点：
[0108] (1 )Gi中的所有节点的标志位均为0;
[0109] (^Gi > Gj，对于任意巧€巧，馬，…，巧,}。
[0110] 步骤④:初始化节点子集Ω = 0 dW步骤③中选择的初始种子社团Gi作为核屯、，根 据公式(4-9)扩展Gi的范围。
[0111]
[0112] 其中，α和β为取值范围在0至1之间的实数。对于Gi的直接邻居节点V，设将V加入子 图Gi后根据公式(4-9)得到的子图连边紧密度为巧若&,+，' ，则将节点V加入子图 Gi;若&刊<馬，贝怀将节点V加入子图Gi中。将凡是能够使得子图Gi的连边密度&增大的 邻居节点均放入节点子集Ω中，直到公式(4-9)不再增大为止。
[0113] 步骤⑤:将集合Ω中的各节点的标志位均设置为1，表示该节点可能与已有种子节 点属于同一社团，从而在后续种子查找过程中不再考虑该节点。
[0114] 步骤⑥:若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标示 的完全子图，则转步骤⑦，否则，转步骤③。
[0115] 所述K为预先设定的正自然数，其取值范围为[2，N]。
[0116] 步骤⑦:若当前W查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择 剩余的种子节点。
[0117] 步骤⑧:计算K个种子社团中各节点通过MDS映射后的中屯、坐标，作为K均值的初始 种子节点的坐标(X1'，X2'，...，X'K)。
[0118] 步骤4、将步骤3中查找到的K个种子作为输入参数进行K均值聚类，获取在当前K值 下的社团结构划分；
[0119] 所述步骤4,具体如下：
[0120] 所述的K均值算法包含如下步骤：
[0121] 输入:聚类个数K，N个节点的坐标(xi，X2, . . .，XN)和初始的K个种子节点坐标(x/， X2' , . . . ,Χ' K)。
[0122] 输出：满足方差最小标准的Κ个聚类。
[0123] 步骤(1):将(xi'，X2'，. . .，χ'κ)作为初始聚类中屯、；
[0124] 步骤(2):循环(3巧lj(4)直到每个聚类不再发生变化为止；
[0125] 步骤(3):在第t次迭代中，将K个集合21。= 1，2，...，1〇设置为空集。对网络中的 任一节点坐标X"按如下的方法把它调整到K个类别中的某一类别中去。对于某一类别i(i = l，2，...，K)，若所有的j辛i(j = l，2，...，K)，如果Mx"-χi'M<Mx"-χ'jM，则x"eZi。
[01%]所述t为从1开始的自然数。Ma-b||表示坐标a与b之间的欧氏距离，设a和b均为p 维向量。
[0127]步骤(4):由第(3)步计算第i类的新中屯、坐标的第j个分量 [012 引
[0129] 式中，|Zi|为Zi类中元素的数目。则第i类的中屯、坐标为：（Χ'ι1，Χ'ι2，...，Χ'ιΚ)4! 据新得到的中屯、坐标计算r的值为：
[0130]
[013。 若I -J I < δ，则退出程序，输出聚类结果Zi (i = 1，2，. . .，K)，反之，令J = r，转步 骤(3)。
[0132] 步骤5、对于每个KE [2，N-1 ]，均运行步骤3至步骤4，从而获取在不同K值下的社团 结构划分。计算计算不同参数值K下社团划分结果的模块度值，选取能使模块度值最大的节 点聚类结果作为最佳划分结果。将最佳划分结果中属于同一类的节点作为一个社团结构， 得到最终划分结果。
[0133] 所述步骤5,具体如下：
[0134] 所述模块度公式为:对复杂网络图G进行社团划分C，记〔=山1，〇2，...，〇。}，其中， ci(i = l，2, . . .，p)分别为复杂网络图G中若干节点组成的集合，计算当前社团划分C下的模 块度化，公式如下：
[0135]
[0136] 式中：
表示网络节点VI的度，即指该节点VI与网络中其他节点的连边 数目，其中，i 二 1,2,...,Ν;
[0137] Μ表示网络连边的数目；
[013引 Cm和cn分别表示节点Vi和vj所属的社团的编号，其中me [1 ,ρ]，ne [1 ,ρ];
[0139] S(Cm，Cn)函数由式(3)所示：
[0140]
[0141] 本发明将利用皮尔逊相关系数公式衡量复杂网络各节点之间的相似度，通过多维 标度法将网络节点映射为低维欧氏空间中的节点坐标，在此基础上，根据复杂网络中社团 结构的拓扑特征提出了一种基于局部扩散的K均值改进算法，该算法合理 选择聚类中屯、并 且根据社团拓扑结构特点聚类隶属于同一社团的网络节点。与现有技术相比，本发明克服 了传统基于K均值社团挖掘方法中种子节点随机选择从而导致精度较差的局限性，提高了 社团挖掘方法的精确度，很好的解决了复杂网络中社团结构的挖掘问题。
[0142] 图3为本发明实施例在空手道俱乐部网络下得到的具有典型的社区结构示意图， 下面将结合图3对本实施例采用社会网络中的经典数据集Zacha巧空手道俱乐部网络进行 社团结构挖掘进行说明，该网络包含34个节点和78条边，α和肚匀取1。具体包括步骤如下：
[0143] 步骤1，根据复杂网络的邻接矩阵计算各节点对之间的相同直接邻居节点的数目 并组成相似度矩阵S，根据相似度矩阵计算网络中各节点间的距离矩阵D;
[0144] 步骤2,利用多维标度法(MDS)将各网络节点映射为2维欧氏空间中的节点坐标；
[0145] 步骤3,根据基于局部扩展的种子筛选子算法选择K个初始种子社团，并根据网络 节点的欧氏坐标计算该种子社团的中屯、坐标作为K个初始种子节点。例如，当Κ = 2时，经过 种子筛选子算法计算得到的2个种子社团为{1，2，"和{30,33,34}，贝化=2时的种子坐标即 为运两个种子社团的节点对应坐标的中屯、坐标；
[0146] 步骤4,将步骤3中查找到的K个种子作为输入参数进行K均值聚类，获取在当前K值 下的社团结构划分；
[0147] 步骤5,对于每个Ke[2,33]，均运行步骤3至步骤4,从而获取在不同K值下的社团 结构划分。计算计算不同参数值K下社团划分结果的模块度值，选取能使模块度值最大的节 点聚类结果作为最佳划分结果。将最佳划分结果中属于同一类的节点作为一个社团结构， 得到最终划分结果。该例中，当Κ = 2时，社团划分的模块度值最大，故该结果即为最终结果。 [014引装置实施例
[0149] 本发明实施例提供了一种Κ均值社团结构挖掘装置，参见图4,该装置包括：
[0150] 计算单元，用于基于局部扩展的种子筛选法选择Κ个初始种子社团，并计算各个初 始种子社团的中屯、节点作为初始种子节点，所述中屯、节点坐标作为Κ均值聚类种子节点的 坐标值，其中，Ke[2，N-l];
[0151] 获取单元，用于将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在 当前K值下的社团结构划分；
[0152] 处理单元，用于获取在不同K值下的社团结构划分，计算不同参数值K下社团划分 结果的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将 最佳划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。
[0153] 本发明通过合理选择聚类中屯、作为K均值聚类算法中的初始种子节点，最后利用K 均值算法在低维欧氏空间中聚类网络节点，并聚类隶属于同一社团的网络节点，从而提高 了挖掘社团精度，进而提高了后续对系统分析的准确性。
[0154] 优选地，本发明实施例所述的装置还包括:映射单元;所述映射单元，用于根据复 杂网络G的邻接矩阵A计算各网络节点对之间的相同直接邻居节点的数目并组成相似度矩 阵S，根据相似度矩阵计算网络中各网络节点间的距离矩阵D;其中，所述邻接矩阵A为具有N 个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点Vi和节点vj之间有边相连时，au = l; 当节点i和j之间无直接连边时，aij = 0，其中，aij为邻接矩阵A中的各元素，具体表示节点间 的连边关系，i = l，2,. . .，N，j = l，2, . . .，N;当i = j时，aij = 0;所述的相似度矩阵S为具有N 个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点Vi和节点vj之间有边相连时，sij = (Ai.，Aj.);当节点巧Pj之间无直接连边时，sij = 0,其中sij为S中的各元素 ，i = l，2,. . .，N，j = 1,2, . . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i行元素组成的向量，
所述的离矩阵D为具有N个节点Vi的复杂网络图G，构造一个NXN的矩 阵，dij = (sii+sjj-2sij)1/2,其中，sij为S中的各兀素 ，i = l,2, . . . ,N，j = l,2,. . . ,Ν;利用多 维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维标度法MDS具体包 括:利用D = UAUT对矩阵D进行分解，其中，Λ =diag{Ai，A2, . . .，λΝ}为一个对角矩阵，且每 个元素 λι表示矩阵D的特征值，不失一般性的，令λι含λ2含...含λΝ，即将特征值按降序排列， 矩阵U中的第i列为特征值λι对应的特征向量，若在λι含λ2含...含λΝ中，存在Ρ个特征值大 于零，ρΕ[1,Ν]，则选择Ρ个特征值对应的特征向量记为m，U2,...，叫，并将其组成矩阵Ρ的 列，取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（xi，X2，...，孙）；
[0155] 优选地，本发明实施例所述的计算单元具体用于，将复杂网络G中的每个节点均设 置一个标志位Si(i = l，2,. . .，N)，0表示该节点未被标识，1表示该节点已被标识;查找该网 络中的所有完全子图，根巧
计算查找到的每个完全子图中权值的平均值，并 按照从大到小的顺序排序，用Gi>G2> ...含Gm表示;在当前节点标志位为0的节点中选择度 数最大的节点，设该节点为曰，在Gi，G2, ...，Gm中选择包含节点a的完全子图组成子集 朽,，馬，·…^!·，r为从1到Μ之间的任意自然数，并在该子集中选取符合条件（1)和条件(2) 的完全子图Gi，将其中屯、节点坐标作为一个初始的种子节点:条件（1): Gi中的所有节点的标 志位均为0;条件(2):Gi含&，对于任意皆MG,,，G,:，...，巧};初始化节点子集Ω = 0，W选择 的初始种子社团Gi作为核屯、，根巧
扩展Gi的范围，其中，α和β为取值范围 在0至1之间的实数，对于Gi的直接邻居节点V，设将V加入子图Gi后的子图用Gi+v表示，根据 公式
得到的子图连边紧密度为，:若^ ，側将节点V加入子图 Gi，否则，不将节点V加入子图Gi中，将凡是能够使得子图Gi的连边密度&增大的邻居节点 均放入节点子集Ω中，直到公式
不再增大为止，并将集合Ω中的各节点 的标志位均设置为1;若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标 示的完全子图，且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择 剩余的种子节点;计算K个种子社团中各节点通过MDS映射后的中屯、坐标，作为K均值的初始 种子节点的坐标(x/，X2/，. . .，χ^κ)，所述相互距离最远原则具体包括:设当前已查到Θ/ (Θ/ Ε[Θ+1，Κ])个种子节点的坐标为yi，y2, . . .，ye'，网络中除种子节点之外的节点的坐标为01， 02, ...，ΟΝ-θ'，则采用相互距离最远原则选择的剩余种子节点0的坐标为网络中除了 yi, 72, ...，ye'之外的节点坐标中，符合下式
的节点，c/ E {〇1,〇2,...， ΟΝ-Θ' }，计算K个种子社团中各节点通过MDS映射后的中屯、坐标，作为K均值的初始种子节点 的坐标{x/，X2/，. ..，χ^κ};所述的各初始种子社团中屯、坐标的计算方式为:对于已查找到 的种子社团Gi，i = l，2, . . .，Κ，设其包含g个节点，各节点坐标为yi，y2, . . .，yg，则种子社团 中屯、坐标天
[0156] 优选地，本发明实施例所述获取单元具体用于，步骤（1)，将(X/，X2/，...，χ/κ)作 为初始聚类中屯、，将κ个集合Zi设置为空集，其中i = l，2，...，Κ，设置为空集;步骤(2)，循环 (3巧IK4)直到每个聚类不再发生变化为止;步骤(3)，在第t次迭代中，对网络中的任一节点 坐标X"按如下的方法把它调整到K个类别中的某一类别中去，对于某一类别i，其中i = l， 2，...，K，若所有的j辛i，其中，j = l，2，...，K，如果Mx"-χi'M<Mx"-χ'j||，则x"EZi，其 中，t为从1开始的自然数，||a-b II为坐标a与b之间的欧氏距离，设a和b均为P维向量;步骤 (4)，由第(3)步计算第i类的新中屯、坐标的第j个分量
式中，IZil为Zi类中 元素的数目。则第i类的中屯、坐标为：^/11，义/12，...，义/11()。根据新得到的中屯、坐标计算^ 的值为：
，若|1'-引<8，则退出程序，输出聚类结果21。= 1， 2，...，1〇，反之，令1 = ^，转步骤(3)。
[0157] 优选地，本发明实施例所述的处理单元具体用于，对复杂网络图GG进行社团划分 C，记C=ki，C2, . . .，Cp}，其中，P为从1开始到N之间的任意自然数，Cia = l，2,. . .，p)为复 杂网络图G中若干节点组成的集合，计算当前社团划分下的模块度
勺网络节点Vi与网络中其他节点的连 边数目，其中，i = l，2, . . .，N，M为网络连边的数目，Cm和Cn分别为节点VI和Vj所属的社团的 编号，其中，me[l,p]，ne[l,p]
[0158] 需要说明的是，本发明实施例的相关部分可W参照方法实施例的相关部分进行理 解，在此不再进行寶述。
[0159] 综上，本发明通过合理选择聚类中屯、作为K均值聚类算法中的初始种子节点，最后 利用K均值算法在低维欧氏空间中聚类网络节点，并聚类隶属于同一社团的网络节点，从而 提高了挖掘社团精度，进而提高了后续对系统分析的准确性。
[0160] W上所述，仅为本发明较佳的【具体实施方式】，但本发明的保护范围并不局限于此， 任何熟悉本技术领域的技术人员在本发明掲露的技术范围内，可轻易想到的变化或替换， 都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该W权利要求书的保护范 围为准。
【主权项】
1. 一种K均值社团结构挖掘方法，该方法包括： 基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种子社团的中心 节点作为初始种子节点，所述中心节点坐标作为K均值聚类种子节点的坐标值，其中，Ke [2,N-1]； 将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当前K值下的社团结 构划分； 获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结果的模块度值，选 取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最佳划分结果中属于 同一类的初始种子节点作为一个社团结构，得到最终划分结果。2. 根据权利要求1所述的方法，其特征在于，还包括： 根据复杂网络G的邻接矩阵A计算各网络节点对之间的相同直接邻居节点的数目并组 成相似度矩阵S，根据相似度矩阵计算网络中各网络节点间的距离矩阵D; 其中，所述邻接矩阵A为具有N个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点Vi 和节点Vj之间有边相连时，aij = l;当节点i和j之间无直接连边时，aij = 0,其中，aij为邻接 矩阵A中的各元素，具体表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时， aij = 0;所述的相似度矩阵S为具有N个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点 Vi和节点Vj之间有边相连时，Sij = (Ai.，Aj.);当节点i和j之间无直接连边时，Sij = O，其中 Sij为S中的各元素，i = l，2, . . .，N，j = l，2, . . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i行 元素组成的向量，所述的距离矩阵D为具有N个节点V1的复杂网络图G， 构造一个^_勺矩阵，屯=(8#8」」-28。）1/2，其中，81」为3中的各元素，1 = 1，2，···』，]·= 1，2，...，N; 利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维标度 法MDS具体包括:利用D = UAUt对矩阵D进行分解，其中，Λ =CliagIA1J2, ...，λΝ}为一个对 角矩阵，且每个元素\表示矩阵D的特征值，不失一般性的，令A1 2 λ2 2 ... 2 λΝ，即将特征值 按降序排列，矩阵U中的第i列为特征值M对应的特征向量，若在λ2> ... >λΝ中，存在ρ 个特征值大于零，ρΕ [1，Ν]，则选择P个特征值对应的特征向量记为U1，U2, . . .，Up，并将其组 成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在 P维空间中的坐标，即（Χ1，Χ 2,...， XN); 所述基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种子社团的 中心节点作为初始种子节点具体包括： 基于局部扩展的种子筛选法选择K个初始种子社团，并根据网络节点的欧氏坐标计算 各个初始种子社团的中心坐标作为各个初始种子社团的初始种子节点。3. 根据权利要求2所述的方法，其特征在于，所述基于局部扩展的种子筛选法选择K个 初始种子社团，并根据网络节点的欧氏坐标计算各个初始种子社团的中心坐标作为各个初 始种子社团的初始种子节点具体包括： 将复杂网络G中的每个节点均设置一个标志位3i(i = l，2, . . .，N)，0表示该节点未被标 识，1表示该节点已被标识； 查找该网络中的所有完全子图，根据计算查找到的每个完全子图中权 值的平均值，并按照从大到小的顺序排序，用G1^G2) ... 2Gm表示； 在当前节点标志位为〇的节点中选择度数最大的节点，设该节点为a，在Gi，G2, ... ,Gm中 选择包含节点a的完全子图组成子集!6心(7,:，·…?丨，r为从1到M之间的任意自然数，并在该 子集中选取符合条件（1)和条件(2)的完全子图G1，将其中心节点坐标作为一个初始的种子 节点： 条件（I):G1中的所有节点的标志位均为O; 条件(2) :Gi 之 Gj，对于任意 G，e {6^i-; 初始化节点子集Ω = 0，以选择的初始种子社团GHt为核心，根据扩展G1的范围，其中，α和β为取值范围在O至1之间的实数，对于仏的直接邻居节点V，设将V加 入子图G 1后的子图用Gdv表示，根据公式得到的子图连边紧密度为 iV,，若&^& ,则将节点ν加入子图匕，否则，不将节点￥加入子图仏中，将凡是能够使得 子图G1的连边密度巧增大的邻居节点均放入节点子集Ω中，直到公式不再增大为止，并将集合Ω中的各节点的标志位均设置为1; 若K个种子社团均已初始化完毕，或者G1,G2, ...，Gm中不再存在未被标示的完全子图， 且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余的种子节 占. 所述相互距离最远原则具体包括：设当前已查到θ'(θ' ε[θ+ι，κ])个种子节点的坐标 为yi，y2,. . .，y^，网络中除种子节点之外的节点的坐标为〇1，〇2,. . .，on-θ'，则采用相互距离 最远原则选择的剩余种子节点〇的坐标为网络中除了yi，y2,... ,ye，之外的节点坐标中，符 合下式的节点，c/ G {〇1，〇2, .. .，0Ν-Θ，}，计算K个种子社团中各节 点通过MDS映射后的中心坐标，作为K均值的初始种子节点的坐标W ι,χ'2,...，X、}; 所述的各初始种子社团中心坐标的计算方式为：对于已查找到的种子社团G^i = I, 2，. . .，K，设其包含g个节点，各节点坐标为yi，y2，. . .，yg，则种子社团中心坐标为4.根据权利要求3所述的方法，其特征在于，将所述初始种子节点的坐标作为输入参数 进行K均值聚类，获取在当前K值下的社团结构划分具体包括： 步骤(1)，将(X71，X7 2，. . .，X7 κ)作为初始聚类中心，将K个集合Zi设置为空集，其中i = 1， 2,. . . , K ； 步骤(2 )，循环(3)到(4)直到每个聚类不再发生变化为止； 步骤(3)，在第t次迭代中，对网络中的任一节点坐标X〃按如下的方法把它调整到K个类 别中的某一类别中去，对于某一类别i，其中i = l，2，. . .，K，若所有的j矣i，其中，j = l， 2，...，κ，如果I IxIxZ1I |〈| |x〃-x、| |，则x〃eZl，其中，t为从1开始的自然数，I Ia-b| I为坐 标a与b之间的欧氏距离，设a和b均为P维向量； 步骤(4)，由第(3)步计算第i类的新中心坐标的第j个分量式中，I Z1IS 中元素的数目，则第i类的中心坐标为u，Y12,... ,X、），根据新得到的中心坐标 计算J '的值为：若I y -J I 0，则退出程序，输出聚类结果& (i = 1， 2，...，1〇，反之，令1 = ^，转步骤(3)。5. 根据权利要求1-4任意一项所述的方法，其特征在于，所述获取在不同K值下的社团 结构划分，计算不同参数值K下社团划分结果的模块度值，选取能使模块度值最大的初始 种子节点聚类结果作为最佳划分结果，将最佳划分结果中属于同一类的初始种子节点作为 一个社团结构，得到最终划分结果具体包括： 对复杂网络图G进行社团划分C，记C= {C1，C2, . . .，cP}，其中，p为从1开始到N之间的任 意自然数，ci(i = l，2,...，p)为复杂网络图G中若干节点组成的集合，计算当前社团划分下 的模块度式中，为网络节点V1与网络中其他 节点的连边数目，其中，i = l，2, ...，N，M为网络连边的数目，cdPcn分别为节点Vi和Vj所属 的社团的编号，其中，me[l，p]，ne[l，p]，6. -种K均值社团结构挖掘装置，其特征在于，包括： 计算单元，用于基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种 子社团的中心节点作为初始种子节点，所述中心节点坐标作为K均值聚类种子节点的坐标 值，其中，Ke[2，N-l]; 获取单元，用于将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当前 K值下的社团结构划分； 处理单元，用于获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结果 的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最佳 划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。7. 根据权利要求6所述的装置，其特征在于，该装置还包括:映射单元； 所述映射单元，用于根据复杂网络G的邻接矩阵A计算各网络节点对之间的相同直接 邻居节点的数目并组成相似度矩阵S，根据相似度矩阵计算网络中各网络节点间的距离矩 阵D;其中，所述邻接矩阵A为具有N个节点 Vi的复杂网络图G，构造一个NXN的矩阵，当节点Vi 和节点Vj之间有边相连时，aij = l;当节点i和j之间无直接连边时，aij = 0,其中，aij为邻接 矩阵A中的各元素，具体表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时， aij = 0;所述的相似度矩阵S为具有N个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点 Vi和节点Vj之间有边相连时，Sij = (Ai.，Aj.);当节点i和j之间无直接连边时，Sij = O，其中 Sij为S中的各元素，i = l，2,. . .，N，j = l，2,. . . ,N当i = j时，sij = 0;Ai.表示矩阵A的第i行元 素组成的向量，所述的距离矩阵D为具有N个节点V1的复杂网络图G，构造 一个~父_勺矩阵，(^ = (8^+8」」-28。）1/2，其中，8。为3中的各元素，1 = 1，2，...具」=1， 2, ...，N;利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维 标度法MDS具体包括:利用D = UAU^矩阵D进行分解，其中，Λ = CliagIA1J2, ...，λΝ}为一 个对角矩阵，且每个元素\表示矩阵D的特征值，不失一般性的，令A1 2 λ2 2 ... 2 λΝ，即将特 征值按降序排列，矩阵U中的第i列为特征值\对应的特征向量，若在A1 2 λ2 2 ... 2 λΝ中，存 在P个特征值大于零，Pe [I，Ν]，则选择ρ个特征值对应的特征向量记为ui，U2, . . .，uP，并将 其组成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在p维空间中的坐标，即（X 1， X2, . . . ,Xn)； 所述计算单元具体用于，基于局部扩展的种子筛选法选择K个初始种子社团，并根据网 络节点的欧氏坐标计算各个初始种子社团的中心坐标作为各个初始种子社团的初始种子 节点。8.根据权利要求7所述的装置，其特征在于， 所述计算单元具体用于，将复杂网络G中的每个节点均设置一个标志位S1G = IJ, ...， N)，0表示该节点未被标识，1表示该节点已被标识；查找该网络中的所有完全子图，根据.计算查找到的每个完全子图中权值的平均值，并按照从大到小的顺序排序， 用Gi2G2> ... 2Gm表示;在当前节点标志位为O的节点中选择度数最大的节点，设该节点为 a，在G^G2, . . .，Gm中选择包含节点a的完全子图组成子集丨?.··Α丨_，r为从1到M之间的 任意自然数，并在该子集中选取符合条件（1)和条件(2)的完全子图G1，将其中心节点坐标 作为一个初始的种子节点:条件（I):Gi中的所有节点的标志位均为O;条件(2):Gi 2 Gj，对于 任意G/e ;初始化节点子集Ω = 0，以选择的初始种子社团Gi作为核心，根据-扩展Gi的范围，其中，α和β为取值范围在〇至1之间的实数，对于G i的直接 邻居节点V，设将V加入子图61后的子图用GAv表示，根据公式得到的子 图连边紧密度为^，若^^+,2&，则将节点V加入子图61，否则，不将节点V加入子图6 1中， 将凡是能够使得子图G1的连边密度巧增大的邻居节点均放入节点子集Ω中，直到公式不再增大为止，并将集合Ω中的各节点的标志位均设置为1;若K个种子 社团均已初始化完毕，或者G1,G2, ...，Gm中不再存在未被标示的完全子图，且若当前已查找 到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余的种子节点；所述相互距离 最远原则具体包括:设当前已查到θ' (θ' Ε[Θ+1，Κ])个种子节点的坐标为yi，y2, . . .，ye'，网 络中除种子节点之外的节点的坐标为〇1，〇2, ...，〇ν-θ'，则采用相互距离最远原则选择的剩 余种子节点〇的坐标为网络中除了 y I，y 2，. . .，y θ，之外的节点坐标中，符合下式的节点，c/ e {〇1，〇2, . . .，ΟΝ-θ，}，计算K个种子社团中各节点通过 MDS映射后的中心坐标，作为K均值的初始种子节点的坐标2, ...，X、};所述的各初 始种子社团中心坐标的计算方式为:对于已查找到的种子社团G1, i = l，2，...，Κ，设其包含 g个节点，各节点坐标为y I，y 2，. . .，y g，则种子社团中心坐标为9. 根据权利要求8所述的装置，其特征在于， 所述获取单元具体用于，步骤⑴，将UW2,... Υκ)作为初始聚类中心，将K个集合 Z1设置为空集，其中i = l，2，...，K，设置为空集;步骤(2)，循环(3)到(4)直到每个聚类不再 发生变化为止;步骤(3)，在第t次迭代中，对网络中的任一节点坐标χ〃按如下的方法把它调 整到K个类别中的某一类别中去，对于某一类别i，其中i = l，2，...，Κ，若所有的j矣i，其中， j = l，2，"_，K，如果I IxW-X^I |〈| |χ〃-χ? I，则x〃EZi，其中，t为从1 开始的自然数，I |a_b| 为坐标a与b之间的欧氏距离，设a和b均为p维向量;步骤(4)，由第(3)步计算第i类的新中心 坐标的第j个分量式中，I Zi I为Zi类中元素的数目，则第i类的中心坐标为： (X' ilY i2, . . . ,X' iK)，根据新得到的中心坐标计算J'的值为：.若 LT -J I〈S，则退出程序，输出聚类结果Zi(i = 1，2，. . .，K)，反之，令J = y，转步骤(3)。10. 根据权利要求6-9中任意一项所述的装置，其特征在于， 所述处理单元具体用于，对复杂网络图G进行社团划分C，记C= {C1，C2, ...，cP}，其中，p 为从1开始到N之间的任意自然数，Cl(i = l，2,. . .，p)为复杂网络图G中若干节点组成的集 合，计算当前社团划分下的模块度网络节点Vi与网络中其他节点的连边数目，其中，i = l，2,...，N，M为网络连边的数目，~和 Cn分别为节点Vi和Vj所属的社团的编号，其中，me[l，p]，ne[l，p]，
【专利摘要】本发明公开了一种K均值社团结构挖掘方法及装置，本发明通过合理选择聚类中心作为K均值聚类算法中的初始种子节点，最后利用K均值算法在低维欧氏空间中聚类网络节点，聚类隶属于同一社团的网络节点，从而提高了挖掘社团精度，进而提高了后续对系统分析的准确性。
【IPC分类】G06F17/50, G06Q10/10
【公开号】CN105488247
【申请号】CN201510784716
【发明人】范科峰, 李琳, 姚相振, 周睿康, 樊晓贺, 叶润国
【申请人】中国电子技术标准化研究院
【公开日】2016年4月13日
【申请日】2015年11月16日
【技术领域】
[0001] 本发明设及网络技术领域，尤其设及一种Κ均值社团结构挖掘方法及装置。
【背景技术】
[0002] 现实世界中的许多复杂系统都可W被抽象为由节点和节点间连边组成的复杂网 络。例如，Internet网络中的网页可W看做复杂网络中的节点，页面间的超链接可W被看作 节点间的连边，从而将整个Internet抽象为复杂网络;在线社交网络中，各虚拟用户可W被 抽象为网络节点，虚拟用户之间的关注、互加好友等操作可W被视为网络之间的连边，在此 基础上，整个在线社交网络可W用复杂网络表示；国家公共交通网络中，将各城市之间的站 点作为网络节点，城市之间的交通路线作为连边，可W得到一个国家公共交通网络的抽象 网络图；生物蛋白质网络将不同生物蛋白作为网络节点并用连边掲示不同蛋白之间的相互 影响。因此，作为研究复杂系统的有效工具，复杂网络的各种性质已经引起了各界学者的广 泛关注。
[0003] 诸多科学家研究表明，复杂网络具有诸多拓扑结构性质。其中，社团结构便是复杂 网络的一个重要的拓扑特性。在复杂网络中，社团结构将复杂网络中的节点分为若干个子 集，使得社团内部的节点之间连边较为紧密而社团之间的连边则较为稀疏。运种高内聚的 网络结构可W很好的掲示复杂系统中的结构特点、功能特性W及组织特征。例如在互联网 中的社团结构反应了讨论共同话题的一些网站，而在线社交网络中的社团结构则表示了 拥有共同兴趣爱好的人组成的一个团体。因此，复杂网络中社团结构的挖掘对于分析网络 的特性和功能具有十分重要的现实意义。近些年，面对越来越多的复杂系统被抽象为复杂 网络，高精度的挖掘复杂网络中的社团结构对于分析复杂系统的物理特性具有重要的意 义。但是目前的挖掘社团精度不高，从而影响了后续对系统分析的准确性。
【发明内容】
[0004] 鉴于上述的分析，本发明旨在提供一种K均值社团结构挖掘方法及装置，用W解决 现有技术中挖掘社团精度不高的问题。
[0005] 本发明主要是通过W下技术方案实现的：
[0006] 本发明一方面提供了一种K均值社团结构挖掘方法，该方法包括：
[0007] 基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种子社团的 中屯、节点作为初始种子节点，所述中屯、节点坐标作为K均值聚类种子节点的坐标值，其中，K E[2，N-1];
[000引将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当前K值下的社 团结构划分；
[0009]获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结果的模块度 值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最佳划分结果 中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。
[0010] 优选地，该方法还包括：
[0011] 根据复杂网络G的邻接矩阵A计算各网络节点对之间的相同直接邻居节点的数目 并组成相似度矩阵S，根据相似度矩阵计算网络中各网络节点间的距离矩阵D;
[0012]其中，所述邻接矩阵A为具有N个节点VI的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点Vj之间有边相连时，aij = 1;当节点巧日j之间无直接连边时，aij = 0，其中，aij为 邻接矩阵A中的各元素，具体表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i = j 时，au = 0;所述的相似度矩阵S为具有N个节点vi的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点vj之间有边相连时，sij = (Ai.，Aj.);当节点i和j之间无直接连边时，sij = 0,其 中sij为S中的各元素 ，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i
行元素组成的向量， 所述的离矩阵D为具有N个节点Vi的复杂网络图G，构 造 1'^NXN的矩阵,dij = (sii+sj广2sij)l/2,其中，sij为S中的各兀素 ，i = l,2,...,N,j = l, 2,...,Ν；
[0013] 利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维 标度法MDS具体包括:利用D = UAIJT对矩阵D进行分解，其中，八= diag{Ai，A2, . . .，λΝ}为一 个对角矩阵，且每个元素 λι表示矩阵D的特征值，不失一般性的，令λι含λ2含...含λΝ，即将特 征值按降序排列，矩阵U中的第i列为特征值λι对应的特征向量，若在λι含λ2含...含λΝ中，存 在Ρ个特征值大于零，ρΕ [1 ,Ν]，则选择Ρ个特征值对应的特征向量记为ui，U2,...，叫，并将 其组成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（XI， X2, . . . ,Χν)；
[0014] 所述基于局部扩展的种子筛选法选择Κ个初始种子社团，并计算各个初始种子社 团的中屯、节点作为初始种子节点具体包括：
[0015] 基于局部扩展的种子筛选法选择Κ个初始种子社团，并根据网络节点的欧氏坐标 计算各个初始种子社团的中屯、坐标作为各个初始种子社团的初始种子节点。
[0016] 优选地，所述基于局部扩展的种子筛选法选择Κ个初始种子社团，并根据网络节点 的欧氏坐标计算各个初始种子社团的中屯、坐标作为各个初始种子社团的初始种子节点具 体包括：
[0017]将复杂网络G中的每个节点均设置一个标志位Si(i = l，2, . . .，Ν)，0表示该节点未 被标识，1表示该节点已被标识；
[0018] 查找该网络中的所有完全子图，根据
计算查找到的每个完全子图中 权值的平均值，并按照从大到小的顺序排序，用Gi>G2> . . . >Gm表示；
[0019] 在当前节点标志位为0的节点中选择度数最大的节点，设该节点为a,在Gi，G2, ...， Gm中选择包含节点a的完全子图组成子集{啤，巧，，…，.巧,}:，r为从巧IjM之间的任意自然数，并 在该子集中选取符合条件（1)和条件(2)的完全子图Gi，将其中屯、节点坐标作为一个初始的 种子节点：
[0020] 条件(1) :Gi中的所有节点的标志位均为0;
[0021 ]条件（2) :Gi > Gj，对于任意(J/ 居.Kj,.|?";;
[0022] 初始化节点子集Ω = 0，W选择的初始种子社团G 1作为核屯、，根据
扩展Gi的范围，其中，α和β为取值范围在0至1之间的实数，对于Gi的直接 邻居节点V，设将V加入子图Gi后的子图用Gi+v表示，根据公式
得到的子 图连边紧密度为巧?+，，若，则将节点V加入子图Gi，否则，不将节点V加入子图Gi中， 将凡是能够使得子图Gi的连边密度增大的邻居节点均放入节点子集Ω中，直到公式
不再增大为止，并将集合Ω中的各节点的标志位均设置为1;
[0023] 若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标示的完全子 图，且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余的种子 节点；
[0024] 所述相互距离最远原则具体包括:设当前已查到0/ (0/ Ε[Θ + 1，Κ])个种子节点的 坐标为yi，y2,...，ye'，网络中除种子节点之外的节点的坐标为〇1，〇2,...，〇Ν-θ'，则采用相互 距离最远原则选择的剩余种子节点0的坐标为网络中除了yi，y2,...，ye'之外的节点坐标 中，符合下式
的节点，〇/ E {〇1，〇2, . . .，ΟΝ-θ< }，计算K个种子社团中 各节点通过MDS映射后的中屯、坐标，作为Κ均值的初始种子节点的坐标{χΛκ^，... yd ;
[0025] 所述的各初始种子社团中屯、坐标的计算方式为:对于已查找到的种子社团Gi，i = 1，2, . . .，Κ，设其包含g个节点，各节点坐标为yi，y2, . . .，yg，则种子社团中屯、坐标为
[0026] 优选地，所述将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当 前K值下的社团结构划分具体包括：
[0027] 步骤（1)，将(x/，X2/，...，χ/κ)作为初始聚类中屯、，将K个集合Zi设置为空集，其中 i = 1,2,. . . ,Κ，设置为至集；
[00%]步骤(2)，循环(3巧ΙΚ4)直到每个聚类不再发生变化为止；
[0029] 步骤(3)，在第t次迭代中，对网络中的任一节点坐标X"按如下的方法把它调整到Κ 个类别中的某一类别中去，对于某一类别1，其中1 = 1，2，...，1(，若所有的_]'辛1，其中〇 = 1，2，...，Κ，如果 l<llx"-x/j| I，则 x"EZi，其中，t 为从1 开始的自然数，I |a-b| 为坐标a与b之间的欧氏距离，设a和b均为P维向量；
[0030] 步骤(4)，由第(3)步计算第i类的新中屯、坐标的第j个分量
式中， Zi|为Zi类中元素的数目。则第i类的中屯、坐标为：^/11，义/12，...，义/11()。根据新得到的中屯、 坐标计算J'的值为：
若|户-引<8，则退出程序，输出聚类结果21 (i = l，2,. . .，Κ)，反之，令J = J'，转步骤(3)。
[0031] 优选地，所述获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结 果的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最 佳划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果具体包 括：
[0032] 对复杂网络图G进行社团划分C，记C=ki，C2, . . .，cp}，其中，P为从1开始到N之间 的任意自然数，Cia = l，2，...，p)为复杂网络图G中若干节点组成的集合，计算当前社团划 分下的模块度
为网络节点Vi与网络中 其他节点的连边数目，其中，i = l，2, . . .，N，M为网络连边的数目，Cm和Cn分别为节点VI和Vj 所属的社团的编号，其中，me[l，p]，ne[l，p]，
[0033] 本发明另一方面还提供了一种K均值社团结构挖掘装置，该装置包括：
[0034] 计算单元，用于基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初 始种子社团的中屯、节点作为初始种子节点，所述中屯、节点坐标作为K均值聚类种子节点的 坐标值，其中，Ke[2，N-l];
[0035] 获取单元，用于将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在 当前K值下的社团结构划分；
[0036] 处理单元，用于获取在不同K值下的社团结构划分，计算不同参数值K下社团划分 结果的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将 最佳划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。
[0037] 优选地，该装置还包括:映射单元；
[0038] 所述映射单元，用于根据复杂网络G的邻接矩阵A计算各网络节点对之间的相同直 接邻居节点的数目并组成相似度矩阵S，根据相似度矩阵计算网络中各网络节点间的距离 矩阵D;其中，所述邻接矩阵A为具有N个节点VI的复杂网络图G，构造一个NXN的矩阵，当节 点Vi和节点vj之间有边相连时，au = l;当节点巧Pj之间无直接连边时，au = 0,其中，aij为邻 接矩阵A中的各元素，具体表示节点间的连边关系，i = l，2, ...，N，j = l，2，...，N;当i = j 时，au = 0;所述的相似度矩阵S为具有N个节点VI的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点Vi之间有边相连时，sij = (Ai.，Aj.);当节点i和j之间无直接连边时，sij = 0,其 中sij为S中的各元素 ，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i 行元素组成的向量：
所述的离矩阵D为具有N个节点VI的复杂网络图G，构 造 1'^NXN的矩阵,dij = (sii+sj广2sij)l/2,其中，sij为S中的各兀素 ，i = l,2,...,N,j = l, 2, ...，N;利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维 标度法MDS具体包括:利用D = UAIJT对矩阵D进行分解，其中，八= dia g{Ai，A2, . . .，λΝ}为一 个对角矩阵，且每个元素 λι表示矩阵D的特征值，不失一般性的，令λι含λ2含...含λΝ，即将 特征值按降序排列，矩阵帅的第i列为特征值λι对应的特征向量，若在λι > λ2 > ...含λΝ中， 存在p个特征值大于零，pE[l,N]，则选择p个特征值对应的特征向量记为m，U2,...，叫，并 将其组成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（XI， X2, . . . ,Χν)；
[0039] 所述计算单元具体用于，基于局部扩展的种子筛选法选择Κ个初始种子社团，并根 据网络节点的欧氏坐标计算各个初始种子社团的中屯、坐标作为各个初始种子社团的初始 种子节点。
[0040] 优选地，所述计算单元具体用于，将复杂网络G中的每个节点均设置一个标志位δι (i = l，2,...，Ν)，0表示该节点未被标识，1表示该节点已被标识;查找该网络中的所有完全 子图，根据
计算查找到的每个完全子图中权值的平均值，并按照从大到小的 顺序排序，用Gi含G2含...含Gm表示;在当前节点标志位为0的节点中选择度数最大的节点， 设该节点为曰，在Gi，G2, . . .，Gm中选择包含节点a的完全子图组成子集{吗，巧。，…，砖}，r为从1 到M之间的任意自然数，并在该子集中选取符合条件（1)和条件(2)的完全子图Gi，将其中屯、 节点坐标作为一个初始的种子节点:条件（l):Gi中的所有节点的标志位均为0;条件(2) :Gi >&，对于任意6,.€巧而:..…h初始化节点子集0 = 0，W选择的初始种子社团Gi作为 核屯、，根据
展Gi的范围，其中，α和β为取值范围在0至1之间的实数，对 于Gi的直接邻居节点V，设将V加入子图Gi后的子图用Gi + v表示，根据公式
得到的子图连边紧密度为馬W，若馬+K ^巧;则将节点V加入子图Gi，否 则，不将节点V加入子图Gi中，将凡是能够使得子图Gi的连边密度馬增大的邻居节点均放 入节点子集Ω中，直到公式
不再增大为止，并将集合Ω中的各节点的标 志位均设置为1;若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标示的 完全子图，且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余 的种子节点;所述相互距离最远原则具体包括:设当前已查到Θ/ (0/ Ε[Θ+1，Κ])个种子节点 的坐标为yi，y2,...，ye'，网络中除种子节点之外的节点的坐标为01,02,...，〇Ν-θ'，则采用相 互距离最远原则选择的剩余种子节点0的坐标为网络中除了yi，y2,...，ye'之外的节点坐标 中，符合下iS：
的节点，c/ E {〇1,〇2, . . . ,ΟΝ-θ< }，计算K个种子社团中 各节点通过MDS映射后的中屯、坐标，作为Κ均值的初始种子节点的坐标{χ/，Χ2/，. . .，χ^κ}; 所述的各初始种子社团中屯、坐标的计算方式为:对于已查找到的种子社团Gi，i = l，2,...， K，设其包含g个节点，各节点坐标为y 1，y 2，. . .，y g，则种子社团中屯、坐标为
[0041] 优选地，所述获取单元具体用于，步骤（1)，将(X/，X2/，. . .，χ^κ)作为初始聚类中 屯、，将κ个集合Zi设置为空集，其中1 = 1，2，...，1(，设置为空集;步骤(2)，循环(3巧1](4)直到 每个聚类不再发生变化为止;步骤(3)，在第t次迭代中，对网络中的任一节点坐标X"按如下 的方法把它调整到K个类别中的某一类别中去，对于某一类别i，其中i = l，2，...，Κ，若所有 的占'辛1，其中〇 = 1，2，...，1(，如果|^"-义1/||<|^"-义/^||，则义"￡21，其中，*为从1开始的 自然数，||a-b II为坐标a与b之间的欧氏距离，设a和b均为Ρ维向量;步骤(4)，由第(3)步计 算第i类的新中屯、坐标的第j个分量
式中，I Zi I为Zi类中元素的数目。则第i 类的中屯、坐标为：（χ/ι?，χ/ι2, . . .，χ^ικ)。根据新得到的中屯、坐标计算的值为：
，若lJ'-Jl<S，则退出程序，输出聚类结果Zl(i = l，2，...，K)，反 之，令J = r，转步骤(3)。
[0042] 优选地，所述处理单元具体用于，对复杂网络图G进行社团划分C，记C={ci， C2, . . .，cp}，其中，P为从1开始至阳之间的任意自然数，ci(i = l，2, . . .，p)为复杂网络图G中 若干节点组成的集合，计算当前社团划分下的模块度
，式 中
，，为网络节点Vi与网络中其他节点的连边数目，其中，i = l，2，. . .，N，M为网 络连边的数目，Cm和Cn分别为节点VI和Vj所属的社团的编号，其中，me[l，p]，ne[l，p]，
[0043] 本发明通过合理选择聚类中屯、作为K均值聚类算法中的初始种子节点，最后利用K 均值算法在低维欧氏空间中聚类网络节点，并聚类隶属于同一社团的网络节点，从而提高 了挖掘社团精度，进而提高了后续对系统分析的准确性。
[0044] 本发明的其他特征和优点将在随后的说明书中阐述，并且部分的从说明书中变得 显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在所写的说明书、 权利要求书、W及附图中所特别指出的结构来实现和获得。
【附图说明】
[0045] 图1为本发明实施例的一种K均值社团结构挖掘方法的流程示意图；
[0046] 图2为本发明实施例的另一种K均值社团结构挖掘方法的流程示意图；
[0047] 图3为本发明实施例在空手道俱乐部网络下得到的具有重叠的社区结构示意图； [004引图4为本发明实施例的一种K均值社团结构挖掘装置的结构示意图。
【具体实施方式】
[0049] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完 整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于 本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他 实施例，都属于本发明保护的范围。
[0050] 本发明利用皮尔逊相关系数公式衡量复杂网络各节点之间的相似度，通过多维标 度法将网络节点映射为低维欧氏空间中的节点坐标，在此基础上，根据复杂网络中社团结 构的拓扑特征提出了一种基于局部扩散的K均值改进算法，该算法合理选择聚类中屯、并且 根据社团拓扑结构特点聚类隶属于同一社团的网络节点。与现有技术相比，本发明克服了 传统基于K均值社团挖掘方法中种子节点随机选择从而导致精度较差的局限性，提高了社 团挖掘方法的精确度，很好的解决了复杂网络中社团结构的挖掘问题。为了更好的理解本 发明，下面仅W几个具体的例子对本发明进行详细的说明。
[0051 ]系统实施例
[0052] 本发明实施例提供了一种K均值社团结构挖掘方法，参见图1，该方法包括：
[0053] S101、基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种子社 团的中屯、节点作为初始种子节点，所述中屯、节点坐标作为K均值聚类种子节点的坐标值，其 中，Ke[2，N-l];
[0054] S102、将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当前K值 下的社团结构划分；
[0055] S103、获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结果的模 块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最佳划分 结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。
[0056] 本发明通过合理选择聚类中屯、作为K均值聚类算法中的初始种子节点，最后利用K 均值算法在低维欧氏空间中聚类网络节点，并聚类隶属于同一社团的网络节点，从而提高 了挖掘社团精度，进而提高了后续对系统分析的准确性。
[0057] 本发明实施例所述的方法还包括:根据复杂网络G的邻接矩阵A计算各网络节点对 之间的相同直接邻居节点的数目并组成相似度矩阵S，根据相似度矩阵计算网络中各网络 节点间的距离矩阵D;
[0058] 利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标；
[0059] 其中，所述邻接矩阵A为具有N个节点VI的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点Vj之间有边相连时，aij = 1;当节点巧日j之间无直接连边时，aij = 0，其中，aij为 邻接矩阵A中的各元素，具体表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i = j 时，au = 0;所述的相似度矩阵S为具有N个节点vi的复杂网络图G，构造一个NXN的矩阵，当 节点Vi和节点vj之间有边相连时，sij = (Ai.，Aj.);当节点i和j之间无直接连边时，sij = 0,其 中sij为S中的各元素 ，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i 行元素组成的向量，
所述的离矩阵D为具有N个节点VI的复杂网络图G，构 造一个NXN的矩阵，dij = (sii+sjj-2sij)l/2，其中，sij为S中的各元素 ，i = l，2，...，N，j = l， 2,...,Ν；
[0060] 利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维 标度法MDS具体包括:利用D = UAIJT对矩阵D进行分解，其中，八=diag{Ai，A2, . . .，λΝ}为一 个对角矩阵，且每个元素 λι表示矩阵D的特征值，不失一般性的，令λι含λ2含...含λΝ，即将特 征值按降序排列，矩阵U中的第i列为特征值、对应的特征向量，若在λι含λ2含...含λΝ中，存 在Ρ个特征值大于零，ρΕ[1，Ν]，则选择Ρ个特征值对应的特征向量记为m，U2,...，叫，并将 其组成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（XI， X2, . . . ,Χν)；
[0061] 本发明实施例所述基于局部扩展的种子筛选法选择Κ个初始种子社团，并计算各 个初始种子社团的中屯、节点作为初始种子节点具体包括：
[0062] 基于局部扩展的种子筛选法选择Κ个初始种子社团，并根据网络节点的欧氏坐标 计算各个初始种子社团的中屯、坐标作为各个初始种子社团的初始种子节点。
[0063] 具体实施时，本发明通过将复杂网络G中的每个节点均设置一个标志位Si(i = l， 2,...，N)，0表示该节点未被标识，1表示该节点已被标识；
[0064] 查找该网络中的所有完全子图，根巧
计算查找到的每个完全子图中 权值的平均值，并按照从大到小的顺序排序，用Gi>G2> . . . >Gm表示；
[0065] 在当前节点标志位为0的节点中选择度数最大的节点，设该节点为a,在Gi，G2, ...， Gm中选择包含节点a的完全子图组成子集!G,,，的，…，(：y，r为从巧IjM之间的任意自然数，并 在该子集中选取符合条件（1)和条件(2)的完全子图Gi，将其中屯、节点坐标作为一个初始的 种子节点：
[0066] 条件(1) :Gi中的所有节点的标志位均为0;
[0067] 条件U):Gi 含 Gj，对于任意巧 €仍,，(;,:，...，6',. h
[006引初始化节点子集Ω = 0，W选择的初始种子社团G 1作为核屯、，根据
扩展Gi的范围，其中，α和β为取值范围在0至1之间的实数，对于Gi的直接 邻居节点V，设将V加入子图Gi后的子图用Gi+v表示，根据公式
得到的子 图连边紧密度为巧，若馬^巧^.，则将节点V加入子图Gi，否则，不将节点V加入子图Gi中， 将凡是能够使得子图Gi的连边密度巧^增大的邻居节点均放入节点子集Ω中，直到公式
不再增大为止，并将集合Ω中的各节点的标志位均设置为1;
[0069] 若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标示的完全子 图，且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余的种子 节点；
[0070] 计算K个种子社团中各节点通过MDS映射后的中屯、坐标，作为K均值的初始种子节 点的坐标(XI'，X2'，. . .，Χ'Κ)。
[0071] 所述相互距离最远原则具体包括:设当前已查到0/(9/ e[9+l ，K])个种子节点的 坐标为yi，y2,...，ye'，网络中除种子节点之外的节点的坐标为〇1，〇2,...，〇Ν-θ'，则采用相互 距离最远原则选择的剩余种子节点0的坐标为网络中除了yi，y2,...，ye'之外的节点坐标 中，符合下王
的节点，c/ E {〇1,〇2, . . . ,ΟΝ-θ< }，计算K个种子社团中 各节点通过MDS映射后的中屯、坐标，作为Κ均值的初始种子节点的坐标{χΛκ^，... yd ;
[0072] 所述的各初始种子社团中屯、坐标的计算方式为:对于已查找到的种子社团Gi，i = 1，2，. . .，Κ，设其包含g个节点，各节点坐标为yi，y2，. . .，yg，则种子社团中屯、坐标为
[0073] 具体来说，本发明实施例所述将所述初始种子节点的坐标作为输入参数进行K均 值聚类，获取在当前K值下的社团结构划分具体包括：
[0074] 步骤（1)，将(χΛχ2^，...，χ/κ)作为初始聚类中屯、，将K个集合Zi设置为空集，其中 i = l，2，...，K，设置为空集；
[0075] 步骤(2)，循环(3巧lj(4)直到每个聚类不再发生变化为止；
[0076] 步骤(3)，在第t次迭代中，对网络中的任一节点坐标X"按如下的方法把它调整到K 个类别中的某一类别中去，对于某一类别i，其中1 = 1，2，...，1(，若所有的_]'辛1，其中〇 = 1， 2, . . .，Κ，如果 I I I I < I I j I I，则X" eZi，其中，t为从1 开始的自然数，I I a-b I I 为 坐标a与b之间的欧氏距离，设a和b均为P维向量；
[0077] 步骤(4)，由第(3)步计算第i类的新中屯、坐标的第j个分量
式中， Zi|为Zi类中元素的数目。则第i类的中屯、坐标为：^/11，义/12，...，义/11()。根据新得到的中屯、 坐标计算J'的值为：
若|户-引<8，则退出程序，输出聚类结果21 (i = l，2,. . .，Κ)，反之，令J = J'，转步骤(3)。
[0078] 具体实施时，本发明实施例所述获取在不同K值下的社团结构划分，计算不同参数 值K下社团划分结果的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最 佳划分结果，将最佳划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终 划分结果具体包括：
[0079] 对复杂网络图G进行社团划分C，记C=レl，C2，...，Cp}，其中，p为从l开始到N之间 的任意自然数，Cia = l，2，...，p)为复杂网络图G中若干节点组成的集合，计算当前社团划 分下的模块度
为网络节点VI与网络 中其他节点的连边数目，其中，i = l，2, ...，N，M为网络连边的数目，Cm和Cn分别为节点VI和 Vj所属的社团的编号，其中，me[l，p]，ne[l，p]，
[0080] 图2为本发明实施例的另一种K均值社团结构挖掘方法的流程示意图，下面将结合 图2对本发明所述的方法进行详细的说明：
[0081] 输入:一个具有N个节点的复杂网络图G的邻接矩阵A。
[0082] 输出：复杂网络G的一个合理的社团结构划分C= ，C2，. .，cm}。
[0083] 步骤1、根据复杂网络的邻接矩阵计算各节点对之间的相同直接邻居节点的数目 并组成相似度矩阵S，根据相似度矩阵计算网络中各节点间的距离矩阵D;
[0084] 所述步骤1，具体如下：
[0085] 1.1获取复杂网络的邻接矩阵A，记A= (aij)NXN;
[0086] 所述的复杂网络图G=(V，E)为具有N个节点vi(i = l，2，. . .，N)，M条连边ek化=1， 2, . . .，M)的网络拓扑图，其中，V=(V1，V2, . . .，VN)表示网络节点的集合，E=(ei，e2, . . .，eM) 表示网络连边的集合，边ek按照其所连接的两个节点vi、vj，记为eij;
[0087] 所述的邻接矩阵A是指对于该具有N个节点VI的复杂网络图G，构造一个NXN的矩 阵，当节点Vi和节点Vj之间有边相连时，aij = 1;当节点i和j之间无直接连边时，aij = 0，其 中，ai功邻接矩阵A中的各元素，表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i =j时，aij = 〇;
[0088] 所述的相似度矩阵S是指对于该具有N个节点vi的复杂网络图G，构造一个NXN的 矩阵，当节点Vi和节点Vj之间有边相连时，Sij= (Ai.，Aj.);当节点巧日j之间无直接连边时， sij = 0,其中3^为5中的各元素 ，i = l，2, . . .，N，j = l，2, . . .，N;当 1 = j时，sij = 0;Ai.表示 矩阵A的第i行元素组成的向量，
[0089] 所述的距离矩阵D是指对于该具有N个节点Vi的复杂网络图G，构造一个NX N的矩 阵，dij = (sii+sjj-2sij)i/2。其中sij为S中的各兀素 ，i = l,2,. . . ,N，j = l,2,. . . ,Ν。
[0090] 步骤2、利用多维标度法(MDS)将各网络节点映射为低维欧氏空间中的节点坐标；
[0091] 所述步骤2,具体如下：
[0092] 2.1利用公式(1)对矩阵D进行分解，公式(1)如下：
[0093] D = U 八 IJT (1)
[0094] 其中，Λ =diag{Ai，A2, . . .，λΝ}为一个对角矩阵，且每个元素、表示矩阵D的特征 值，不失一般性的，令λ? ^ λ2 ^ ^ λΝ，即将特征值按降序排列。矩阵U中的第i列为特征值 Ai对应的特征向量。
[0095] 2.2若在λι > λ2 > . . . > λΝ中，存在P个特征值大于零，pe [1 ,Ν]，则选择P个特征值 对应的特征向量记为m，U2,...，up，并将其组成矩阵Ρ的列。
[0096] 2.3取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（xi，X2, ...， XN)。
[0097] 步骤3、根据基于局部扩展的种子筛选子方法选择K个初始种子社团，并根据网络 节点的欧氏坐标计算该种子社团的中屯、坐标作为K个初始种子节点；
[0098] 所述步骤3,具体如下：
[0099] 所述基于局部扩展的种子筛选子方法，其特点如下：
[0100] 该方法包括W下步骤：
[0101] 输入:一个具有N个节点的复杂网络图G的邻接矩阵AW及种子节点数目K。
[0102] 输出:K个种子节点的坐标。
[0103] 步骤①:为复杂网络G中的每个节点设置一个标志位Si(i = l，2, . . .，N)，该标志位 为取值为0或者1的数字，0表示该节点未被标识，1表示该节点已被标识。
[0104] 步骤②:查找该网络中的所有完全子图，根据公式(4-8)计算查找到的每个完全子 图中权值的平均值，并按照从大到小的顺序排序，用Gi>G2> ...含Gm表示。
[0105]
[0106] 所述的完全子图为具有如下特点的子图，子图G/=(y/，E/)具有沪个节点Vi(i = 1，2，. . .，N')，则其边数Μ' =N' (Ν' -1 )/2。
[0107] 步骤③:在当前节点标志位为0的节点中选择度数最大的节点，设该节点为a。在 Gi，G2, . . .，Gm中选择包含节点a的完全子图组成子集巧,，G,:，…，G, ^ >并在该子集中选取符合 如下条件的完全子图Gi，将其中屯、坐标作为一个初始的种子节点：
[0108] (1 )Gi中的所有节点的标志位均为0;
[0109] (^Gi > Gj，对于任意巧€巧，馬，…，巧,}。
[0110] 步骤④:初始化节点子集Ω = 0 dW步骤③中选择的初始种子社团Gi作为核屯、，根 据公式(4-9)扩展Gi的范围。
[0111]
[0112] 其中，α和β为取值范围在0至1之间的实数。对于Gi的直接邻居节点V，设将V加入子 图Gi后根据公式(4-9)得到的子图连边紧密度为巧若&,+，' ，则将节点V加入子图 Gi;若&刊<馬，贝怀将节点V加入子图Gi中。将凡是能够使得子图Gi的连边密度&增大的 邻居节点均放入节点子集Ω中，直到公式(4-9)不再增大为止。
[0113] 步骤⑤:将集合Ω中的各节点的标志位均设置为1，表示该节点可能与已有种子节 点属于同一社团，从而在后续种子查找过程中不再考虑该节点。
[0114] 步骤⑥:若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标示 的完全子图，则转步骤⑦，否则，转步骤③。
[0115] 所述K为预先设定的正自然数，其取值范围为[2，N]。
[0116] 步骤⑦:若当前W查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择 剩余的种子节点。
[0117] 步骤⑧:计算K个种子社团中各节点通过MDS映射后的中屯、坐标，作为K均值的初始 种子节点的坐标(X1'，X2'，...，X'K)。
[0118] 步骤4、将步骤3中查找到的K个种子作为输入参数进行K均值聚类，获取在当前K值 下的社团结构划分；
[0119] 所述步骤4,具体如下：
[0120] 所述的K均值算法包含如下步骤：
[0121] 输入:聚类个数K，N个节点的坐标(xi，X2, . . .，XN)和初始的K个种子节点坐标(x/， X2' , . . . ,Χ' K)。
[0122] 输出：满足方差最小标准的Κ个聚类。
[0123] 步骤(1):将(xi'，X2'，. . .，χ'κ)作为初始聚类中屯、；
[0124] 步骤(2):循环(3巧lj(4)直到每个聚类不再发生变化为止；
[0125] 步骤(3):在第t次迭代中，将K个集合21。= 1，2，...，1〇设置为空集。对网络中的 任一节点坐标X"按如下的方法把它调整到K个类别中的某一类别中去。对于某一类别i(i = l，2，...，K)，若所有的j辛i(j = l，2，...，K)，如果Mx"-χi'M<Mx"-χ'jM，则x"eZi。
[01%]所述t为从1开始的自然数。Ma-b||表示坐标a与b之间的欧氏距离，设a和b均为p 维向量。
[0127]步骤(4):由第(3)步计算第i类的新中屯、坐标的第j个分量 [012 引
[0129] 式中，|Zi|为Zi类中元素的数目。则第i类的中屯、坐标为：（Χ'ι1，Χ'ι2，...，Χ'ιΚ)4! 据新得到的中屯、坐标计算r的值为：
[0130]
[013。 若I -J I < δ，则退出程序，输出聚类结果Zi (i = 1，2，. . .，K)，反之，令J = r，转步 骤(3)。
[0132] 步骤5、对于每个KE [2，N-1 ]，均运行步骤3至步骤4，从而获取在不同K值下的社团 结构划分。计算计算不同参数值K下社团划分结果的模块度值，选取能使模块度值最大的节 点聚类结果作为最佳划分结果。将最佳划分结果中属于同一类的节点作为一个社团结构， 得到最终划分结果。
[0133] 所述步骤5,具体如下：
[0134] 所述模块度公式为:对复杂网络图G进行社团划分C，记〔=山1，〇2，...，〇。}，其中， ci(i = l，2, . . .，p)分别为复杂网络图G中若干节点组成的集合，计算当前社团划分C下的模 块度化，公式如下：
[0135]
[0136] 式中：
表示网络节点VI的度，即指该节点VI与网络中其他节点的连边 数目，其中，i 二 1,2,...,Ν;
[0137] Μ表示网络连边的数目；
[013引 Cm和cn分别表示节点Vi和vj所属的社团的编号，其中me [1 ,ρ]，ne [1 ,ρ];
[0139] S(Cm，Cn)函数由式(3)所示：
[0140]
[0141] 本发明将利用皮尔逊相关系数公式衡量复杂网络各节点之间的相似度，通过多维 标度法将网络节点映射为低维欧氏空间中的节点坐标，在此基础上，根据复杂网络中社团 结构的拓扑特征提出了一种基于局部扩散的K均值改进算法，该算法合理 选择聚类中屯、并 且根据社团拓扑结构特点聚类隶属于同一社团的网络节点。与现有技术相比，本发明克服 了传统基于K均值社团挖掘方法中种子节点随机选择从而导致精度较差的局限性，提高了 社团挖掘方法的精确度，很好的解决了复杂网络中社团结构的挖掘问题。
[0142] 图3为本发明实施例在空手道俱乐部网络下得到的具有典型的社区结构示意图， 下面将结合图3对本实施例采用社会网络中的经典数据集Zacha巧空手道俱乐部网络进行 社团结构挖掘进行说明，该网络包含34个节点和78条边，α和肚匀取1。具体包括步骤如下：
[0143] 步骤1，根据复杂网络的邻接矩阵计算各节点对之间的相同直接邻居节点的数目 并组成相似度矩阵S，根据相似度矩阵计算网络中各节点间的距离矩阵D;
[0144] 步骤2,利用多维标度法(MDS)将各网络节点映射为2维欧氏空间中的节点坐标；
[0145] 步骤3,根据基于局部扩展的种子筛选子算法选择K个初始种子社团，并根据网络 节点的欧氏坐标计算该种子社团的中屯、坐标作为K个初始种子节点。例如，当Κ = 2时，经过 种子筛选子算法计算得到的2个种子社团为{1，2，"和{30,33,34}，贝化=2时的种子坐标即 为运两个种子社团的节点对应坐标的中屯、坐标；
[0146] 步骤4,将步骤3中查找到的K个种子作为输入参数进行K均值聚类，获取在当前K值 下的社团结构划分；
[0147] 步骤5,对于每个Ke[2,33]，均运行步骤3至步骤4,从而获取在不同K值下的社团 结构划分。计算计算不同参数值K下社团划分结果的模块度值，选取能使模块度值最大的节 点聚类结果作为最佳划分结果。将最佳划分结果中属于同一类的节点作为一个社团结构， 得到最终划分结果。该例中，当Κ = 2时，社团划分的模块度值最大，故该结果即为最终结果。 [014引装置实施例
[0149] 本发明实施例提供了一种Κ均值社团结构挖掘装置，参见图4,该装置包括：
[0150] 计算单元，用于基于局部扩展的种子筛选法选择Κ个初始种子社团，并计算各个初 始种子社团的中屯、节点作为初始种子节点，所述中屯、节点坐标作为Κ均值聚类种子节点的 坐标值，其中，Ke[2，N-l];
[0151] 获取单元，用于将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在 当前K值下的社团结构划分；
[0152] 处理单元，用于获取在不同K值下的社团结构划分，计算不同参数值K下社团划分 结果的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将 最佳划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。
[0153] 本发明通过合理选择聚类中屯、作为K均值聚类算法中的初始种子节点，最后利用K 均值算法在低维欧氏空间中聚类网络节点，并聚类隶属于同一社团的网络节点，从而提高 了挖掘社团精度，进而提高了后续对系统分析的准确性。
[0154] 优选地，本发明实施例所述的装置还包括:映射单元;所述映射单元，用于根据复 杂网络G的邻接矩阵A计算各网络节点对之间的相同直接邻居节点的数目并组成相似度矩 阵S，根据相似度矩阵计算网络中各网络节点间的距离矩阵D;其中，所述邻接矩阵A为具有N 个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点Vi和节点vj之间有边相连时，au = l; 当节点i和j之间无直接连边时，aij = 0，其中，aij为邻接矩阵A中的各元素，具体表示节点间 的连边关系，i = l，2,. . .，N，j = l，2, . . .，N;当i = j时，aij = 0;所述的相似度矩阵S为具有N 个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点Vi和节点vj之间有边相连时，sij = (Ai.，Aj.);当节点巧Pj之间无直接连边时，sij = 0,其中sij为S中的各元素 ，i = l，2,. . .，N，j = 1,2, . . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i行元素组成的向量，
所述的离矩阵D为具有N个节点Vi的复杂网络图G，构造一个NXN的矩 阵，dij = (sii+sjj-2sij)1/2,其中，sij为S中的各兀素 ，i = l,2, . . . ,N，j = l,2,. . . ,Ν;利用多 维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维标度法MDS具体包 括:利用D = UAUT对矩阵D进行分解，其中，Λ =diag{Ai，A2, . . .，λΝ}为一个对角矩阵，且每 个元素 λι表示矩阵D的特征值，不失一般性的，令λι含λ2含...含λΝ，即将特征值按降序排列， 矩阵U中的第i列为特征值λι对应的特征向量，若在λι含λ2含...含λΝ中，存在Ρ个特征值大 于零，ρΕ[1,Ν]，则选择Ρ个特征值对应的特征向量记为m，U2,...，叫，并将其组成矩阵Ρ的 列，取矩阵P的N个行向量对应网络中N个节点在P维空间中的坐标，即（xi，X2，...，孙）；
[0155] 优选地，本发明实施例所述的计算单元具体用于，将复杂网络G中的每个节点均设 置一个标志位Si(i = l，2,. . .，N)，0表示该节点未被标识，1表示该节点已被标识;查找该网 络中的所有完全子图，根巧
计算查找到的每个完全子图中权值的平均值，并 按照从大到小的顺序排序，用Gi>G2> ...含Gm表示;在当前节点标志位为0的节点中选择度 数最大的节点，设该节点为曰，在Gi，G2, ...，Gm中选择包含节点a的完全子图组成子集 朽,，馬，·…^!·，r为从1到Μ之间的任意自然数，并在该子集中选取符合条件（1)和条件(2) 的完全子图Gi，将其中屯、节点坐标作为一个初始的种子节点:条件（1): Gi中的所有节点的标 志位均为0;条件(2):Gi含&，对于任意皆MG,,，G,:，...，巧};初始化节点子集Ω = 0，W选择 的初始种子社团Gi作为核屯、，根巧
扩展Gi的范围，其中，α和β为取值范围 在0至1之间的实数，对于Gi的直接邻居节点V，设将V加入子图Gi后的子图用Gi+v表示，根据 公式
得到的子图连边紧密度为，:若^ ，側将节点V加入子图 Gi，否则，不将节点V加入子图Gi中，将凡是能够使得子图Gi的连边密度&增大的邻居节点 均放入节点子集Ω中，直到公式
不再增大为止，并将集合Ω中的各节点 的标志位均设置为1;若K个种子社团均已初始化完毕，或者Gi，G2, ...，Gm中不再存在未被标 示的完全子图，且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择 剩余的种子节点;计算K个种子社团中各节点通过MDS映射后的中屯、坐标，作为K均值的初始 种子节点的坐标(x/，X2/，. . .，χ^κ)，所述相互距离最远原则具体包括:设当前已查到Θ/ (Θ/ Ε[Θ+1，Κ])个种子节点的坐标为yi，y2, . . .，ye'，网络中除种子节点之外的节点的坐标为01， 02, ...，ΟΝ-θ'，则采用相互距离最远原则选择的剩余种子节点0的坐标为网络中除了 yi, 72, ...，ye'之外的节点坐标中，符合下式
的节点，c/ E {〇1,〇2,...， ΟΝ-Θ' }，计算K个种子社团中各节点通过MDS映射后的中屯、坐标，作为K均值的初始种子节点 的坐标{x/，X2/，. ..，χ^κ};所述的各初始种子社团中屯、坐标的计算方式为:对于已查找到 的种子社团Gi，i = l，2, . . .，Κ，设其包含g个节点，各节点坐标为yi，y2, . . .，yg，则种子社团 中屯、坐标天
[0156] 优选地，本发明实施例所述获取单元具体用于，步骤（1)，将(X/，X2/，...，χ/κ)作 为初始聚类中屯、，将κ个集合Zi设置为空集，其中i = l，2，...，Κ，设置为空集;步骤(2)，循环 (3巧IK4)直到每个聚类不再发生变化为止;步骤(3)，在第t次迭代中，对网络中的任一节点 坐标X"按如下的方法把它调整到K个类别中的某一类别中去，对于某一类别i，其中i = l， 2，...，K，若所有的j辛i，其中，j = l，2，...，K，如果Mx"-χi'M<Mx"-χ'j||，则x"EZi，其 中，t为从1开始的自然数，||a-b II为坐标a与b之间的欧氏距离，设a和b均为P维向量;步骤 (4)，由第(3)步计算第i类的新中屯、坐标的第j个分量
式中，IZil为Zi类中 元素的数目。则第i类的中屯、坐标为：^/11，义/12，...，义/11()。根据新得到的中屯、坐标计算^ 的值为：
，若|1'-引<8，则退出程序，输出聚类结果21。= 1， 2，...，1〇，反之，令1 = ^，转步骤(3)。
[0157] 优选地，本发明实施例所述的处理单元具体用于，对复杂网络图GG进行社团划分 C，记C=ki，C2, . . .，Cp}，其中，P为从1开始到N之间的任意自然数，Cia = l，2,. . .，p)为复 杂网络图G中若干节点组成的集合，计算当前社团划分下的模块度
勺网络节点Vi与网络中其他节点的连 边数目，其中，i = l，2, . . .，N，M为网络连边的数目，Cm和Cn分别为节点VI和Vj所属的社团的 编号，其中，me[l,p]，ne[l,p]
[0158] 需要说明的是，本发明实施例的相关部分可W参照方法实施例的相关部分进行理 解，在此不再进行寶述。
[0159] 综上，本发明通过合理选择聚类中屯、作为K均值聚类算法中的初始种子节点，最后 利用K均值算法在低维欧氏空间中聚类网络节点，并聚类隶属于同一社团的网络节点，从而 提高了挖掘社团精度，进而提高了后续对系统分析的准确性。
[0160] W上所述，仅为本发明较佳的【具体实施方式】，但本发明的保护范围并不局限于此， 任何熟悉本技术领域的技术人员在本发明掲露的技术范围内，可轻易想到的变化或替换， 都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该W权利要求书的保护范 围为准。
【主权项】
1. 一种K均值社团结构挖掘方法，该方法包括： 基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种子社团的中心 节点作为初始种子节点，所述中心节点坐标作为K均值聚类种子节点的坐标值，其中，Ke [2,N-1]； 将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当前K值下的社团结 构划分； 获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结果的模块度值，选 取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最佳划分结果中属于 同一类的初始种子节点作为一个社团结构，得到最终划分结果。2. 根据权利要求1所述的方法，其特征在于，还包括： 根据复杂网络G的邻接矩阵A计算各网络节点对之间的相同直接邻居节点的数目并组 成相似度矩阵S，根据相似度矩阵计算网络中各网络节点间的距离矩阵D; 其中，所述邻接矩阵A为具有N个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点Vi 和节点Vj之间有边相连时，aij = l;当节点i和j之间无直接连边时，aij = 0,其中，aij为邻接 矩阵A中的各元素，具体表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时， aij = 0;所述的相似度矩阵S为具有N个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点 Vi和节点Vj之间有边相连时，Sij = (Ai.，Aj.);当节点i和j之间无直接连边时，Sij = O，其中 Sij为S中的各元素，i = l，2, . . .，N，j = l，2, . . .，N;当i = j时，sij = 0;Ai.表示矩阵A的第i行 元素组成的向量，所述的距离矩阵D为具有N个节点V1的复杂网络图G， 构造一个^_勺矩阵，屯=(8#8」」-28。）1/2，其中，81」为3中的各元素，1 = 1，2，···』，]·= 1，2，...，N; 利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维标度 法MDS具体包括:利用D = UAUt对矩阵D进行分解，其中，Λ =CliagIA1J2, ...，λΝ}为一个对 角矩阵，且每个元素\表示矩阵D的特征值，不失一般性的，令A1 2 λ2 2 ... 2 λΝ，即将特征值 按降序排列，矩阵U中的第i列为特征值M对应的特征向量，若在λ2> ... >λΝ中，存在ρ 个特征值大于零，ρΕ [1，Ν]，则选择P个特征值对应的特征向量记为U1，U2, . . .，Up，并将其组 成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在 P维空间中的坐标，即（Χ1，Χ 2,...， XN); 所述基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种子社团的 中心节点作为初始种子节点具体包括： 基于局部扩展的种子筛选法选择K个初始种子社团，并根据网络节点的欧氏坐标计算 各个初始种子社团的中心坐标作为各个初始种子社团的初始种子节点。3. 根据权利要求2所述的方法，其特征在于，所述基于局部扩展的种子筛选法选择K个 初始种子社团，并根据网络节点的欧氏坐标计算各个初始种子社团的中心坐标作为各个初 始种子社团的初始种子节点具体包括： 将复杂网络G中的每个节点均设置一个标志位3i(i = l，2, . . .，N)，0表示该节点未被标 识，1表示该节点已被标识； 查找该网络中的所有完全子图，根据计算查找到的每个完全子图中权 值的平均值，并按照从大到小的顺序排序，用G1^G2) ... 2Gm表示； 在当前节点标志位为〇的节点中选择度数最大的节点，设该节点为a，在Gi，G2, ... ,Gm中 选择包含节点a的完全子图组成子集!6心(7,:，·…?丨，r为从1到M之间的任意自然数，并在该 子集中选取符合条件（1)和条件(2)的完全子图G1，将其中心节点坐标作为一个初始的种子 节点： 条件（I):G1中的所有节点的标志位均为O; 条件(2) :Gi 之 Gj，对于任意 G，e {6^i-; 初始化节点子集Ω = 0，以选择的初始种子社团GHt为核心，根据扩展G1的范围，其中，α和β为取值范围在O至1之间的实数，对于仏的直接邻居节点V，设将V加 入子图G 1后的子图用Gdv表示，根据公式得到的子图连边紧密度为 iV,，若&^& ,则将节点ν加入子图匕，否则，不将节点￥加入子图仏中，将凡是能够使得 子图G1的连边密度巧增大的邻居节点均放入节点子集Ω中，直到公式不再增大为止，并将集合Ω中的各节点的标志位均设置为1; 若K个种子社团均已初始化完毕，或者G1,G2, ...，Gm中不再存在未被标示的完全子图， 且若当前已查找到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余的种子节 占. 所述相互距离最远原则具体包括：设当前已查到θ'(θ' ε[θ+ι，κ])个种子节点的坐标 为yi，y2,. . .，y^，网络中除种子节点之外的节点的坐标为〇1，〇2,. . .，on-θ'，则采用相互距离 最远原则选择的剩余种子节点〇的坐标为网络中除了yi，y2,... ,ye，之外的节点坐标中，符 合下式的节点，c/ G {〇1，〇2, .. .，0Ν-Θ，}，计算K个种子社团中各节 点通过MDS映射后的中心坐标，作为K均值的初始种子节点的坐标W ι,χ'2,...，X、}; 所述的各初始种子社团中心坐标的计算方式为：对于已查找到的种子社团G^i = I, 2，. . .，K，设其包含g个节点，各节点坐标为yi，y2，. . .，yg，则种子社团中心坐标为4.根据权利要求3所述的方法，其特征在于，将所述初始种子节点的坐标作为输入参数 进行K均值聚类，获取在当前K值下的社团结构划分具体包括： 步骤(1)，将(X71，X7 2，. . .，X7 κ)作为初始聚类中心，将K个集合Zi设置为空集，其中i = 1， 2,. . . , K ； 步骤(2 )，循环(3)到(4)直到每个聚类不再发生变化为止； 步骤(3)，在第t次迭代中，对网络中的任一节点坐标X〃按如下的方法把它调整到K个类 别中的某一类别中去，对于某一类别i，其中i = l，2，. . .，K，若所有的j矣i，其中，j = l， 2，...，κ，如果I IxIxZ1I |〈| |x〃-x、| |，则x〃eZl，其中，t为从1开始的自然数，I Ia-b| I为坐 标a与b之间的欧氏距离，设a和b均为P维向量； 步骤(4)，由第(3)步计算第i类的新中心坐标的第j个分量式中，I Z1IS 中元素的数目，则第i类的中心坐标为u，Y12,... ,X、），根据新得到的中心坐标 计算J '的值为：若I y -J I 0，则退出程序，输出聚类结果& (i = 1， 2，...，1〇，反之，令1 = ^，转步骤(3)。5. 根据权利要求1-4任意一项所述的方法，其特征在于，所述获取在不同K值下的社团 结构划分，计算不同参数值K下社团划分结果的模块度值，选取能使模块度值最大的初始 种子节点聚类结果作为最佳划分结果，将最佳划分结果中属于同一类的初始种子节点作为 一个社团结构，得到最终划分结果具体包括： 对复杂网络图G进行社团划分C，记C= {C1，C2, . . .，cP}，其中，p为从1开始到N之间的任 意自然数，ci(i = l，2,...，p)为复杂网络图G中若干节点组成的集合，计算当前社团划分下 的模块度式中，为网络节点V1与网络中其他 节点的连边数目，其中，i = l，2, ...，N，M为网络连边的数目，cdPcn分别为节点Vi和Vj所属 的社团的编号，其中，me[l，p]，ne[l，p]，6. -种K均值社团结构挖掘装置，其特征在于，包括： 计算单元，用于基于局部扩展的种子筛选法选择K个初始种子社团，并计算各个初始种 子社团的中心节点作为初始种子节点，所述中心节点坐标作为K均值聚类种子节点的坐标 值，其中，Ke[2，N-l]; 获取单元，用于将所述初始种子节点的坐标作为输入参数进行K均值聚类，获取在当前 K值下的社团结构划分； 处理单元，用于获取在不同K值下的社团结构划分，计算不同参数值K下社团划分结果 的模块度值，选取能使模块度值最大的初始种子节点聚类结果作为最佳划分结果，将最佳 划分结果中属于同一类的初始种子节点作为一个社团结构，得到最终划分结果。7. 根据权利要求6所述的装置，其特征在于，该装置还包括:映射单元； 所述映射单元，用于根据复杂网络G的邻接矩阵A计算各网络节点对之间的相同直接 邻居节点的数目并组成相似度矩阵S，根据相似度矩阵计算网络中各网络节点间的距离矩 阵D;其中，所述邻接矩阵A为具有N个节点 Vi的复杂网络图G，构造一个NXN的矩阵，当节点Vi 和节点Vj之间有边相连时，aij = l;当节点i和j之间无直接连边时，aij = 0,其中，aij为邻接 矩阵A中的各元素，具体表示节点间的连边关系，i = l，2,. . .，N，j = l，2,. . .，N;当i = j时， aij = 0;所述的相似度矩阵S为具有N个节点Vi的复杂网络图G，构造一个NXN的矩阵，当节点 Vi和节点Vj之间有边相连时，Sij = (Ai.，Aj.);当节点i和j之间无直接连边时，Sij = O，其中 Sij为S中的各元素，i = l，2,. . .，N，j = l，2,. . . ,N当i = j时，sij = 0;Ai.表示矩阵A的第i行元 素组成的向量，所述的距离矩阵D为具有N个节点V1的复杂网络图G，构造 一个~父_勺矩阵，(^ = (8^+8」」-28。）1/2，其中，8。为3中的各元素，1 = 1，2，...具」=1， 2, ...，N;利用多维标度法MDS将各网络节点映射为低维欧氏空间中的节点坐标;所述多维 标度法MDS具体包括:利用D = UAU^矩阵D进行分解，其中，Λ = CliagIA1J2, ...，λΝ}为一 个对角矩阵，且每个元素\表示矩阵D的特征值，不失一般性的，令A1 2 λ2 2 ... 2 λΝ，即将特 征值按降序排列，矩阵U中的第i列为特征值\对应的特征向量，若在A1 2 λ2 2 ... 2 λΝ中，存 在P个特征值大于零，Pe [I，Ν]，则选择ρ个特征值对应的特征向量记为ui，U2, . . .，uP，并将 其组成矩阵P的列，取矩阵P的N个行向量对应网络中N个节点在p维空间中的坐标，即（X 1， X2, . . . ,Xn)； 所述计算单元具体用于，基于局部扩展的种子筛选法选择K个初始种子社团，并根据网 络节点的欧氏坐标计算各个初始种子社团的中心坐标作为各个初始种子社团的初始种子 节点。8.根据权利要求7所述的装置，其特征在于， 所述计算单元具体用于，将复杂网络G中的每个节点均设置一个标志位S1G = IJ, ...， N)，0表示该节点未被标识，1表示该节点已被标识；查找该网络中的所有完全子图，根据.计算查找到的每个完全子图中权值的平均值，并按照从大到小的顺序排序， 用Gi2G2> ... 2Gm表示;在当前节点标志位为O的节点中选择度数最大的节点，设该节点为 a，在G^G2, . . .，Gm中选择包含节点a的完全子图组成子集丨?.··Α丨_，r为从1到M之间的 任意自然数，并在该子集中选取符合条件（1)和条件(2)的完全子图G1，将其中心节点坐标 作为一个初始的种子节点:条件（I):Gi中的所有节点的标志位均为O;条件(2):Gi 2 Gj，对于 任意G/e ;初始化节点子集Ω = 0，以选择的初始种子社团Gi作为核心，根据-扩展Gi的范围，其中，α和β为取值范围在〇至1之间的实数，对于G i的直接 邻居节点V，设将V加入子图61后的子图用GAv表示，根据公式得到的子 图连边紧密度为^，若^^+,2&，则将节点V加入子图61，否则，不将节点V加入子图6 1中， 将凡是能够使得子图G1的连边密度巧增大的邻居节点均放入节点子集Ω中，直到公式不再增大为止，并将集合Ω中的各节点的标志位均设置为1;若K个种子 社团均已初始化完毕，或者G1,G2, ...，Gm中不再存在未被标示的完全子图，且若当前已查找 到的种子节点数目Θ小于K，则采用相互距离最远原则选择剩余的种子节点；所述相互距离 最远原则具体包括:设当前已查到θ' (θ' Ε[Θ+1，Κ])个种子节点的坐标为yi，y2, . . .，ye'，网 络中除种子节点之外的节点的坐标为〇1，〇2, ...，〇ν-θ'，则采用相互距离最远原则选择的剩 余种子节点〇的坐标为网络中除了 y I，y 2，. . .，y θ，之外的节点坐标中，符合下式的节点，c/ e {〇1，〇2, . . .，ΟΝ-θ，}，计算K个种子社团中各节点通过 MDS映射后的中心坐标，作为K均值的初始种子节点的坐标2, ...，X、};所述的各初 始种子社团中心坐标的计算方式为:对于已查找到的种子社团G1, i = l，2，...，Κ，设其包含 g个节点，各节点坐标为y I，y 2，. . .，y g，则种子社团中心坐标为9. 根据权利要求8所述的装置，其特征在于， 所述获取单元具体用于，步骤⑴，将UW2,... Υκ)作为初始聚类中心，将K个集合 Z1设置为空集，其中i = l，2，...，K，设置为空集;步骤(2)，循环(3)到(4)直到每个聚类不再 发生变化为止;步骤(3)，在第t次迭代中，对网络中的任一节点坐标χ〃按如下的方法把它调 整到K个类别中的某一类别中去，对于某一类别i，其中i = l，2，...，Κ，若所有的j矣i，其中， j = l，2，"_，K，如果I IxW-X^I |〈| |χ〃-χ? I，则x〃EZi，其中，t为从1 开始的自然数，I |a_b| 为坐标a与b之间的欧氏距离，设a和b均为p维向量;步骤(4)，由第(3)步计算第i类的新中心 坐标的第j个分量式中，I Zi I为Zi类中元素的数目，则第i类的中心坐标为： (X' ilY i2, . . . ,X' iK)，根据新得到的中心坐标计算J'的值为：.若 LT -J I〈S，则退出程序，输出聚类结果Zi(i = 1，2，. . .，K)，反之，令J = y，转步骤(3)。10. 根据权利要求6-9中任意一项所述的装置，其特征在于， 所述处理单元具体用于，对复杂网络图G进行社团划分C，记C= {C1，C2, ...，cP}，其中，p 为从1开始到N之间的任意自然数，Cl(i = l，2,. . .，p)为复杂网络图G中若干节点组成的集 合，计算当前社团划分下的模块度网络节点Vi与网络中其他节点的连边数目，其中，i = l，2,...，N，M为网络连边的数目，~和 Cn分别为节点Vi和Vj所属的社团的编号，其中，me[l，p]，ne[l，p]，
【专利摘要】本发明公开了一种K均值社团结构挖掘方法及装置，本发明通过合理选择聚类中心作为K均值聚类算法中的初始种子节点，最后利用K均值算法在低维欧氏空间中聚类网络节点，聚类隶属于同一社团的网络节点，从而提高了挖掘社团精度，进而提高了后续对系统分析的准确性。
【IPC分类】G06F17/50, G06Q10/10
【公开号】CN105488247
【申请号】CN201510784716
【发明人】范科峰, 李琳, 姚相振, 周睿康, 樊晓贺, 叶润国
【申请人】中国电子技术标准化研究院
【公开日】2016年4月13日
【申请日】2015年11月16日
最新回复(0)