Complex Networks

148 

Complex Networks: An Algorithmic Perspective

Algorithm 8.1 KL Part

1: Input : G(V,E), V

A

, V

B

with |V| = 2n ⊲ two partitions of G

2: Output : A,B such that |V

A

| = |V

B

|, V

A

∪V

B

= V, V

A

∩V

B

= Ø

3: repeat

4: for all v ∈V do ⊲ start a pass

5: compute D(v)

6: end for

7: for i = 1 to n do

8: find unlocked a ∈V

A

and b ∈V

B

swapping results in largest gain g

i

9: lock a and b

10: for all v ∈V \{a,b} do

11: compute D(v) as if a and b are swapped

12: end for

13: end for

14: find k where G

k

=

P

k

i=1

g

i

is maximum

15: if G

k

> 0 then

16: swap v

A1

,..., v

Ak

with v

B1

,..., v

Bk

17: end if

18: ∀v ∈V, unlock v

19: until G

k

≤ 0

pass, the sequence of the sets of vertices locked which results in the ...