摘要 动态网络社团结构挖掘有助于获取整体网络特性和发展规律。由于动态网络具有多个时刻，传统静态网络社团挖掘算法不仅容易在相邻时刻产生具有较大差异的社团划分结果，而且导致较高时间复杂度。虽然最近受到广泛关注的动态网络增量算法可以一定程度上降低算法时间复杂度，但普遍存在人工设定参数、可扩展性差等局限性。该文提出一种随机游走与增量相关节点相结合的社团挖掘算法(RWIV)进行动态网络社团挖掘。利用动态网络时间局部性即相邻采样时刻网络变化不大的特点，通过对增量相关节点进行随机游走聚类后社团划分，避免了对整个网络中的节点全部重新划分。实验结果和分析表明：RWIV算法可有效解决IC(Incremental algorithm for Community identification)和IDCM(Increment and Density based Community detection Method)判定参数难以选定、累积误差及网络突变等问题，其社团挖掘效率高于现有IC和IDCM算法。
Abstract：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.
肖杰斌, 张绍武. 基于随机游走和增量相关节点的动态网络社团挖掘算法[J]. 电子与信息学报, 2013, 35(4): 977-981.
Xiao Jie-Bin, Zhang Shao-Wu. An Algorithm of Integrating Random Walk and Increment Correlative Vertexes for Mining Community of Dynamic Networks. , 2013, 35(4): 977-981.
2013, Vol. 35 
