代数连通性在复杂网络割边模型中的应用研究  

Application Research of Algebraic Connectivity in Complex Network Cut Edge Model

作　　者：赵富强[1] 张程[2] 邢恩军[1] 张铠[1] 

机构地区：[1]天津财经大学理工学院,天津300222 [2]天津大学计算机科学与技术学院,天津300072

出　　处：《计算机工程》2015年第12期40-43,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(11471239);天津市自然科学基金资助项目(15JCYBJC16000);天津市哲学社会科学研究规划基金资助项目(TJTJ15-002)

摘　　要：复杂连通图的连通性由拉普拉斯矩阵第二小特征值决定,根据该特性,通过最小化网络连通性,提出基于边中心性测度的改进割边模型。删除网络代数连通性下降最快的多条边以提高运算速度。为避免节点过度分割,对权重进行重新定义,在同一个社区中,当度较大时,选取费德勒向量中分量绝对值较大的进行权重计算。实验结果表明,在矩阵重排的基础上求取第二小特征值运行时间较重排前短,改进模型的分割精度能达到社团划分要求,适合处理中规模社区结构。In complex connected graph,the second smallest eigenvalue of Laplacian matrix decides its connectivity.According to this characteristic,this paper presents advanced cut edge model based on edge centrality measure by minimizing the algebraic connectivity of networks.It cuts the edges which are the fastest decline in the algebraic connectivity at one time in order to reduce the time complexity.To avoid nodes overcutting,the weight is refined for each edge.When the degree is higher in a community,absolute maximum of the Fiedler vector is chosen for computing weight.Experimental results conclude that elapsed time by ordering matrix is less than before for computing the second smallest eigenvalue.The advanced cut model can be used in medium-size networks with suitable efficiency and accuracy for community detection.

关 键 词：代数连通性 矩阵重排 拉普拉斯矩阵 割边 复杂网络 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]