Analysis On Community Detection And Characteristics Of Online Social Network

With the rapid development of large-scale online social network applications, people found out social networks possess community structures. Community detection is helpful for comprehending evolution and organization of social networks. At present, community partitions only can be gained by heuristic process. How to detect community on large-scale online social network is still a hard problem. Understanding characteristics of community is benefit not only to improve application performance, but also to design better social networks.In this paper we have researched on community detection and characteristics of community on large-scale social networks. The data for our experiment are YouTube and Flickr. The main work of this paper consists of three parts. Firstly, we discovered community on YouTube with label propagation algorithm (LPA) from two different strategies. Our experiment proved LPA is an effective local updating algorithm. On the one hand, we modified LPA for considering about the degree of the node and its neighbor nodes, using game method for community partition. On the other hand, we adopted the idea of overlapping structure and regarded oscillated nodes as overlapping nodes. This strategy accelerates convergence speed of algorithm and gets more excellent partition result. Secondly, a method, derived from community aggregate, to detect community like Flickr is found out. The entire network is divided into ten sub-networks, and then we made community partition for each sub-graph with LPA respectively. A new network is built consists of communities as nodes in order to aggregate. We didn't stop community aggregation until none of links between communities existing. Thirdly, we analyzed characteristics of community of different strategies from three aspects: community size, the density of community and the largest community. Our experiment result has proved that community sizes satisfy power-law and medium-sized communities have much higher density. The characteristics of the largest community which was gained by game strategy are very similar to that of the largest community of original partition. In the end of the paper, we point out the directions of next step.