Automated network analysis by projected power method

Many systems can be formulated by a network. The network analysis has attracted much recent research attention. In network analysis, a useful problem is to study the community structure of the network vertices. To automate the process of community detection, a criterion called “modularity” has been widely adopted for optimization. With highly demanding computational requirement for exact solutions, approximate solution has to be sought if tractability is to be ensured. Among the approximate solutions, the spectral relaxation method has attracted extensive attentions, which provides good accuracies and, more importantly, efficient solutions for large-scale problems. A recent advance in spectral method is the constrained power method, which introduces “iterative rounding” during the relaxation and rounding process and gives significantly improved accuracies while keeping the running time comparable to the standard spectral method. In this paper, our work establishes the connection between the constrained power method and the projected power method. With the connection, we are able to further analyze the method and get improved results in modularity optimization for automated network analysis.