IC:动态社会关系网络社区结构的增量识别算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported by the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)); the National Natural Science Foundation of China under Grant Nos.60703012, 60533110, 60773063, 60903017 (国家自然科学基金); the Heilongjiang Province Fund f


IC: Incremental Algorithm for Community Identification in Dynamic Social Networks
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    社会关系网络(SNS)中社区结构的识别有助于得出有意义的个体间活动模式和社会发展规律,传统的静态SNS社区结构识别的方法不能发现SNS的变化规律,而最近受到广泛关注的动态SNS社区识别方法普遍存在可扩展性差的缺点.描述了动态SNS的数学模型,并在此基础上提出了动态SNS中发现社区结构的增量式新方法.提出方法利用动态网络时间局部性即相邻采样时刻网络变化不大的特点,通过增量分析避免对整个网络中的个体全部重新划分,达到较高的算法效率.分析和实验结果表明,效率高于现有方法,在大规模网络上(105结点量级)效率提升在一个数量级以上,发现的社区结构很好地反映出社会关系网络的本质结构.

    Abstract:

    Community structure in social networks (SNS) could provide interesting information, such as the pattern of social activities between individuals and the trend of social development. Traditional methods to identify communities on static social networks will miss interesting laws how SNS change. The few methods on modeling and analyzing of community structures in dynamic social networks, which are obtaining more and more attention recently, fail to identify large networks in acceptable time. This paper proposes an incremental new method to identify community structure in dynamic social networks. Utilizing the time locality that there’s little change in adjacent network snapshots, the paper incrementally analyzes social networks to avoid repeatedly partitioning the whole networks. Experiments demonstrate that this approach offers orders-of-magnitude performance improvement over state-of-the-art approaches on large scale networks (105 nodes) and can produce nice community structures which reflect the essence of SNS.

    参考文献
    相似文献
    引证文献
引用本文

单 波,姜守旭,张 硕,高 宏,李建中. IC:动态社会关系网络社区结构的增量识别算法.软件学报,2009,20(zk):184-192

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2009-05-01
  • 最后修改日期:2009-07-20
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号