文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 复杂网络社团发现算法研究新进展_骆志刚
侵权投诉

复杂网络社团发现算法研究新进展_骆志刚

50 国防科技大学学报 2011年

模糊聚类结果作为最终的社团划分结果。

上述方法在判断社团数上需要预先给定或花费大量计算以确定合理的社团数目。我们在文献[24]中提出基于通信-时间核构建距离矩阵,输入到模糊相似性传播聚类来实现重叠社团发现,在考虑节点长程相关性的同时,可以自适应地确定社团数。值得一提的是,此类算法的关键在于所构建的距离矩阵,采用何种节点距离更符合实际情况在具体应用中是一个值得探索的问题。2 3 基于非负矩阵分解的重叠社团发现算法

非负矩阵分解方法是一种聚类和降维技术,已经在多个领域取得广泛应用。它将特征矩阵V近似分解为两个非负矩阵Wn k和Hk n,使得两者的乘积尽可能等于原有特征矩阵。将非负矩阵分解应用于社团发现,其思想是特征矩阵V中的每个行向量v可以近似地看作H的列向量的线性组合:v=wH,w其中是W的行向量,从而可以用相对于V更少的基向量H来表示整个数据空间,而w则表示各基向量对于产生数据点v所起到的权重。因此,可以利用W将各节点聚成k个类,而W各分量值表示每个节点到每个社团的绝对隶属度。从图3所示的w分量曲线可以看出,节点6和节点11分别与两个社团呈现出一定的隶属关系,说明节点6和节点11是潜在的社团重叠区域。算法关键在于如何选取特征矩阵以表

复杂网络社团发现算法研究新进展_骆志刚

示复杂网络中所蕴含的拓扑信息。

降低算法对初始条件的敏感性,扩大了适用范围。2 4 基于种子扩展思想的重叠社团发现算法

此类算法的基本思想是以具有某种特征的子网络为种子,通过合并、扩展等操作向邻接节点扩展,直至获得评价函数最大的社团。该类算法近两年来得到了迅速发展。

[27]

Lancichinetti等提出以若干个节点为种子,通过扩展形成对整个网络的覆盖,即LMF算法。该算法定义了两个适应度函数:社团的适应度和节点对社团的适应度。其种子扩展的基本步骤是:以单个节点v为初始社团g,考虑所有与其相邻的节点A,将对g的适应度最大的邻节点加入到当前社团形成g ,重新计算g 中各节点的适应度,将适应度为负的节点剔除,重复上述过程直至扩展后的社团其邻节点对它的适应度均为负。通过一定的种子选取策略(每次选取尚未指派到社团的节点),可以由扩展得到的若干个局部社团生成整个网络的覆盖,保证网络中每个节点至少被一个局部社团所覆盖。

此外,尚明生、陈端兵等也提出类似的种子扩[28-29]

展思想,主要区别在于种子选择策略、扩展评价函数上的不同。如文献[28]提出节点强度的概念,即节点所有邻接边的权重之和,依次以最大强度的单个节点为种子;文献[29]则是以最大团为种子,通过合并和扩展两步逐步形成最终的社团,而两者均以考虑节点隶属度的重叠模块度Qo为扩展评价函数。

2 5 基于混合概率模型的重叠社团发现

前述很多算法均是先给出社团结构的定义或量化特征,然后再设计相应的算法寻找社团。换句话说,这些方法均需对社团结构作出假设。针对此问题,Newman等建立了社团结构的混合概率模型,以概率方法对复杂网络的社团结构进行探

图3 一个包含两个重叠节点的简单网络

及其对应的w分量

Fig.3 Asimplenetworkwithtwooverlappingnode

andcorrespondingwentries

索,以求得期望最大的社团结构,从而避开社团定义的问题。他们认为社团是由具有相似连接的节点组成的,因此定义两个模型参数 ri和 r用来刻画社团r的特征,其中 ri表示社团r中某节点对节点i的连接概率, r表示社团r的节点数占整个网络节点数的比例。通过这两个参数,可以将网络的邻接矩阵A看作是观察数据,并引入缺失数据g={gi},用来表示节点i所属社团,由此将问题转换为典型的带缺失数据的最大似然估计问题,其似然度计算如下:

L=lnP(A,g| , )(|( , )

[30]

张世华等首次将NMF应用于重叠社团发现

[25]

,他们以扩散核为基础,将正规化后的核矩

阵作为特征矩阵V,同时采用一种梯度下降的迭

代方法来求解W和H。该算法最大的优点在于能够给出节点与社团之间所属关系的绝对概率,这是上述算法所不具备的。但该算法依然需要预先给定k参数,不可避免在确定k值时带来较高的计算开销,仅适用较小规模的网络。Zarei等则引入新的节点-节点关联矩阵作为特征矩阵

[26]

,

上一页第4页

热门文档

相关文档

  • 复杂网络社团发现算法研究新进展

    些堡盟塑咝坐坠翌堕匹堡旦墅婴墅望型盟垡塑复杂网络社团发现算法研究新进展‘骆志刚,丁凡,蒋晓舟,石金龙 国防科技大学学报 v01.33No.1 &坠:垫!! 文章...

  • 复杂网络社团发现算法研究新进展

    2011 文章编号: 1001- 2486( 2011) 01- 0047- 06 复杂网络社团发现算法研究新进展骆志刚, 丁凡, 蒋晓舟, 石金龙 410073) ( 国 防科技大学 计算机学院, ...

  • 复杂网络重叠社团挖掘算法

    ( 19) : 41774187. 〔 3〕 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究 J〕 . 国防科技大学学报, 2011 , 33 ( 1 ): 4752. 新进展〔 〔 ...

  • 复杂网络重叠社团挖掘算法_吕晓军

    ( 19) : 41774187. 〔 3〕 骆志刚, 丁凡, 蒋晓舟, 等. 复杂网络社团发现算法研究 J〕 . 国防科技大学学报, 2011 , 33 ( 1 ): 4752. 新进展〔 〔 ...

  • 复杂网络中节点重要度评估

    张湘莉兰.苑波.骆志刚.Zhang Xianglilan.Yuan Bo....复杂网络中的社团结构算法综述[期刊论文]-电子科技...陈盖凯 基于约束熵的复杂系统重要节点崩溃控制研究[...

  • 复杂网络中节点重要度评估

    张湘莉兰.苑波.骆志刚.Zhang Xianglilan.Yuan Bo....复杂网络中的社团结构算法综述[期刊论文]-电子科技...陈盖凯 基于约束熵的复杂系统重要节点崩溃控制研究[...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email