# Suppose disjoint communities in the corresponding line

Suppose the theorem is not true. Based on the facts that 1) a
vertex in a partition of L(G) corresponds to an edge with end
vertices in a cover of G, and 2) vertex 1 and 2 in G are attached
to C1 and C2 respectively, we find that vertex ‘1-2’ in L(G)
belongs to two different parts, which contradicts the definition
of partition. Hence, Theorem 3 must be true.
From theorem 3 we can see that if an optimal cover of G
satisfies the conditions in Theorem 3, then it is impossible to
directly compute the optimal cover through a partition of L(G).
Hence, we have the following corollary.
Corollary 2: Disjoint communities obtained by partitioning
the vertex set of L(G) are finer-grained and suboptimal overlapping
communities of G.
IV. THE PROPOSED ALGORITHM LEPSO
According to Corollary 2, to detect overlapping communities
in a network, we just need to detect disjoint communities in
the corresponding line graph. In this section, we present an
improved DPSO, named LEPSO, to optimize partition result of
the line graph.
A. Representation of Communities
Common encoding schemes of DPSO include integer encoding
and binary encoding 44. The locus-based adjacency
representation scheme is a popular integer encoding scheme to
represent communities in a network, described as follows.
Given line graph L(G) = < N,E >, where N = (n1 ,
n2 ,…,nk ), a partition of L(G) can be represented as a particle
Xi = (Xi1 , Xi2 ,…,Xid ), where k = |N|. If Xij = m, then
there exists an edge e = nj , nm in the communities corresponding
to particle Xi, that is, vertex nj and nm are in the
same community in L(G).
This representation scheme, however, has a drawback, i.e.,
randomness in particle initialization and particle position update
procedure makes it difficult to avoid producing illegal particles.
In other words, edges represented by some components
of a particle may not exist in the network at all. To overcome
this shortcoming, we propose a novel representation scheme,
which represents a particle based on ordered neighbor list. The
key idea of our scheme is to utilize distribution information
of the neighbors of each vertex, so as to guarantee legality of
newborn particles produced during initialization or moving. We
exemplify this below.
Example 2: Suppose G is a network depicted in Fig. 4(a).
An example particle P encoded by locus-based adjacency representation
scheme is shown in Fig. 4(b), where edges <3, 6>,
<5, 1> and <7, 2> in particle P do not exist in G. So, P is an
illegal particle. In fact, we can create an ordered neighbor list of
all vertices as shown in Fig. 4(e). Based on the list we can use
our proposed scheme to represent a partition see Fig. 4(d) of
G as a legal one, as shown in Fig. 4(c).
Compared to traditional locus-based adjacency representation
schemes, our representation scheme has several advantages,
such as elimination of illegal particles completely, avoidance of
Fig. 4. Encoding particle based on ordered neighbor list. (a) Network G; (b)
illegal particle; (c) particle encoded by LEPSO; (d) generated communities; (e)
ordered neighbor list.”Dim” refers to dimension, and “Pos” refers to position.
generating local optimal communities obtained through iterative
bipartition strategy 11, and determining the number of
communities automatically.
B. Particle Fitness
The concept of community in a network is not rigorously
defined since its definition depends on the application domain
of interest. The subjectivity of community definition encourages
researchers to put forward various quality indices to evaluate the
goodness of a partition, among which the most famous one is
modularity 6. The idea underlying modularity is that a random
graph has no obvious cluster structure, thus edge density of a
cluster should be higher than the expected density of a subgraph
whose nodes are connected at random. Formally, modularity
can be defined as
f it(Pi) = Q (C) = m
c=1 
lc
|E|
?
 dc
2 |E|
2

(4)
where f it(Pi) is the fitness value of particle Pi, m the number
of communities in partition C of a network G = < N,E >, lc
the number of edges connecting vertices in a community c ? C,
dc sum of degree of the nodes in c, and |E| the total number of
edges in G.
C. Update Particle Velocity and Position
1) Update Particle Velocity: From (1) we can see that gbest
has a great impact on search ability of particle swarm, since it
acts as the leader of the swarm and every particle learns from it
in each iteration. When gbest falls into a local optimum, there
is a high possibility that the whole swarm is trapped in the local
optimum too. Traditional methods to update particle velocity are
generally useful in optimization, however those methods may
not fully capture cluster structure information of a network, as
demonstrated below.