Relations Between Adjacency and Modularity Graph Partitioning
This work addresses graph partitioning efficiency for researchers in network analysis, though it appears incremental as it builds on existing methods.
The paper establishes an exact linear relationship between the leading eigenvector of the unnormalized modularity matrix and the eigenvectors of the adjacency matrix, and shows that normalized adjacency clustering can be up to twice as efficient as normalized modularity clustering in numerical experiments.
This paper develops the exact linear relationship between the leading eigenvector of the unnormalized modularity matrix and the eigenvectors of the adjacency matrix. We propose a method for approximating the leading eigenvector of the modularity matrix, and we derive the error of the approximation. There is also a complete proof of the equivalence between normalized adjacency clustering and normalized modularity clustering. Numerical experiments show that normalized adjacency clustering can be as twice efficient as normalized modularity clustering.