Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (8): 2313-2318.DOI: 10.11772/j.issn.1001-9081.2020010072

• Advanced computing • Previous Articles     Next Articles

Improved community evolution relationship analysis method for dynamic graphs

LUO Xiangyu1,2, LI Jianan1, LUO Xiaoxia1, WANG Jia1   

  1. 1. College of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an Shaanxi 710054, China;
    2. School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an Shaanxi 710049, China
  • Received:2020-02-04 Revised:2020-04-17 Online:2020-08-10 Published:2020-04-28
  • Supported by:
    This work is partially supported by the Youth Program of National Natural Science Foundation of China (61702408), the Key Project of National Natural Science Foundation of China (51634007), the Scientific Research Program of Education Department of Shaanxi Province (18JK0507).

改进的动态图社区演化关系分析方法

罗香玉1,2, 李嘉楠1, 罗晓霞1, 王佳1   

  1. 1. 西安科技大学 计算机科学与技术学院, 西安 710054;
    2. 西安交通大学 电子与信息工程学部, 西安 710049
  • 通讯作者: 罗香玉(1984-),女,河北宁晋人,讲师,博士,CCF会员,主要研究方向:分布式存储、大数据;luoxiangyu@xust.edu.cn
  • 作者简介:李嘉楠(1992-),男,陕西西安人,硕士研究生,主要研究方向:分布式存储、动态图演化;罗晓霞(1964-),女,陕西扶风人,教授,主要研究方向:大数据、云计算、软件工程、分布式计算;王佳(1995-),女,陕西延安人,硕士研究生,主要研究方向:分布式存储、图的划分算法。
  • 基金资助:
    国家自然科学基金青年基金资助项目(61702408);国家自然科学基金重点项目(51634007);陕西省教育厅专项科研计划项目(18JK0507)。

Abstract: The community evolution relationships extracted by the traditional adjacent time slice analysis cannot fully describe the entire community evolution process in dynamic graphs. Therefore, an improved community evolution relationship analysis method was proposed. First, the community events were defined, and the evolution states of the community were described according to the occurred community events. Then, the event matching was performed on two communities within different time slices to obtain community evolution relationships. Results of comparison with the traditional methods show that the total number of community events detected by the proposed method is more than twice that revealed by the traditional method, which proves that the proposed method can provide more useful information for describing the evolution process of communities in dynamic graphs.

Key words: dynamic graph, community structure, community event, community evolution relationship analysis, community detection

摘要: 传统基于相邻时间片分析所获得的社区演化关系无法完备地刻画动态图社区演化的整个过程。为此提出了一种改进的社区演化关系分析方法。首先,定义社区事件,并根据发生的社区事件来描述社区的演化状态;然后,对两个不相同时间片内的社区进行事件匹配,从而获得社区演化关系;最后,通过实验将所提方法与传统方法进行比较。实验结果表明,所提方法发现的社区事件总数是传统方法的2倍以上,可为动态图社区演化过程的描述提供更丰富的信息。

关键词: 动态图, 社区结构, 社区事件, 社区演化关系分析, 社区发现

CLC Number: