Towards a Heuristic Algorithm for Partitioning Network Community

摘要

Community detection is one of the key problems in the field of complex network analysis. In the paper, we mainly focus on the two-part division problem for network, i.e. community (or graph) partitioning. Based on the in-depth analysis on the partitioning results, a two-stage heuristic algorithm named SPC is proposed. It firstly identifies two pseudo-centers, and then generates two semi-communities by removing some undecided nodes. In the next step, it adopts an experience rule to classify such nodes. The experiment results show that the SPC algorithm is effective and can yield the best partitioning results for most instances.