Community structure is an important property of network. Being able to identify communities can provide invaluable help in exploiting and understanding both social and non-social networks. Several algorithms have been...Community structure is an important property of network. Being able to identify communities can provide invaluable help in exploiting and understanding both social and non-social networks. Several algorithms have been developed up till now. However, all these algorithms can work well only with small or moderate networks with vertexes of order 104. Besides, all the existing algorithms are off-line and cannot work well with highly dynamic networks such as web, in which web pages are updated frequently. When an already clustered network is updated, the entire network including original and incremental parts has to be recalculated, even though only slight changes are involved. To address this problem, an incremental algorithm is proposed, which allows for mining community structure in large-scale and dynamic networks. Based on the community structure detected previously, the algorithm takes little time to reclassify the entire network including both the original and incremental parts. Furthermore, the algorithm is faster than most of the existing algorithms such as Girvan and Newman＇s algorithm and its improved versions. Also, the algorithm can help to visualize these community structures in network and provide a new approach to research on the evolving process of dynamic networks.展开更多
动态网络社团结构挖掘有助于获取整体网络特性和发展规律。由于动态网络具有多个时刻,传统静态网络社团挖掘算法不仅容易在相邻时刻产生具有较大差异的社团划分结果,而且导致较高时间复杂度。虽然最近受到广泛关注的动态网络增量算法可...动态网络社团结构挖掘有助于获取整体网络特性和发展规律。由于动态网络具有多个时刻,传统静态网络社团挖掘算法不仅容易在相邻时刻产生具有较大差异的社团划分结果,而且导致较高时间复杂度。虽然最近受到广泛关注的动态网络增量算法可以一定程度上降低算法时间复杂度,但普遍存在人工设定参数、可扩展性差等局限性。该文提出一种随机游走与增量相关节点相结合的社团挖掘算法(RWIV)进行动态网络社团挖掘。利用动态网络时间局部性即相邻采样时刻网络变化不大的特点,通过对增量相关节点进行随机游走聚类后社团划分,避免了对整个网络中的节点全部重新划分。实验结果和分析表明:RWIV算法可有效解决IC(Incremental algorithm for Community identification)和IDCM(Increment and Density based Community detection Method)判定参数难以选定、累积误差及网络突变等问题,其社团挖掘效率高于现有IC和IDCM算法。展开更多
基金This work is supported by the NSFC Major Research Program under Grant No. 60496321, the National Natural Science Foundation of China under Grant No. 60503016, and the National High-Tech Development 863 Program of China under Grant No. 2003AA118020..
文摘Community structure is an important property of network. Being able to identify communities can provide invaluable help in exploiting and understanding both social and non-social networks. Several algorithms have been developed up till now. However, all these algorithms can work well only with small or moderate networks with vertexes of order 104. Besides, all the existing algorithms are off-line and cannot work well with highly dynamic networks such as web, in which web pages are updated frequently. When an already clustered network is updated, the entire network including original and incremental parts has to be recalculated, even though only slight changes are involved. To address this problem, an incremental algorithm is proposed, which allows for mining community structure in large-scale and dynamic networks. Based on the community structure detected previously, the algorithm takes little time to reclassify the entire network including both the original and incremental parts. Furthermore, the algorithm is faster than most of the existing algorithms such as Girvan and Newman＇s algorithm and its improved versions. Also, the algorithm can help to visualize these community structures in network and provide a new approach to research on the evolving process of dynamic networks.
文摘动态网络社团结构挖掘有助于获取整体网络特性和发展规律。由于动态网络具有多个时刻,传统静态网络社团挖掘算法不仅容易在相邻时刻产生具有较大差异的社团划分结果,而且导致较高时间复杂度。虽然最近受到广泛关注的动态网络增量算法可以一定程度上降低算法时间复杂度,但普遍存在人工设定参数、可扩展性差等局限性。该文提出一种随机游走与增量相关节点相结合的社团挖掘算法(RWIV)进行动态网络社团挖掘。利用动态网络时间局部性即相邻采样时刻网络变化不大的特点,通过对增量相关节点进行随机游走聚类后社团划分,避免了对整个网络中的节点全部重新划分。实验结果和分析表明:RWIV算法可有效解决IC(Incremental algorithm for Community identification)和IDCM(Increment and Density based Community detection Method)判定参数难以选定、累积误差及网络突变等问题,其社团挖掘效率高于现有IC和IDCM算法。
