A Constrained Optimization Method for Community Detection

摘要

Community detection is one of the most important problems in complex network research. In recent years, great efforts have been devoted to this problem in term of evaluating the resulting community structure. Our previous work has shown that in addition to the resolution limit of Q, both Q and D suffer from a more serious limitation, termed as extra weak community phenomenon, i.e. some derived communities do not satisfy even the weak community definition. In this paper, we provide a constrained optimization model to overcome extra weak community phenomenon. With an improved simulated annealing algorithm, we solve the constrained optimization model for both Q and D, and then use our new method in several practical community detection problems. The experimental results show that the new method can not only partition large networks into communities properly but also ensure that all resulting communities at least satisfy the weak community definition. In addition, we find that constrained optimization of Q finds fewer but large communities, while constrained optimization of D takes the network apart more detailed.