Research Of Community Detection In Large Social Network

Because of scientific and social development,social network is becoming more and more common in people's lives.The social networks became larger,and more diversity.The existing community detection algorithms are only made for the classic,undirected social network,and does not take old and new features of networks into account,which will make the algorithm inaccurate.In order to solve this problem,this paper combines community detection algorithms with node's community choice behavior undirected social network and node's following behavior in directed social network and presents two new community discovery algorithms to improve community discovery algorithm applicability in different social networks.We talk about the research background and value of community detection at the beginning of the first chapter,and then introduce the current research situation about community detection algorithms in rest of chapter 1 and chapter 2.After that,we proposed a novel algorithm,which is based on label propagation mechanism and take the community choosing behavior of vertices into consideration,called Attraction Label Propagation Algorithm.The ALPA algorithm can improve both the stability and quality of the result community partition when compared with traditional algorithms such as RAK and LPAm.We also realized the difference of edges between directed social networks and undirected social networks.There are more kinds of connect status,more kinds of node similarities and more complex community structures in directed social networks such as Twitter.We looked into Twitter networks and define a new kind of community that is common in directed social networks,namely directional community.Different from nondirectional Radicchi community,vertices in the same directional community aren't always similar with each other,but they always share the same information and interesting points.We proposed Directional Label Propagation Algorithm to detect directional community structure.The DLPA can calculate a more reasonable influence score of the vertices in a directed network with Directional Influence method,and sort the vertices sequence in order of the influence score.Then it detects directional community structure through a label propagation mechanism with a limit of propagation direction.DLPA algorithm can apply to both directed social networks and undirected social network.When handling undirected social networks,it has similar performance with ALPA and Leung algorithm,when handling directed social networks,it can solve the problem that ALPA and other traditional community discovery algorithm will produce a lot of meaningless nondirectional communities fairly well.