基于谱方法的复杂网络“反社区”划分

《基于谱方法的复杂网络“反社区”划分》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学硕士学位论文基于谱方法的复杂网络“反社区”划分姓名：王帆申请学位级别：硕士专业：系统工程指导教师：沈轶20080603华中科技大学硕士学位论文摘要复杂网络是对自然界和人类社会中系统的高度抽象。复杂系统通常由若干群（组）构成，当群（组）的内部边明显的多于外部边时，网络具有社区结构；相反，当群（组）的外部边明显多于内部边时，网络呈现出一种“反社区”结构。属于同一“反社区”的结点间无连接或连接松散，属于不同“反社区”的结点间连接紧密，具有“反社区”结构的复杂网络对应的图为二模图或多模图。本文致力于研究复杂网络的“反社区”结构的划分方法，揭示看上去错综复杂

2、的网络是怎样由相对独立又互相交错的“反社区”组成的。本文根据社区结构的划分方法，引入模块性的思想，定义了模块性函数Q，把寻找“反社区”结构的过程转化为使模块性函数Q的值最小化的过程，并得到了模块性矩阵的负特征值个数与“反社区”个数之间的关系；然后研究了模块性矩阵的性质，讨论了最小负特征值在“反社区”划分中的作用，得出了能将网络划分为2个“反社区”的基于最小负特征值的谱平分法；接着进一步分析了其它负特征值在“反社区”划分中的作用，得出了能将网络分为了c个“反社区”的基于多个负特征值的谱方法。最后，仿真了k部图和近似k部图的划分过程，将得到的结果与真实情况进行对比

3、，验证了基于最小负特征值的谱平分法和基于多个负特征值的谱方法是确实可行的。关键词：“反社区”谱方法负特征值特征向量I华中科技大学硕士学位论文AbstractThecomplexnetworksarethehighlyabstractofthesystemsofnatureandhumansociety.They’reusuallycomposedofsomegroupsorclusters.Iftheedgesingroupsorclustersareobviouslymorethantheedgesbetweenthem,thenetworkismadeup

4、ofsomecommunities;onthecontrary,iftheedgesingroupsorclustersareobviouslylessthantheedgesbetweenthem,thenetworkcontainssome“anti-communities”,anditscorrespondinggraphisabipartitegraphorak-partitegraph.Thenodesbetweendifferent“anti-communities”haveverycloserelationshipswitheachother,a

5、ndthenodesinthesame“anti-community”havedistantrelationships.Thisthesisisdedicatedtoinvestigatethe“anti-communities”whichhavenotonlytheindependencebutalsothecorrelationcharacteristics.Onthefoundationoflearningmethodsofdetectingcommunities,firstly,thethesisimportthetheoryofthemodulari

6、ty,definethemodularityfunctionQ,transformtheprocessoffinding“anti-communities”totheprocessesofminimizingthemodularityfunctionQ,andprovetherelationshipbetweenthenumberof“anti-communities”andthenumberofmodularitymatrixs’negativeeigenvalues.Secondly,bydoingtheresearchonthecharacterofmo

7、dularitymatrix,findoutthemethodoffinding“anti-communities”basedonthelargestnegativeeigenvalue,whichcandividethenetworkintotwo“anti-communities”,anddenominateitasthespectralmethodbasedonthelargestnegativeeigenvalue.Thirdly,analyzestheeffectsoftheothernegativeeigenvalues,foundouttheme

8、thodoffinding“anti-