《网络中的模块性及群落结构.docx》由会员分享，可在线阅读，更多相关《网络中的模块性及群落结构.docx（10页珍藏版）》请在课桌文档上搜索。
1、重庆邮电高校争论生堂下考试答卷2022学年第1学期考试科目图论及其应用姓名王裕坤年级2022级专业计算机应用技术2022年12月18日网络中的群落结构性分析及应用摘要：在对科学网络的争论中,包括社交网络、计算机网络、管理网络等都需要对网络进行分类，探测以及描述网络的特征是网络系统争论过程中一个特别重要的问题。其中有一个特别高效的方法就是在网络可能的划分上使质量函数模块度（“小面山y）的值达到最优（在后面会看到实际上就是使得模块度的值达到最大）。而模块度可以用描述网络的特征矩阵的特征向量来表示，这种表示方法使用谱算法对群落进行探测。这种算法与竞争算法相比具有更好的性能，这在以后的应用中会加以阐释
2、。关键字：划分；模块度；社交网络；模块1、社交网络划分的背景很多具有科学价值的系统都可以用节点组，或者通过边所连接的节点来进行表示，这样的例子有很多，比如因特网、万维网、新陈代谢网络、食品网络、神经网络、通信和分布式网络、社交网络等等。关于网络系统的争论已经有很多的历史了，但是争论网络的爱好在最近的十几年却渐渐的增加，特殊是在数学科学中，这主要是由于描述现实的网络拓扑中大规模精确数据应用的增加。对这些数据的分析显示了一些未料到的特征，比如高度的网络传递性，幕-律度的分布性等等O现在有一个争论方向引起了很大的关注，这就是对网络中群落结构进行探测以及描述，这意味着发觉高密度节点相连接的群落，而在不
3、同的群落之间只有很少的连接。这种探测群落的力量将会有重要的意义，例如，在万维网上的群落所对应的网页组可能具有相同的话题，网络中的群落可能与现实中的社会单元或者团体相对应。现在仅有的发觉是网络中包含的紧紧交织的群落可以传递出有用的信息，假如一个新陈代谢的网络被划分成这样的群落，那么它可以为网络动态变化的模块式观点供应有用的证据。这种网络的动态变化的模块式观点是不同群落中的结点具有不同的功能，并且具有肯定的独立性。在过去对网络的划分上分为两个派系，并且这两个派系都有很长的历史,第一种是采用图形来进行划分,这种方法被计算机科学以及相关的领域推崇,广泛的应用于平行计算以及集成电路的设计。其次种方法是采
4、纳块模型、层次性集中或者群落结构探测等,主要是一些社会学家、物理学家以及生物学家在用这个方法，这个方法特殊应用于社会和生物网络。而在本文中的重点则是在网络数据集的基础卜来探测群落结构。当给定我们一个网络时,我们最常用的方法就是去查找两个部落节点的分界以此来削减两个部落之间边的数目，这种最小切割的方法是在图形分割中最为常用的。但是这种仅仅依靠边数来量化群落结构明显不是一个好的方法，一个好的分割群落的方法应当不仅仅是在两个群落之间有很少的边数，更应当是两个群落之间的边数比我们预期的要少。2、模块度在社交网络划分上应用在网络中真正群落结构和边的排布从静态上看具有惊人的全都性，这可以通过模块度的方法进
5、行量化。模块度的值既可以是正数也可以是负数，正数预示着群落可能的结构，因此我们可以特别精确的得到网络的结构通过查找那些模块度的值比较大的网络划分。这种依靠模块度来分割的方法比其他的分割的方法都要优秀的多，现在我们就来看一看如何求的一个网络的模块度的值。假设我们的网络包含个顶点，首先我们考虑将网络划分为两个群落的的状况,假如顶点i属于群落1我们让Sj=1,假如顶点，属于群落2我们让耳=-1,顶点i与顶点j之间的边我们称为&,它的值通常是O或者L当多条边存在的状况下它的值会更大一些(&也被称为邻接矩阵)。在同一时间顶点i和顶点/有边的概率为左勺/2?，其中仁和“是顶点的度，而?是网络中边的总数目，
6、模块度的值。是落在相同群落全部顶2I点4-%j27的总和。通过观看我们可以得到假如顶点i和顶点，在同一群落那么;33+l)为1,假如不在同一群落那么表达式的值为0。我们可以将模块度的值如下表示：=-A/-l儿书+1)=；Z(&-j-Ksi14mF2m4ZK2Z通过观看我们还得知2m=2%=Z4。前面的1/4帆仅仅是一个传统的参数，它的只是为前面的模块度定义相兼公。方程1可以很便利的写成矩阵的形式。Q=-LstBs4m在这里S为列向量，它的元素为我们又定义了一个对称矩阵B并且它的元素为：学我们称8矩阵为模块度矩阵，在这篇文章中我们大部分的篇幅都在争论这个矩阵的特性。我们会发觉B矩阵的每行以及每列
7、的元素之和都为0,所以它总会有一个与特征值0相对应的特征向量(1,1,1)o依据已给出的方程2,我们可以将S用矩阵3的标准化特征向量ui的线性组合加以表示，即：s=Z：产四，其中q=4s.然后我们发觉：2=J1MirBEau4mjjj4nf在这里民是矩阵B的特征值，其所对应的特征向量为小,我们假设特征值依据递减的挨次进行排列，即：12-n.我们可以对网络恰当的划分使得模块度的值达到最大，同样也可以选择4的值使得模块度的值达到最大。这意味着我们要选的S使得(%JSM.的值达到最大。假如我们对S出了标准化之外没有其他的限制，我们3以很简洁的完成这个任务，即：选择S和特征向量对成比例。这将全部的比重
8、都加在了特征值为Sl的这一项上，其他项都为0,由于特征向量都相互正交。但是不幸的是，我们有此外一个限制，即S元素的值只能是+1或者-1，这意味着我们不能选择让S和对成比例。但是我们可以S与对尽可能的平行,这和让的点积取的最大值是等价的。简明的说就是假如中相应的元素为正数我们就将Sj设置为+1,相反我们将Sj设置为换句话说，我们将全部顶点相对应的元素，正数放在一个群里，剩下的放在另一个群落。这也给划分网络供应了一个方法:我们计算模块度矩阵的第一个(最大的)特征向量,然后依据特征向量的元素的符号来将顶点分成两个不同的群落。我们很快就发觉了这个方法所具有的令人满足的特点，第一，在之前已经被说的很清晰
9、了，这个方法在不知道群落的大小的状况下仍旧是有用的。不像一些最小化群落之间边的数目的传统算法，这种算法不需要对群落的大小加以限制或者禁止单群落全部顶点的平凡解。然而在模块度矩阵中可能没有正数的特征值，在这种状况下，第一个特征向量为(1,1,1)与单群落全部顶点相对应。但是这是最精确的结果，这个算法在这种状况下告知我们，在特征值都为非正数的模块度矩阵是不行分割的，这从方程4可以直接的看出来，由于全部的项目的和只能是0或者是负数。不能分割的网络其模块度的值为0,这是算法可以达到的最好的结果。这是算法的一个很重要的特征，这个算法不仅能高效的对网络进行分割，并且在没有好的分割方法存在的状况下能拒绝分割
10、网络，后一种状况在网络中成为不行分割。即：假如模块度矩阵没有正数的特征值那么这个网络不行分割，这个思想在以后的争论中起着重要的作用。这个算法仅用到第一个特征向量元素的符号，但是元素的度也能传递一些有用的信息。假如顶点所对应的元素有很大的度的话，那么它对模块度的值的贡献也就越大，反之亦然，这在方程4中可以看到。假如一个顶点，它所对应的元素的度很大，不行能将这个元素从一个群落移动到另一个群落而不引起模块度值大的变化。因此在第一个特征向量中的元素值描述了顶点属于指定群落的紧密程度，那些元素值比较大的是群落的核心成员，而那些值相对较小的元素在群落中则不那么重要。3、试验部分我们现在运用模块度的方法得出
11、了这样一个算法，现在我们来简洁的检验一下这个算法是不是像我们前面所得出的结论那样可以高效的对网络进行划分。在某个试验室中有两个试验小组，分别为A组和B组，总共有12人。他们都在试验室但是分别从事的是不同的项目，每一个组有一个核心的成员负责他的组的进度，有些成员即在从事A组的项目同时又在做B组的项目，为了便利我们把每一个成员进行编号，分别为1号到12号，由于我们已经事先知道哪些成员是属于A组，哪些成员是属于B组，所以我们这个小试验只是来进行验证，以下是试验室全部成员的网络拓扑：10图一图一中的网络拓扑就描述了试验室各成员之间的状况，很明显的可以看出一组以6号成员为核心成员，一组以11号成员为核心
12、成员，现在我们考虑在Matlab的试验环境下对上述算法进行测试，看是否能够达到我们要求的效果。上述的网络拓扑建立相应的邻接矩阵如下：X1234567891011121010000100000210100100000030101010000004001001000000500000I0000006011110100000710000100000080000101010109000000010110100000000010111100000001110112000000000110由图二可知，邻接矩阵是一个对称矩阵，对每一对（i,力在邻接矩阵A中都有唯一的一个元素&与之对应。在Matlab实现模块
13、性划分算法的源代码如下：function=Main()Social_Data=xlsread(D:matlab5(IEtest_data.xls);K=2,332,L5,3,433,4,2;%用以描述回点的度A=SociaLData;%A表示为邻接矩阵m=sum(K);%为全部结点度的总和kl,k2=size(A);B=zeros(kl,k2);fori=l:k2forj=l:k2B(i,j)=A(i,jK(i)*K(j)2*m;endend%求出B矩阵V,D=eig(B);max=D(l,l);fork=l:k2if(D(k,k)max)max=D(k,k);max.k=k;endend%求
14、出B矩阵的最大特征值VeCtojmaX=V(:,max_k);cl=l;c2=l;fort=l:k2if(Vector.max(t)0)S_pos(cl)=t;cl=cl+l;%求出B矩阵最大特征值所对应的最%大特征向量%依据最大特征向量中的值对结点进行%分类elseS.neg(c2)=t;c2=c2+l;endendRl=sprintf(,Thenumbersoffollowingnode%disingroupAn,S.pos)R2=sprintf(,Thenumbersoffollowingnode%disingroupBnS_neg)运行上述程序得到如下的结果截图如下:MainRl=Th
15、enumbersoffollowingnode1isingroupAThenumbersoffollowingnode2isingroupAThenumbersoffollowingnode3isingroupAThenumbersoffollowingnodeisingroupAThenumbersoffollowingnode5isingroupAThenumbersoffollowingnode6isThenumbersoffollowingnode7isingroupAingroupAR2=Thenumbersoffollowingnode8isingroupBThenumbersof
16、followingnode9isingroupBThenumbersoffollowingnode10isingroupBThenumbersoffollowingnode11isingroupBThenumbersoffollowingnode12isingroupB将上述截图的结果转换为用例图如下:从图三中可以看出，上述算法完善的把成员进行了划分，也就是我们之前在所说的A、B组。所以验证的结果还是比较满足。现在我们重新组织一下试验室的人的组织结构的到一下的网络拓扑：我们重新运行程序得到一下的结果:图五我们从图五可以看到原先5号成员是属于A组，但是经过人员的调动，他现在被划分到B组中去，这也
17、和实际中的比较全都。当然假如我们有此外的一种状况，原先试验室的A、B组被合为一组来做一个比较大的项目，这样的话应当不会有可能的分组才对，所以我们用上述的算法进行再次的验证，这样的话试验室人员的组织拓扑结构如下图所示：图六而通过上述算法我们得到图七的网络拓扑划分:图七我们发觉在图七中上述的算法还是把网络划分为两个组，其实这并不是算法本身的问题，而是我们所涉及的这个试验室组的模型并不完善，而在相对完善的模型中我们可以看到假如网络是一个统一的整体，那么算法是拒绝分割的，这也是本算法一个比较重要的方面。4、总结在这篇文章中，我们争论了在社交网络群落结构检测方面的一些问题，通过查找模块度的最大值来得到网
18、络的划分，我们也展现了这个问题是如何通过转化为与模块度矩阵的特征向量和特征值相关的问题的，在文章的最终，我们通过一个试验室成员的例子对我们所提出的算法进行了一些测试，测试的结果还是特别满足,在最终的一个例子中，是试验数据而不是算法的问题导致了结果的不正确,在真实的试验性数据下，所得到的结果应当还是特别抱负的。我们可以将这个算法用于真实世界的网络结构中。备注：这篇论文是在2006发表的ModularityandCommunitystructureinnetworks的验证性试验，在论文中首次提出通过模块度的思想对社交网络进行划分，而在本论文中只是通过一些实例对模块度的相关算法进行验证。5、参考文
19、献:1. (2006)ModularityandCommunitystructureinnetworks.2. 殷剑宏吴开亚(2005)图论及其算法26-353. 同济高校数学系线性代数(第五版)4. Albert,R.&Barabarsi,A.-L.(2002)Rev.Mod.Phys.74,47-97.5. Dorogovtsev,S.N.&Mendes,J.F,F.(2002)Adv.Phys.51,1079-1187.6. Newman,M.E,J.(2003)SIAMRev.45,167-256.7. Newman,M.E.J.(2004)Eur.Phys.J.B38,321-330
20、.8. Danon,L.,Duch,J.,Diaz-Guilera,.&Arenas,A.(2005)J.Stat.Mech.,P09008.9. Flake,G.W.,Lawrence,S.R.,Giles,C.L.&Coetzee,F.M.(2002)IEEEComputer35,66-71.10. Girvan,M.&Newman,M.E.J.(2002)Proc.Natl.Acad.Sci.USA99,7821-7826.11. Holme,P.,Huss,M.&Jeong,H.(2003)Bioinformatics19,532-538.12. Guimera,R.&Amaral,L.A.N.(2005)Nature433,895-900.13. Elsner,U.(1997)GraphPartitioning:ASurvey(TechnischeUniversitatChemnitz,Chemnitz,Germany),TechnicalReport97-27.
