Community Structure Mining And Community Influence Analysis In Social Networks

In the past decade, the technology of Web and Internet has undergone a rapid development and immense changes with the emergence of numerous interactive web applications and social networking sites such as Facebook, Twitter, Flickr, Sina Microblog and so on. The extensive user population is linked through some certain ways by the Social Networking Services whose representatives are web applications and social network sites, as a result, the social networks whose nodes represent the users and edges represent the relationships come into being. With the deepening of research in social networks, the researchers find that the users in a social network tend to be linked together and form a complex community structure through the different relationships among them. The community structure is able to reveal the hidden laws and user behavior characteristics in social networks which is one of the most important topological structure properties, therefore, the problem of community mining draws the great concern of academics. In addition, with the emergence of Social Commerce, many enterprises utilize the Facebook and Microblog platforms for marketing, promotion and expanding product sales channels through social interaction and user-generated content. The huge economic benefits gained by these enterprises attract many researchers to study the influence in social networks, but the main works remain on the user-level influence, and the community-level influence is rarely involved and concerned.In the face of increasing demand of practical application in the commercial field, this paper studies the two key issues in social network analysis, i.e. community structure mining and community influence analysis. The two issues are closely linked and are both related with community. At present, digging out the community structure accurately and evaluating the community influence effectively based on community structure still remain to be solved. For community structure mining problem, a multi-objective particle swarm optimization with decomposition is proposed and the multi-objective optimization model of community discovery is constructed through comparing the optimization objectives of different community discovery algorithms in social network. The proposed algorithm adopts the Tchebycheff method to decompose the multi-objective optimization problem into a number of scalar optimization sub-problems and uses Particle Swarm Optimization(PSO) to mining the community structure. Moreover, a novel local search based mutation strategy is put forward to improve the search efficiency and speed up convergence. The proposed algorithm overcomes the defects of single objective optimization methods. The experimental results on synthetic networks and real-world networks show that the proposed algorithm can mining the community structure rapidly and accurately and reveal the hierarchical community structure. For community influence analysis problem, a novel community influence analysis model is proposed in this paper through modeling the community-level influence based on the gained community structure, this model utilizes the Markov Chain to calculate the final community influence. Moreover, a simple but effective heuristic node-selection strategy is designed considering the community influence, and the influence spread experiments are conducted with the node set selected. We also compare the effect with some classical algorithms of influence maximization, and the results show the effectiveness of the node-selection strategy in influence spread and also prove the rationality of the proposed commumty influence analysis model.