| With the rapid development of Internet and Web2.0applications, many different patterns of online social networks become fashionable all over the world. These sites help people share and exchange information, as well as maintain their social relations on the Internet. Therefore, study the structure of communities in online social network is very meaningful and it has become a hotspot recently.Many algorithms for community discovery have been proposed, most of which have a high time complexity. An algorithm for community discovery based on label propagation has near linear time complexity. It propagates the labels of nodes iteratively in social network. Initially, every node will be assigned a unique label and update the label for each node in a random order. A node will choose a label randomly if there is more than one candidate label. This method will result in many fragmentary communities unsteadily. Therefore, we proposed an algorithm for community discovery based on label influence (LIB). It will select a set of nodes as seeds, each of which is assigned a unique label. A node will choose its label by calculating Label-Influence Value during propagating procedure. We have tested LIB algorithm in different datasets and the results show that the quality of communities discovered by LIB algorithm is improved with a better stability.Considering the dynamic behavior of users in online social networks, we proposed an algorithm for community discovery based on label influence vector (LIVB). In this algorithm, many kinds of entities are considered as nodes in the graph, such as posts, videos and comments. The edges are classified into static edge and dynamic edge. A node will update its label by calculating label influence vector. We designed two experiments and the results show that communities discovered by LFVB algorithm have more concentrative topics. The quality of the communities is improved and LIVB algorithm remains a near linear time complexity. |
PDF Full Text Request