Community Discovery On Social Networks Based On Label Propagation

Recently,the development of social network-based Web 2.0 applications has been becoming more and more popular.The typical social network applications include Facebook,Twitter,Xinlang Weibo,Wechat,through which people no longer need to communicate with each other face to face.Hence,the time and space distance between people are greatly shortened and the communication cost is also greatly reduced.In social network applications,research on online virtual society is not only of great commercial value,but also important in academic research.Discovering communities on social network can be viewed as a clustering problem in general.However,social network has the characteristics of complex networks,such as small world,scale free,etc.It also has its own characteristics of large scale and dynamic variation,which make detecting communities and tracing community evolution quite different from normal clustering.Therefore,it is in urgent need to study new methods to solve problems in community discovery on social network.There have been a lot of papers published on discovering communities in static social network so far.However,in real world,there may be billions of vertices and edges in social networks,while communities are often complex overlapping and always changing.The static community discovering algorithms are incapable of solving these problems.In this paper,a series of research has been carried out on discovering complex communities in social networks based on label propagation.The main contents include:(1)Vertices in social networks could belong to more than one community,which blur the boundaries of communities.In order to solve the problem,we describe the similarity of vertices with the integration of the grey relational analysis and the Jaccard similarity.Then,new automatic label updating strategy based on the ankle value is proposed to improve the standard LPA.Finally,parallel steps based on the MapReduce model are developed to realize parallel community discovery on large social networks.(2)The scale free characteristic of social network leads to different impacts on the label propagation progress of different vertices.In order to solve the problem,the influence model based on vertices and labels is proposed,and combined with the parallel steps of the standard LPA based on the MapReduce model.New improved label propagation algorithms are built upon the models to find overlapping communities on large social networks.(3)The characteristic of dynamic variation of the social network makes the communities structures change frequently as time goes by.In order to adapt to the dynamics of social network,a new dynamic community disco-very algorithm is proposed for community detection based on label propagation and incremental dynamic community discovery method,by introducing a new attenuation strategy,a static community discovery method with linear time complexity and designing a new community stability index.(4)The evolution of social network has the characteristic of locality.In order to handle the local variation phenomenon,the label propagation progress is integrated with the label ranking strategy to discover communities on social networks.A new local label updating strategy with linear time complexity is developed to consider the local variations of the community structures,such as the emergence and evaporation of vertices and edges.Moreover,the Jaccard similarity and the termination criterion in the COPRA algorithm are used to improve the performance with fewer interactions.