An Algorithm of Integrating Random Walk and Increment Correlative Vertexes for Mining Community of Dynamic Networks

Community mining in dynamic networks can help to obtain the whole network characteristics and the trend of network development. As dynamic networks usually consist of many consecutive static networks, traditional methods of identifying network communities will lead to significant variations between communities close in time and high time complexity. Although the general incremental methods (e.g. Incremental algorithm for Community identification (IC) and Increment and Density based Community detection Method (IDCM)) can reduce the time complexity at a certain extent, but they need to manually set the judgment parameter, and fail to identify large networks in acceptable time. In this paper, an algorithm of integrating Random Walk and Increment correction Vertexes (RWIV) is proposed to identify the dynamic network structure. RWIV algorithm first deals with increment correlative vertexes with random walk, and then adjusts the residual vertexes by analyzing their community affinity. The simulation results and analysis show that RWIV avoid manually selecting the parameter of IC or IDCM, which affect the accuracy of community mining, the cumulative error. RWIV can fit the situation of community structure sharp changes. The performance of RWIV is super than that of IC and IDCM methods.