基于网络加权机制的动态迭代聚类算法

Dynamical Network Clustering Algorithm Based on Weighting Strategy

动态网络在分析功能属性与拓扑结构的相关性方面具有重要作用。文中提出了一个新的动态迭代聚类算法,通过引入包含拓扑信息的权重W和紧密度T来调整边权和节点紧密度,以提高网络聚类结构检测的速度与准确度。值得一提的是,为了估计最优的迭代停止时间,文中利用以时间t为分辨率参数的稳定性指标(stability)作为测度指标,可以自然地找到使聚类划分达到最优的时刻t。该算法非常高效,而且不需要预先指定聚类的数目,因此可以方便地应用于各种模糊网络。最后在包括法律案例关联网络等数据上的实验结果表明,该算法能快速而准确地探测各种人工和现实网络的聚类结构。

Network dynamic plays an important role in analyzing the correlation between the function properties and the topological structure.This paper proposed a novel dynamical iteration algorithm incorporating the iterative process of membership vector with weighting scheme,i.e.weighting W and tightness T.These new elements can be used to adjust the link strength and the node compactness for improving the speed and accuracy of community structure detection.To estimate the optimal stop time of iteration,this paper utilized stability function defined as the Markov random walk auto-covariance.The algorithm is very efficient,and doesn’t need to specify the number of communities in advance,so it naturally supports overlapping communities by associating each node with a membership vector describing node’s involvement in each community.Theoretical analysis and experiments show that the algorithm can uncover communities effectively and efficiently.