一种基于随机块模型的快速广义社区发现算法

被引：11

作者：

柴变芳 ^{[1
,2
]}

于剑 ^{[1
]}

贾彩燕 ^{[1
]}

王静红 ^{[3
]}

机构：

[1] 交通数据分析与挖掘北京市重点实验室(北京交通大学)

[2] 石家庄经济学院信息工程系

[3] 河北师范大学信息技术学院

来源：

软件学报 | 2013年 / 24卷 / 11期

基金：

北京市自然科学基金;

关键词：

随机块模型; 广义社区; 时间复杂度; 复杂网络;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

随机块模型可以生成各种不同结构(称作广义社区,包括传统社区、二分结构、层次结构等)的网络,也可以根据概率对等原则发现网络中的广义社区.但简单的随机块模型在网络生成过程建模和模型学习方面存在许多问题,导致不能很好地发现实际网络的结构,其扩展模型GSB(general stochastic block)基于链接社区思想发现广义社区,但时间复杂度限制其在中大型规模网络中的应用.为了在无任何先验的情形下探索不同规模网络的潜在结构,基于GSB模型设计一种快速算法FGSB,更快地发现网络的广义社区.FGSB在迭代过程中动态学习网络结构参数,将GSB模型的参数重新组织,减少不必要的参数,降低算法的存储空间;对收敛节点和边的参数进行裁剪,减少每次迭代的相关计算,节省算法的运行时间.FGSB与GSB模型求解算法有相同的结构发现能力,但FGSB耗费的存储空间和运行时间比GSB模型求解算法要低.在不同规模的人工网络和实际网络上验证得出:在近似相同的准确率下,FGSB比GSB模型求解算法快,且可发现大型网络的广义社区.

引用

页码：2699 / 2709

页数：11

共 7 条

[1] 复杂网络的社区结构 [J].

程学旗 ;

沈华伟 .

复杂系统与复杂性科学, 2011, 8 (01) :57-70

[2]

Improved Bayesian inference for the stochastic block model with application to large networks[J] . Aaron F. McDaid,Thomas Brendan Murphy,Nial Friel,Neil J. Hurley.Computational Statistics and Data Analysis . 2013

[3] Variational Bayesian inference and complexity control for stochastic block models [J].

Latouche, P. ;

Birmele, E. ;

Ambroise, C. .

STATISTICAL MODELLING, 2012, 12 (01) :93-115

[4]

Community detection in graphs[J] . Santo Fortunato.Physics Reports . 2009 (3)

[5] A mixture model for random graphs [J].

Daudin, J. -J. ;

Picard, F. ;

Robin, S. .

STATISTICS AND COMPUTING, 2008, 18 (02) :173-183

[6]

Fast online graph clustering via Erd?s–Rényi mixture[J] . Hugo Zanghi,Christophe Ambroise,Vincent Miele.Pattern Recognition . 2007 (12)

[7] Estimation and prediction for stochastic blockmodels for graphs with latent block structure [J].

Snijders, TAB ;

Nowicki, K .

JOURNAL OF CLASSIFICATION, 1997, 14 (01) :75-100

← 1 →