Research On Community Detection Algorithms In Signed Networks

With the development of information technology,the analysis in complex networks has enjoyed a large increase in interest.Community structure is one of the most well-known characteristics in complex networks,visualizing community structure in complex networks has great significance for theoretical analysis and practical application.Signed networks are an extension of complex networks,which contain both positive edge attributes and negative edge attributes.Take social network as an instance,signed networks can flexibly describe the oppositional relationship between individuals in real life,such as like-dislike,agreement-disagreement,trust-distrust.In recent years,revealing the community structure in signed networks has become a research hotspot.Despite some progress and results have been achieved,identifying community structure in signed networks still poses challenges.We studied the community detection problem in signed networks and the main motivations and contributions of our research are as followsModularity maximization is one of the NP-complete problems,in which the main goal is to detect community structures in networks.However,there are some literatures pointed out that the modularity index presents the resolution limit issue.In other words,it fails to identify small modules which may remain hidden within the larger ones.To overcome this drawback,this thesis proposes a simple and effective iterated local search algorithm to solve the community detection problem in signed networks with the objective of maximizing the modularity density.During the iterative process,the random movements of a certain percent nodes is applied to achieve good perturbation effect,and then local search phase adopts two neighborhood operations to obtain good quality solution.Extensive experiments have been conducted on synthetic and real-world networks.The statistical analyses demonstrate that the proposed algorithm can provide high-quality solutions compared to the state-of-the-art algorithms.Moreover,the modularity density demonstrates the good ability to detect multi-resolution communitiesLabel propagation algorithm(LPA)is a simple community detection algorithm with near linear time.However,LPA might generate unstable results due to its randomness shortcomings.To improve the stability and make LPA applicable to detect community structure in signed networks.In this paper,we propose an improved label propagation algorithm based on graph,named ILPAG Firstly,this algorithm adopts a specific node update sequence based on structural similarity.Secondly,the iterative process of label propagation consists of two phases,in the first phase,each node updates its label to the neighbor label that brings the largest gain value.During the second phase,the collection of nodes with same label is treated as a super node,and updating each super node's label at the same time.The experiment results demonstrate that the proposed ILPAG shows good performance on stability and effectively improves the quality of community detection compared with other algorithms in the literature.