Journal of Frontiers of Computer Science and Technology ›› 2009, Vol. 3 ›› Issue (3): 282-292.DOI: 10.3778/j.issn.1673-9418.2009.03.006

• 学术研究 • Previous Articles     Next Articles

CommTracker: A Core-based Algorithm of Tracking Community Evolution

WANG Yi+, WU Bin, YANG Shengqi   

  1. Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-05-15 Published:2009-05-15
  • Contact: WANG Yi


王 翼+,吴 斌,杨胜琦   

  1. 北京邮电大学 智能通信软件与多媒体北京市重点实验室,北京 100876
  • 通讯作者: 王 翼

Abstract: CommTracker, a novel and parameter-free algorithm of tracking community evolution is proposed, which utilizes the representative quality of core nodes in a community to establish the evolving relationship between two communities in consecutive time snapshots. With such a distinct strategy, it is suitable for analyzing large scale datasets. Depending on relationships established from CommTracker, it is feasible to identify community split and mergence. In addition, two relationships amongst evolution traces, evolution traces intersection and community rebirth, are also studied. At last, the correctness and effectiveness of our algorithm on 4 real datasets are demonstrated.

Key words: social network analysis, community evolution, algorithm

摘要: 提出了一种无需参数设置的社区演化跟踪算法CommTracker,它有效利用社区中核心点来为两个处于不同时间段的社区之间建立演化关系。这种方法非常适合于大规模数据集。当社区之间的演化关系建立后,利用CommTracker来鉴定演化路径中存在的分裂点和融合点。重点分析了社区演化路径之间的关系:路径相交和社区重生。最后,通过实验,验证了CommTracker的正确性和有效性。

关键词: 社会网络分析, 社区演化, 算法