基于多重特征向量的有向网络社团结构划分算法

Detecting Community Structure in Directed Networks Via Multiple Eigenvectors

有向网络社团结构的识别对于理解复杂系统的结构特性和动力学特性都有着重要的意义。提出了一种基于拉普拉斯矩阵多重特征向量的有向网络社团结构划分算法,该算法利用有向网络拉普拉斯矩阵的前c个较小特征值所对应的特征向量来划分有向网络的社团结构。在人工数据和实证数据上与模块度的谱优化算法和模拟退火算法做了对比实验。实验结果表明,当社团结构明显时,该算法的归一化互信息指标的值接近于1。当社团结构不明显时,该算法所取得的效果也优于谱优化和模拟退火算法。与这两种算法相比,在实证网络上模块度Q值也可以提高17.28%和19.21%。该文工作对于理解有向网络上拉普拉斯矩阵的多重特征向量与网络的社团结构的关系具有十分重要的意义。

Detecting community structure of directed networks is of significance for understanding the structures and functions of complex systems. In this paper, we develop a spectral algorithm using multiple eigenvectors of the Laplacian matrix （MEL） in directed networks, where the c eigenvectors of the smallest eigenvalues of the Laplacian matrix are taken into account. We compare with the spectral optimization method （SOM） and simulated annealing （SA） algorithm of modularity matrix in directed networks on synthetic and empirical networks. The experimental results indicate that, the values of the normalized mutual information （NMI） obtained by our algorithm are approximated 1 when the community structures are clearly. The proposed algorithm outperforms the SOM and SA algorithms when the community structures are not clearly. In addition, the numerical results for empirical data set show that the modularity values Q could be enhanced by 17.28% and 19.21% respectively. This work may be helpful to analyze the relationship between the properties of Laplacian matrix and community structures in directed networks.