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.



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

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


social network G

overlapping communities of G

1.       Transform G into LG(G); build the
ordered neighbor list     


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

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)

         MPS = MPS U gbestk;

         MPS = MPS U gbestk;

11.     if fit(gbestk) tmax;

18.      Get partition HP of LG(G) that
corresponds to gbest;

          Transform HP into a cover CP of G;

19.      Return HABM(CP)