资源描述：
《【2011】基于字典学习的网络社团结构探测算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、中国科学:信息科学2011年第41卷第11期:1343{1355www.scichina.cominfo.scichina.com论文基于字典学习的网络社团结构探测算法张忠元中央财经大学统计学院,北京100081E-mail:zhyuanzh@gmail.com收稿日期:2011{01{14;接受日期:2011{05{17中央财经大学学科建设基金资助项目摘要复杂网络中的社团结构探测对于理解网络的拓扑结构和功能有重要的意义.本文将字典学习方法应用到社团结构探测问题中,给出一种新的字典学习方法,并将其和其他几种流行的模型与算法作了系统比较.在
2、三种类型的人工数据和来自不同领域的实际数据上的实验结果表明,本文所提出的算法在社团结构探测问题上是非常有效的,具有算法简单、收敛速度快、计算精度高等特点.关键词社团结构探测字典学习最小二乘回归非负矩阵分解1引言复杂网络已经成为描述自然和社会中的系统结构的一个有力工具,是研究热点.研究表明,复杂网络中经常是有社团结构的.尽管对社团结构难于给出一个明确的数学化的定义,我们可以大体上将社团结构描述为网络中的一个顶点集,其内部连接是紧密的,而与外部的连接是疏松的.许多证据表明,社团结构经常是有其特殊含义的.比如说,在生物网络中,社团结构经常是一个
3、功能模块或者通路,而在社会网中,社团结构经常是由一群持相同观点的人组成,在科研合作网中,社团结构则经常是某一个科研领域等.图1给出了一个直观的社团结构的例子,这是一个真实的社会网络,描述了某个俱乐部里34名成员之间的人际关系.这34个人分成两组,即该网络有两个社团结构.详细的信息可以在第3.1.5小节中找到.文献中已经发展了大量有趣的模型来探测复杂社会网络中的社团结构.这些模型根据研究视角的不同大体可以分为两类：图分割模型和分层模型.图分割模型将网络看做一个整体,经常是通过优化某些描述网络结构的目标函数来达到分割网络的目的,比如优化模块化
4、函数Q(见第3.1.1小节).具体的模型包括文献[1]中的方法,谱聚类模型[2;3]以及基于非负矩阵分解的模型等.而分层模型则正好相反,正如其名字所表达的那样,其试图建立一个网络中顶点的分层结构或者是树状的聚类结构,该类模型一般有两种:从下至上"和从上到下".第一种类型的模型开始的时候,将每一个顶点看做一个独立的社团,然后逐步地将这些社团合并,而第二种类型的模型开始的时候,将所有的顶点放在一起,看做一个大的社团,然后将这个社团逐步地分割开.具体的模型包括文献[4,5]中的方法.需要指出的是,网络社团结构探测问题本质上是属于无监督学习的
5、范畴,因此我们可以将目光转向那些在无监督学习领域中取得了成功应用的模型,比如非负矩阵分解模型(nonnegativematrixfac-引用格式:张忠元.基于字典学习的网络社团结构探测算法.中国科学:信息科学,2011,41:1343{1355张忠元:基于字典学习的网络社团结构探测算法25261828222029321324102432114173482331533961730161115121927图1空手道俱乐部人际关系网Figure1Karateclubnetworkasanillustrativeexample.Thenetwor
6、kisdividedintotwodensesubgroupsduetoadisagreementontheclubfees.Thelightones(redones)aresupportersoftheadministrator(nodeid:34)andthedarkones(blueones)aresupportersoftheinstructor(nodeid:1).Thiscommunitystructureisalsoobtainedfromourproposedalgorithmtorization,NMF).NMF起初是为
7、图像处理而提出的[6].由于其在自动探测数据背后隐藏模式方面具有的良好能力,NMF已经在无监督学习领域中获得了广泛的应用,包括环境学、文本挖掘、生物信息学、多媒体数据分析等.该模型可以被表述如下:给定一个非负的n£m的目标矩阵X,我们试图找到两个非负矩阵F和G,分别是n£k的和k£m的,使得X¼FG,换句话说,(F;G)是下面的规划问题的最优解：minJ(X;FG);(1)s:t:F>0;G>0;(2)其中J(X;FG)是某些度量X和FG之间相似性的费用函数.最经常使用的费用函数是最小二乘方函数和K-Ldivergence.事实上,已经有
8、一些工作,使用NMF来探测网络社团结构了.其中最近的一个有趣的工作是对称非负矩阵分解模型,这是由文献[7]提出的.该模型可以被表述如下:minkX¡GTGk2;s:t:G>0:2尽管已经发展了
