For the last decades, community detection is a well-studied problem because it has applications in various fields. Variable Neighborhood Search (VNS) is an efficient metaheuristic for solving combinatorial optimization problems. Naturally, it has been applied to community detection in networks. If parallel algorithms exist for finding communities in networks and parallel implementations of VNS are designed for a variety of problems, parallel VNS was not yet used for community detection. For this problem, we present a parallel algorithm using VNS with shared memory and message passing interface. Numerical results are encouraging.