4. Optimizing the

Overlapping Community Structure

The finer-grained and

the suboptimal overlapping communities of the graph are to be refined, by partitioning

vertices in the line graph, in order to get the optimal overlapping

communities. . A

famous modularity functions proposed in 19.

(7)

Where P is a cover of

the graph, m represents the number of communities in the graph G. represents the degree

of the nodes. (A) Represent the adjacency matrix of the graph. Represent the number of

communities that contains the node i. to the post process finer-grained and the

suboptimal overlapping communities; we propose Hierarchical Agglomerative

Bottom-up merging techniques, namely HABM. Our HABM differs from the

traditional hierarchical clustering algorithm. HABM chooses to merge the communities

with the maximum community overlapping rate, instead of the maximal similarity.

5. Algorithm

Description

LEPSO Algorithm can be

described as follows. First initialize the particles needed. Next, we search

for the optimal partition of the line graph with the DPSO. Then, transform the

result of the line graph into a cover of the graph G.

Algorithm 3 LEPSO

Algorithm

Input:

social network G

Output:

overlapping communities of G

1. Transform G into LG(G); build the

ordered neighbor list

L;

2. k=0; MPS ? 0;

3. Initialise particle swarm Pk+1

based on L

4. fit(gbestk) = -?;

5. fit(pbestki) = -?,

i=1,2…, m;

6. Evaluate particles in Pk+1 with

(4)

7. for Pki Pk do

8. if fit(Pik+1)>fit(pbestik)

then pbestik=Pik;

9. gbestk= arg max fit(Pki)

10. if fit(gbestk) = fit(gbestk+1)

then

MPS = MPS U gbestk;

MPS = MPS U gbestk;

11. if fit(gbestk)

18. Get partition HP of LG(G) that

corresponds to gbest;

Transform HP into a cover CP of G;

19. Return HABM(CP)