A Conical Area Evolutionary Algorithm For Multi-objective Community Detection From Social Networks

The study of social networks(SNs)is a hot topic in recent years.In the real world,objects and the relationships among them can be represented by various SNs.For example,friend network,metabolic network,etc.In SNs,nodes denote the objects of a system,and edges represent the interactions among these objects.With the development of research on SNs,researchers find that most SNs have characteristic of community structure,that is,SNs can be divided into a certain number of communities with different size.In most situations,the higher connection density between two nodes implies a higher possibility they lie in the same community.Specifically,a social network where there exists both positive and negative edges is called a signed social network.Moreover,if some communities share nodes with each other,the social network has overlapping communities.Although many community detection(CD)algorithms have been proposed,most of them focus on unsigned and non-overlapping community SNs.Obviously,the signed SNs and SNs with overlapping communities represent networks of the real world more effectively and realistic.In the signed SNs,the division of the community structure takes not only the connection density but also the properties of the connection into account.In SNs with overlapping community,finding an effective represent mechanism of overlapping nodes is a difficult problem.Considering the noise in the real world and in the hope of detecting the signed SNs and SNs with overlapping communities more effectively and efficiently,this paper completes the following research to design CD algorithms from the above two types of SNs.(1)The signed similarity and the inherent weighted connection among nodes are hybrid to defined the connection strength of the node for CD from signed SNs.Foremost,the node connection strength overcomes the drawback that the signed similarity is not suitable for the sparse network and the node weighted connection is easily disturbed by noise.Based on the connection strength of node,the community tightness is proposed to generate a community-structured population in initialization and plays the role in guiding whether the gene is mutated during the evolution process.At last,the CD algorithm from signed SNs is implemented combining with more efficient multi-objective optimization algorithm CAEA.(2)Combined with CAEA and maximal clique representation for overlapping CD from SNs.Using the idea of decomposition,MOEA/D decomposes a multi-objective optimization problem into multiple single-objective optimization sub-problems and optimizes these subproblems simultaneously through population evolution.Unlike MOEA/D,CAEA not only decomposes multi-objective optimization problems into sub-problems of multiple sizes,but also assigns each sub-question a unique decision sub-area.In addition,each sub-question uses a cone-shaped area indicator as its scalar target to find a local non-dominated solution in its associated decision subset.Practice shows that the CAEA performs better results and higher efficiency.Furthermore,the phenomenon that maximal clique are allowed to share the same nodes meets the intrinsic property of the overlapping community structure.Since it is time-consuming to decode indirect representation scheme during the evolution process,we apply the clique and the maximal clique to overlapping CD from SNs effectively to overcome this drawback.Foremost,we find all the largest cliques in the preprocessing stage.Afterwards,we set these cliques as new nodes,and then use the simple direct representation mechanism for overlapping CD.At the same time,aiming at the problem that the evolution of the objective function is biased toward the large-scale target due to the different scales of the objective function,and consequently the loss of population diversity,the feature scaling of the objective function is designed in this paper.(3)The performance of the two algorithms is evaluated on two types of networks comprehensively,which call real-world networks and synthetic networks(i.e.,networks with noise).Among them,synthetic networks are a combination of various parameters to carry out systematic experiments.These experiments include large-scale,high-noise tests of two algorithms.Moreover,our algorithms are compared with excellent MEAs-SN,louvain and MCMOEA systematically to verify the effectiveness and efficiency on CD problems.Experimental results on both synthetic networks and real-world networks indicate that,the two multi-objective CD algorithms based on conical area evolution algorithm designed in this paper can not only obtain excellent detection results in the corresponding types of social network community detection but also show higher computational efficiency and robustness.