College Papers

In interests in the fi eld of social

In recent years there is a lot of interests in the
fi eld of social networks partitioning. Network
partitioning is a process in which a complex net-
work is divided into different groups that each
part has similar features. For a particular network, the links between nodes in a particular
group are dense while the links between different groups are sparse. Due to this feature, each
of these groups form a community and is called
a partition or a module. The problem of dis-
covering the community structure is called community detection. There is no unique mathematical de finition for this problem that is acceptable by all the researchers 1. So every re-
searcher depending on the application and the
target network, uses a different de nition which
is based on some intuitive assumptions or past
algorithms. However, the defi nition which is accepted for community is that a group of ver-
tices which are connected to each other inside
a group more than other parts of the network
2. Currently there are various algorithms proposed to discovering community structures in
different networks but researches are so focused
on social network community detection problem.
One of the reasons for this attention is the high
knowledge which obtained by discovering such
structures. For example, in shopping sites we
can identify groups of people who do the same
stuffs by setting up efficient recommender sys-
tems which recommend customer more desirable
options to purchase; In this way business oppor-
tunities could be increased.
Complex network clustering is necessery to
undrestanding how organizing a network and
knowledge of its application and performance.
In recent decades many methods and techniques
in network clustering has been developed which
a summary of these is observable in 9.
Generally, network clustering could be mod-
eling in the form of an optimization problem
which is often put into NP-hard class. The
problem of community detection has been re-
ceiving a lot of attention and many different ap-
proaches have been proposed 15,16, 17, 18, 19,
20, 21. Since this problem is NP-hard, applying
some evolutionary algorithms could be useful as
a tool for solving the problem of community de-
tection. For example Pizzuti in 1 used genetic
algorithm for network clustering. Another work
which used GA is 22 that proposed a multiob-
jective evolutionary algorithm for dynamic net-
works community detection based on the frame-
work of nondominated sorting genetic algorithm
23. Gong 2 also presented an algorithm based
on memetic for this problem. Gog 13 proposed
a new evolutionary technique for community de-
tection in complex networks. The new algorithm
is based on an information sharing mechanism
between individuals of a population. In another
work Gong and others 14 proposed a multi-
objective discrete particle swarm optimization
algorithm to solve the network clustering prob-
lem. Following this work, Gong et al. intro-
duced a novel multiobjective immune algorithm
with local search to solve the community detec-
tion problem in dynamic networks 24. They
adopted Modularity and NMI as two objectives
to optimize. A comparative analysis of commu-
nity detection algorithms on arti cial networks
is done by Yang et al. 25. They provided ac-
tual techniques to determine which is the most
suited algorithm in most circumstances based
on observable properties of the network under
consideration. Another work by M. M. Ahmed
et al.26 proposed a multi-objective approach,
named MOGA-MDNet, to discover communi-
ties in multidimensional networks, by applying
genetic algorithms. The method aimed to nd
community structure that simultaneously max-
imizes modularity, as an objective function, in
all network dimensions.
In this paper, Imperialist Competitive Al-
gorithm(ICA) has been applied for community
detection. Since time is not signi cant in evo-
lutionary algorithms and some times running a
program takes hours we use ICA with parallel
approach, too. Using parallel ICA leads to bet-
ter results and also faster convergence rate than
the serial version of this algorithm.
In this section we define community detection
problem and specify the objective function for
optimization problem.
A complex network can be considered as a graph
G = (V;E). Radichi and others 6 have pre-
sented a comprehensive de nition of network
communities based on nodes degree. According
to this de nition the social network graph pre-
sentes as G = (V;E) which V and E are set of
vertices and edges, respectively. Considering ki
the degree of node i (number of links are con-
nected to node i) and A is adjacency matrix of
G . Aij = 1 if there is a link between node i
and j, otherwise Aij = 0. A weighted network
has weight w attached to the edges, where w is
a real number.Let ki =
?N
i=1 Aij denotes the degree of
a vertex i that is a total number of edges
connnected to vertex i. Directed networks in-
cludes two types of degrees: . a)in-degree and
b)out-degree. The number of links a vertex
received is called in-degree, such that kin
i =
?
j=1 Aij . While the number of links a ver-
tex sends is called out-degree, such that kout
i =
?
j=1 Aji. Total degree in directed networks is
Ki = kin
i +kout
i , whereas in undirected networks
total degree is Ki = kin
i = kout
i . In an undi-
rected network, the total number of degrees is
double the number of links in the network 5.
Let S  G denotes a subgraph which node i is
belong to S, we de ne kint
i =
?
i2S Aij that is
the number of linkes connecting vertex i to other
vertices in S. kext
i =
?
i?2S Aij also denotes the
number of links between i and other vertices out-
side S in G. Then S is a community in strong
sense if And S is a community in weak sense if In other words, communities in a network are
the groups of nodes, which are highly connected
to each other than to the rest of the nodes in the
network 6.
To detect community structure of networks, Li
et al. 31 have introduced a new measure called
modularity density (D), which is based on the
density of subgraphs. The higher the value
D, the more accurate a partition is. Consid-
ering a graph G = (V;E) with jV j = n and
jEj = m. The adjacency matrix of this network
is A.
The rst term of D is equivalent to the ratio
association 7 and the second term is equivalent
to the ratio cut 32. We have changed the sec-
ond term into kernel k-means according to 7.
Therefore we define KKM and RC as:
KKM and RC are two con
icting objects.
In other words, the second term in the right of
KKM relation can be considered as sum of the
density of the links inside a community, intra-
communities links, and RC is the sum of the
density of the links to outside of communities,
intercommunities links. To minimize KKM and
RC it should be assured that the links in a community are dense while the links between com-
munities are sparse and this is the natural of
communities in a complex network.
The objective function which is to be minimized using Imperialist Competitive Algorithm
can be de ned as sum of KKM and RC.
The Imperialist Competitive Algorithm (ICA)
is in evolutionary algorithm class. It was introduced by Atashpaz and Lucas 8 and inspired
by imperialist competition. In the algorithm all
countries are divided in two types: colonies and
imperialists. The imperialist competition is the
core part of the algorithm and it is expected that
colonies get close to the global minimum of the
cost function 8.
ICA is appropriate for optimization problems
but applying the evolutionary algorithms has
some challenges. As an example, when considering a large search space we need to a numerous
initial population to get a proper result but due
to the processor resources limitation, such requirement may not be satis fied. Also when dealing with a complex problem which requires complex computations the run time increase. There-
fore it is necessary to apply an efficient method
to improve the speed, stability and accuracy of
the results.
In this paper we rst do the community detection using ICA in its base form. Then to im-
prove the runtime and speed up the algorithm
we apply the parallel version of the algorithm.
ICA naturally has the parallel structure and so
parallel implementation of ICA is an appropriate
solution to improve the algorithm. In ICA, in
its base form, each imperialist and colony work
independently and after one decade(iteration) a
colony moves to another imperialist; so the algorithm is very similar to a multi-population
method which works on a processor. In the
next section we use a multi-population ICA to
solve the community detection in social networks
problem.
3 The Proposed Method
The multi-population model for ICA implementation applies a local search approach to solve
the community detection problem. The goal
is to use all capacities of the evolutionary algorithms (such faster convergence, shorter run-
time and accuracy of the results) to solve optimization problems. There are several meth-
ods to parallelize the evolutionary algorithms
such a master-slave, multi-population method
and combinational approaches. Among these
methods, the multi-population method has bet-
ter convergence speed and presents more accu-
4
rate resluts than other parallel methods 9. In
multi-population methods, there are indepen-
dent populations in different processors which
each has their own search space independently.
Every processor runs ICA on its population with
independent parameters values. Due to this in-
dependence, different levels of exploration and
exploitation could be exist, so the program does
not get in local optimal. Another advantage of
the multi-population method is its migration capability which it dramatically increase the per-
formance. In fact the migration is the most important part of parallelism in multi-population
method implementation that allows processors to
share their best results with other processors and
this fact leads to obtaining better results in less
iterations. There are different types of migration9, for example every processor can choose
the best/worst country to send to other processors or choose some random countries for sending. In this paper, the best countries are selected because we want the best results to be
shared and processors replace their worst country with the best country they received. Since
the method have executed on a multicore processor using any topology is meaningless, but if
the method runs on a real network with several
distinct computers it would be better to use the
ring topology. In this paper the receiver processors are selected based on ring topology, how-
ever considering a computer with multi core processor, the receiver processors can have any order. Figure 1 shows how the migration is done.
For example for a network with fully connected
topology, each processor can receive countries
from another processor. The ring topology is
used to reduce the migration rate and decrease
the distance of the migration.
Every country is a possible solution to the
community detection algorithm. Therefore the
algorithm creates randomly the initial population which are the possible solutions. Figure 2
shows a solution.
In the implementation we implement both
the message passing and shared memory to
transfer the best country of each processor.
Each processor is initialized with a set of in-
dependent country (number of countries in each
processor is the same) and ICA runs on them
independently. During each decade (iteration)
the best country from each processor Pi is sent
to the next processor Pi+1 and replaced with the
worst country in Pi+1 processors. Because the
migration process is done simultaneously in the
processors, the number of countries in every two
processors is equal at any time. The following
algorithm shows the multi-population ICA. In
the implementation all parameters are the same
in different processors and all ICA computations
are done independently in different processors.
In multi-population ICA, country selection is
increased by growing number of countries which
helps to obtain more accurate results in shorter
time and faster convergence rather that serial
ICA. So it is better to increase number of coun-
tries.
In order to check the proposed method more,
we implement the shared memory version of the
method. In this version every processor has a
copy of the variables of the parallel section and
there is no need to send/receive messages and
the replacement of the worst country with the
best one is possible by only a simple assignment.
In this section we used karate dataset22 to
show the PICA performance. The karate dataset
has 34 nodes. The execution time is presented
by number of processors and number of algo-
rithm iterations. The results for serial execu-
tion of the algorithm is done and a comparison
has done to the serial execution time of the al-
gorithm and the parallel version. The algorithm
is implement and runs on a Intel core i5 sys-
tem with 4 processors and 1.80 GHZ and 6 GB
memory. The implementation of the algorithm
is done with Matlab 2016 Ra. To parallelize the
algorithm, Parallel Computing Toolbox (PCT)
in Matlab has been applied.
The PCT in Matlab is running on a multi-
processor system and it can use 8 to 12 cores
according to the hardware speci cations. Parallel methods such as message passing and shared
memory can be implemented by this tool. Parallelism in Matlab can support GPU processing. Although using GPUs can leads to a signi cantly
speedup in execution time but not in all cases.
For example in the proposed algorithm, since in
each iteration number of empires is decreased it
causes the GPU cores being idle and this leads
6
to a long execution time.
4.1 Results
The unitized parameters for solving the community detection problem are shown in Table
1. Since the ICA as well as PICA produces different solutions in each different execution, the
presented results are the average of several executions.
Figure 3 shows PICA execution time using message passing for different number of iterations and different number of processors. As it
can be seen, by increasing number of processors
the execution time decreased. One of the reasons
of such event is due to the send/receive messeges
between processors which causes communication
overheads for the system. This would be more
intense with the increase of processors.
The accuracy of the solution does not change
with different number of processors but if num-
ber of iterations is little, the algorithm might
not present an acceptable results. Table 2 shows
number of algorithm iterations and number of
detected communities for them by PICA algo-
rithm. The algorithm with 30 and 50 iterations
detects more communities which it decreased by
increasing number of iterations. It is necessary
to note that respecting the randomness of the
initial population in PICA we consider the average of several executions of the algorithm. Number of real communities in karate dataset is 2
communities.
Figure 4 shows the PICA execution time us-
ing shared memory method for different number
of threads and different number of iterations.
The execution time in serial case is also pre-
sented in this gure (with 1 thread). As it can
be seen generally the execution time in shared
memory method is faster than messege passing.
By increasing number of threads from 1 to 3
for different number of processors the execution
time is decreased. But by increasing number of
threads the execution time is also increased or
does not change alot. Usually the best number
of threads to run a program is the number of pro-
cessors in the system. In case of more number
of threads, threads compete to obtain the pro-
cessor. Context switch between threads is also
another reason of increased execution time. The
use of more threads than the number of proces-
sors is useful when threads require IO operations
and other operations that block the threads.
Figure 5 shows the convergence speed diagram for 4 processors and messege passing
method and Figure 6 is the diagram in serial
case. Diagrams shows that convergence in par-
allel approach occures faster that serial.
The accuracy of obtained result is the same
in both parallel and serial cases. However
the accuracy is dependent to number of itera-
tions of the algorithm. The performance of the
presented algorithm on karate dataset with 34
nodes and 78 edges with 2 communities is eval-
uated. The reason for choosing karate dataset
is that number of communities is known. It is
also knows that each node is belong to which
community.
For the case when the ground truth of a net-
work is known, we adopt the so called normal-
ized mutual information (NMI) index described
in 27 to estimate the similarity between the
true clustering results and the detected ones.
Given two partitions A and B of a network, let
C be the confusion matrix whose element Cij is
the number of nodes shared in common by com-
munity i in partition A and by community j in
partition B. The NMI(A,B) is then defines as where CA(CB) is the number of clusters in
partition A(B), Ci:(C:j) is the sum of elements
of C in row i(column j), and N is the num-
ber of nodes of networks. If A = B, then
NMI(A;B) = 1; if A and B are totakky dif-
ferent, then NMI(A;B) = 0. The reliability of
this measure has been proved in 28.
To test the proposed method several datasets
has been used. For real datasets, in addition to
karate dataset, dolphins dataset has been used
as well. We used LFR 29 graph generator to
test the method. Two graphs with 50 and 70
nodes respectively has been generated with LFR
tool and given to the program to detect their
communities. The results shows in the form of NMI similarity measures in table 3.
For the case when the graph has more than
70 nodes (for example 100 nodes or more) the
execution time is so long. Therefore pica is not
appropriate for large graphs for community de-
tection problem. The long execution time is due
to the great number of initial population and
large number of iterations which are necessary
to have more accurate results. The larger the
initial population, the more problem space is
covered.
5 Conclusion and Future
Work
In this paper the implementation of ICA based
on multi-population approach for solving the
community detection problem has done. The
objective function consists of sum of two equa-
tions, kernel k-means and ratio cut, that have
been minimized using ICA. The parallel version
of ICA was implemented using two parallel ap-
proaches, messege passing and shared memory.
The results show that the messege passing ap-
proach has slower execution time than shared
memory, since it has the overhead of messege
passing communications. In shared memory we
have seen decreased execution time when the
number of threads equals to the number of pro-
cessors(cores) but with more threads the execu-
tion time increased.
The convergence speed is faster in parallel
case than the serial which is considerable in optimization problems. The reason is that in the
parallel implementation several threads or pro-
cessors work simultaneously to obtain the optimal solution and in each iteration the worst
country replaced with the best one in other processors and this leads to the faster convergence
speed. But in serial case there is only one processor which works to nd the optimal solution
and naturally it take more time that solution to
be converged.
The method have been tested on the real net-
works, karate and dolphins, and LFR networks
with 50 and 70 nodes, respectively. Test results
presented as NMI factor. For the case when the
graph has 100 nodes or more this method is not
appropriate due to the high execution time.
As the size of real world social networks in-
creases continuously, increasing scalability of our
proposed method will be investigated in the fu-
ture. Also enhancing the capabilities of this
algorithm to discover overlapped communities
is another aspect which needs more researches.
The proposed method has a high CPU time and
due to the ICA structure using GPUs leads to a
higher CPU time. There would be some meth-
ods to accelerate the parallel version of ICA
which would be a good research topic in the future.