分类:Finding community structure in networks using the eigenvectors of matrices

M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74, 036104(2006).

Abstract

We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as “modularity” over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.

总结和评论

在文章^[1] 中，Newman把网络的集团结构的发现的问题变成了一个基于矩阵的本征值和本征向量的问题的优化问题。

实际上，原则上来说，所有的网络的问题，都可以转变成为矩阵的表达形式。这一点是非常重要的。尽管有的时候，这样的转变带来问题的解决，有的时候不能帮助解决问题。研究工作中，对一个问题具有一个根本形式的表达，以及具有多个形式的表达，是非常重要的。

另外，从对根本形式的深刻理解之中，产生新的问题和解法，也是创性的基本形式。

所有，这几个方面，网络、思维方式、创新、多个表象，都可以从Newman的这个工作以及Newman的其他好多工作中借鉴。

参考文献