###
DOI:
Journal of Software:2009.20(zk):184-192

IC:动态社会关系网络社区结构的增量识别算法
单波,姜守旭,张硕,高宏,李建中
(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)
IC: Incremental Algorithm for Community Identification in Dynamic Social Networks
SHAN Bo,JIANG Shou-Xu,ZHANG Shuo,GAO Hong,LI Jian-Zhong
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3612   Download 4324
Received:May 01, 2009    Revised:July 20, 2009
> 中文摘要: 社会关系网络(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.
文章编号:     中图分类号:    文献标志码:
基金项目: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 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
Foundation items:
Reference text:

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

SHAN Bo,JIANG Shou-Xu,ZHANG Shuo,GAO Hong,LI Jian-Zhong.IC: Incremental Algorithm for Community Identification in Dynamic Social Networks.Journal of Software,2009,20(zk):184-192