Detecting Community In Very Large Social Network And Analysis It' Characteristics

With the development of Internet, online social networks develop rapidly and vast scale datasets of such networks are available for study. Community characteristics are found critical in understanding social activities, designing better application of communication and preventing the spread of harmful information. However, how to efficiently find community structures in large social networks is still a hard problem.This research targets on taking advantage of local information to find community in large-scale networks quickly and effectively. Based on the analysis of existing algorithms, we improve the LFM algorithm and analyze the community characteristics of some social networks with the modified algorithm. The main work of this paper consists of three parts. Firstly, some algorithms have been analyzed and obtained the most suitable algorithm. The LFM algorithm is based on the local optimization of a fitness function, it can find overlapping node. Secondly, we found two disadvantages of LFM, try a number of improved methods, and determine the best improvement. When there is noise node in the network, the original LFM cannot stop. When there is large-scale community, the time complexity of the original LFM is too high. We improve the LFM form three strategies, removing the edge between noise node and community, selecting the best node as the starting node that to found an sub graph as community, and removing the noise node as staring node and adding the node of highest CC as second node. To improve the time complexity, we determine everyone of community as starting node to detecting the sub-graph for finding community. Thirdly, we analyzed characteristics of community of different strategies in three aspects: community size, relationship between overlapping node and community size, and the density of community. Our experiment results have proved that community sizes satisfy Heavy-tailed distribution, and small communities more likely have overlapping node, but large community have litter or no overlapping node. The larger the community size, the higher intra-density. Intra-density and size within the community is positively related. Inter-density has a different performance in different network topologies; the fitness does not change with changes in the size of community. In the end of the paper, we point out the directions of next step.