Community mining on dynamic weighted directed graphs

摘要

This paper focuses on community mining including community discovery and change-point detection on dynamic weighted directed graphs(DWDG). Real networks such as e-mail, co-author and financial networks can be modeled as DWDG. Community mining on DWDG has not been studied thoroughly, although that on static(or dynamic undirected unweighted)graphs has been exploited extensively. In this paper, Stream-Group is proposed to solve community mining on DWDG. For community discovery, a two-step approach is presented to discover the community structure of a weighted directed graph(WDG) in one time-slice: (1)The first step constructs compact communities according to each node's single compactness which indicates the degree of a node belonging to a community in terms of the graph's relevance matrix; (2)The second step merges compact communities along the direction of maximum increment of the modularity. For change-point detection, a measure of the similarity between partitions is presented to determine whether a change-point appears along the time axis and an incremental algorithm is presented to update the partition of a graph segment when adding a new arriving graph into the graph segment. The effectiveness and efficiency of our algorithms are validated by experiments on both synthetic and real networks. Results show that our algorithms have a good trade-off between the effectiveness and efficiency in discovering communities and change-points.