Data Mining: The Textbook

Di = Ei − Ii

(19.14)

Of course, we are not interested in simply moving a node from one partition to the other, but in exchanging a pair of nodes i and j between two partitions. Then, the gain J_ij of exchanging nodes i and j is given by the following:

Jij = Di + Dj − 2 · wij

(19.15)

This is simply a sum of the gains from moving nodes i and j to different partitions, with a special adjustment for the impact on the edge (i, j ) that continues to be a part of the external cost of both nodes because of the exchange. The value of J_ij therefore quantifies the gain that one can obtain by exchanging nodes i and j. Positive values of J_ij result in an improvement of the objective function.

The overall algorithm uses repeated sequences of at most (n/2) heuristic exchanges between the two partitions, which are designed to optimize the total gain from the exchanges. Each such sequence of at most (n/2) exchanges will be referred to as an epoch. Each epoch proceeds as follows. A pair of nodes is found, such that the exchange leads to the maximum improvement in the objective function value. This pair of nodes is marked, although the exchange is not actually performed. The values of D_i for different nodes are recomputed, however, as if the exchange were already performed. Then, the next pair of unmarked nodes is determined with these recomputed values of D_i , for which the exchange leads to the maximum improvement in the objective function value. It should be pointed out that the gains will not always decrease, as further potential exchanges are determined. Fur-thermore, some intermediate potential exchanges might even have negative gain, whereas later potential exchanges might have positive gain. The process of determining potential exchange pairs is repeated until all n nodes have been paired. Any sequence of k ≤ n/2 contiguous potential pairs, starting with the first pair, and in the same order as they were determined, is considered a valid potential k-exchange between the two partitions. Among these different possibilities, the potential k-exchange maximizing the total gain is found. If the gain is positive, then the potential k-exchange is executed. This entire process of a

• 
  Without loss of generality, it can be assumed that the graph contains an even number of nodes, by adding a single dummy node.
  

630 CHAPTER 19. SOCIAL NETWORK ANALYSIS

Algorithm KernighanLin(Graph: G = (N, A), Weights:[w_ij ])

begin

Create random initial partition of N into N₁ and N₂; repeat

Recompute D_i values for each node i ∈ N ;

Unmark all nodes in N ;

for i = 1 to n/2 do

begin
Select x_i ∈ N₁ and y_i ∈ N₂ to be the unmarked node pair with the highest exchange-gain g(i) = J_xiyi ;

Mark x_i and y_i;
Recompute D_j for each node j, under the assumption that x_i and y_i will be eventually exchanged;
end

Determine k that maximizes Gk =