The Kernighan-Lin algorithm divides a network into two communities trying to maximize the modularity of the division. The division into more than two groups can be performed using repeated bisection of a network. We start by dividing the network first into two parts and then we further subdivide those parts in to smaller ones, and so on. Given that our goal is to maximize the modularity for the entire network, we should only go on subdividing groups so long as doing so results in an increase in the overall modularity. If we are unable to find any division of a community that results in a positive change in the modularity, then we should simply leave that community undivided. The practical indicator of this situation is that our bisection algorithm will put all vertices in one of its two groups and none in the other, effectively refusing to subdivide the community rather than choose a division that actually decreases the modularity. When we have subdivided our network to the point where all communities are in this indivisible state, the algorithm is finished and we stop.
The Kernighan-Lin algorithm divides networks into two communities starting from some initial division, such as a random division into equally sized groups. The algorithm then considers each vertex in the network in turn and calculates how much the modularity would change if that vertex were moved to the other group. It then chooses among the vertices the one whose movement would most increase, or least decrease, the modularity and moves it. Then it repeats the process, but with the important constraint that a vertex once moved cannot be moved again, at least on this round of the algorithm. And so the algorithm proceeds, repeatedly moving the vertices that most increase or least decrease the modularity. When all vertices have been moved exactly once, we go back over the states through which the network has passed and select the one with the highest modularity. We then use that state as the starting condition for another round of the same algorithm, and we keep repeating the whole process until the modularity no longer improves.
Hence the algorithm visits a limited (polynomial in size) fragment of the entire state space (which is exponential in size), where each state is a bisection of the network with a given modularity value, and it chooses the best encountered state. Of course, there is no guarantee that such state is the optimal one. Notice that the algorithm accepts moves to worse states, that is, bisections with a lower modularity with respect to the previous division. This is a typical strategy in function maximization: to reach the top of the hill at times it is necessary going downhill for a while.
The described algorithm is quite efficient. At each step of the algorithm we have to evaluate the modularity change due to the movement of each vertex. Such modularity update can be computed by analyzing the neighbourhood of the moving vertex in time proportional to its degree. Hence, if the network is stored as an adjacency list, choosing the vertex to move costs $O(m)$. Since there are $n$ steps in one complete round of the algorithm, the total time of a round is $O(mn)$. This time must be multiplied by the number of rounds the algorithm performs before the modularity stops increasing. It is not well understood how the number of rounds required varies with network size. In typical applications the number is small and it seems quite unlikely that the number of rounds would actually increase as network size grows. Hence, assuming it remains constant, the time complexity of the algorithm is $O(mn)$, which is $O(n^2)$ for sparse graphs.