动态社区的点增量发现算法

Vertex-based Incremental Algorithm for Dynamic Communities Detecting

当前复杂网络中动态社区发现方式大多为孤立地考察当前时间节点,没有利用之前时间节点上社区结构的信息,因而产生了大量的冗余计算。为解决此问题,基于动态社会网络在短时间内未发生过多改变的短时平滑性假设,提出了一种增量聚类动态社区发现算法。该算法将物理学领域万有引力的思想引入到动态社区发现中,针对动态社会网络中的节点,定义了节点间的相互作用力,在t-1与t时刻社区变化差量的基础上,通过比较节点间作用力对节点的社区归属进行了分析和调整,以期在t时刻快速准确地发现动态社区。在安然邮件数据集上的实验表明,当网络中的节点数量达到104以上,提出的算法能够在两分钟左右的时间内挖掘出模块度为0.53左右的社区结构,优于其他几种算法,说明该方法能够快速准确地挖掘出较好的社区结构。

Currently ,most ways of community detection in dynamic complex networks belongs to separate observations on nonce time nodes without utilization of community structural information on former time nodes, thus more redundant computation has been genera- ted. To solve this problem,on the short-term smoothness assumption that the dynamic community networks could not generate too many changes in short-time interval, an incremental clustering algorithm for detecting dynamic communities has been proposed. The universal gravitation in physic field has been introduced into community detection and mutual forces has been defined between nodes in dynamic community. The community adscription of the node has been analyzed and adjusted through comparison of the mutual forces based on the difference between t - 1 and t interval so as to detect dynamic community quickly and accurately at t interval. Results of experiments on Enron email dataset show that when the network has more than 104 vertices,the proposed algorithm can detect community structures with modularity at around 0.53 within about two minutes and is more efficient than other algorithms,and thus it can detect dynamic communi- ty structures quickly and accurately.