一种增量式的社区发现算法研究

被引:4
作者
王慧芳 [1 ]
黄林鹏 [1 ]
俞晟 [2 ]
机构
[1] 上海交通大学计算机科学与工程系
[2] 上海交通大学信息安全学院
关键词
社区发现; 增量式算法; 社会网络;
D O I
暂无
中图分类号
TP301.6 [算法理论];
学科分类号
081202 ;
摘要
传统社区发现算法基本上属于静态的分析算法,其计算复杂性使其难以适应目前网络结构的频繁变化。为了改善静态算法的这一局限性,通过对Radicchi静态算法进行扩展,提出一种增量式的社区发现算法,并将其应用于MSN Space链接结构分析上。该算法能在网络结构变化频繁时进行增量式计算并保证社区发现的实时性。实验结果表明,该增量式算法在处理网络结构变化时的效率相对传统算法有显著提高,尤其对小规模频繁变化的网络有很强的适应力。
引用
收藏
页码:149 / 152+167 +167
页数:5
相关论文
共 10 条
[1]  
Partitioning sparse matrices with eigenvectors of graph. Pothen A,Simon H,Liou K P. SIAM Journal on Computing . 1990
[2]  
Defining and identifying communities in net- works. F Radicchi,etal. . 2004
[3]  
Email as spectrosco- py:Automated discovery of community structure within organiza- tions. T J R yler,D M Wilkinson,B A Huberman. Proceed- ings of the First International Conference on Communities and Technologies . 2003
[4]  
The theory of Social Structure. N S F adel. . 1957
[5]  
Structural models. F Harary,N R Z orman,& D Cartwright. . 1965
[6]  
Structural Balance:a Generalisation of Heider‘s Theory. C D artwright,& F Harary. Psychological Review . 1956
[7]  
Algebraic connectivity of graphs. Fiedler M. Czechoslovak Mathematical Journal . 1973
[8]  
Social Network Analysis:A brief theoretical review and further perspectives in the study of Informa- tion Technology. Francesco Martino,Andrea Spoto. PsychNology Journal . 2006
[9]  
Community structurein social and bi-ological networks. Girvan M,Newman MEJ. Proceedings of the National Academy of Sciences of the United States of America . 2002
[10]  
An efficient heuristic procedure for partitioning graphs. Kernighan B W,Lin S. Bell System Technical Journal, The . 1970