Community Discovery Methods In Bipartite And Multiplex Networks

Many complex systems can be modeled as complex networks so as to be studied thoroughly.Community structure is a basic property of complex networks and identifying the hidden communities contributes to understand the structure of a network and facilitate other related tasks in networks.This thesis focuses on community detection algorithms in different types of networks,mainly including three classes of networks,namely traditional networks,multiplex networks and bipartite networks.The major work can be summarized as follows.1.Community detection can be modeled as optimization problems and modularity(Q)is the most popular global measure to uncover community structure in complex networks.However,it has the resolution limit,which means maximizing Q fails to identify small and natural communities when the size of the network is large enough.Recently,Aldecoa et al.proposed an alternative criterion,termed as Surprise(S),and showed that S might not have the resolution limit through experiments.Here,we propose a memetic algorithm to detect communities by maximizing S(MA_S-CD).Experiments on synthetic and real life networks validate the performance of MA_S-CD,and the communities found have higher intra-cluster densities.Moreover,maximizing S often leads to unbalanced partitions.We revise those results by means of a simple community merging method MA_S-CD_revised.The comparison between revised and unrevised results shows the effectiveness of MA_S-CD_revised.2.Community detection in multiplex networks concentrates on obtaining a robust partition by considering all information hidden in different layers.However,there are more algorithms designed for traditional networks and less for multiplex networks.Here,we propose an algorithm for finding communities in multiplex networks based on layer reduction.The basic idea is to turn community detection in multiplex networks into the problem of layer reduction.First,we improve a layer reduction algorithm,neighaggre.Second,we detect the communities by employing neighaggre.The results in real-life networks show that neighaggre can achieve higher value of relation entropy than other layer reduction algorithms.Besides,we apply LRCD-BNs on lots of artificial and real-life networks and the results show that LRCD-BNs does not have the advantage in terms of Q,it can obtain higher values of S.3.There are many measures related to community detection designed for bipartite networks but few works focus on comparing the performance of those measures through experiments.There are two ideas towards communities in bipartite networks.Therefore,those measures can be classified into two categories.Here,we want to compare those measures's performance on benchmark networks.Then,we design different algorithms for different classes of measures based on memetic algorithms.The comparison between different measures on lots of networks show that the relative best measure in most cases and advantages and disadvantages of each measure.