作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

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

赵富强  1,张程  2,邢恩军  1,张铠  1   

  1. (1.天津财经大学理工学院,天津 300222; 2.天津大学计算机科学与技术学院,天津 300072)
  • 收稿日期:2014-11-03 出版日期:2015-12-15 发布日期:2015-12-15
  • 作者简介:赵富强(1974-),男,副教授、博士、CCF会员,主研方向:社会网络分析,数据挖掘;张程,硕士;邢恩军,讲师、博士;张铠,实验师、博士。
  • 基金资助:
    国家自然科学基金资助项目(11471239);天津市自然科学基金资助项目(15JCYBJC16000);天津市哲学社会科学研究规划基金资助项目(TJTJ15-002)。

Application Research of Algebraic Connectivity in Complex Network Cut Edge Model

ZHAO Fuqiang  1,ZHANG Cheng  2,XING Enjun  1,ZHANG Kai  1   

  1. (1.Institute of Ploytechnic,Tianjin University of Finance and Economics,Tianjin 300222,China; 2.School of Computer Science and Technology,Tianjin University,Tianjin 300072,China)
  • Received:2014-11-03 Online:2015-12-15 Published:2015-12-15

摘要: 复杂连通图的连通性由拉普拉斯矩阵第二小特征值决定,根据该特性,通过最小化网络连通性,提出基于边中心性测度的改进割边模型。删除网络代数连通性下降最快的多条边以提高运算速度。为避免节点过度分割,对权重进行重新定义,在同一个社区中,当度较大时,选取费 德勒向量中分量绝对值较大的进行权重计算。实验结果表明,在矩阵重排的基础上求取第二小特征值运行时间较重排前短,改进模型的分割精度能达到社团划分要求,适合处理中规模社区结构。

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

Abstract: 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.

Key words: algebraic connectivity, matrix reordering, Laplascian matrix, cut edge, complex network

中图分类号: