一种增量式的社区发现算法研究

An Incremental Community Discovering Approach

传统社区发现算法基本上属于静态的分析算法,其计算复杂性使其难以适应目前网络结构的频繁变化。为了改善静态算法的这一局限性,通过对Radicchi静态算法进行扩展,提出一种增量式的社区发现算法,并将其应用于MSN Space链接结构分析上。该算法能在网络结构变化频繁时进行增量式计算并保证社区发现的实时性。实验结果表明,该增量式算法在处理网络结构变化时的效率相对传统算法有显著提高,尤其对小规模频繁变化的网络有很强的适应力。

Because of the complexity of static community discovery algorithm, traditional algorithm is weak in adapting network structural change. By extending Radicchi static algorithm, an incremental community analysis algorithm is brought forward. The incremental algorithm can obtain high result freshness when network changes frequently. By applying this algorithm to MSN Space linkage structure analysis, high efficiency promotion is obtained comparing to traditional static algorithm. The experiment result shows that the efficiency is promoted even more when the small changes happen frequently to network structure.