Study On The Overlapping Community Detection Algorithm In Online Social Network And Application

Research shows that the network has become the form of many systems that the real world exists.Generally, most real networks have a common feature, namely community structure. Among many research directions for online social networks, there is a research direction that has greatful commercial value which named overlapping communitiy detect. The concept of overlapping community is different from network community that graph theory proposed. The main differentiator in overlapping communities is the node can belong to different communities. In online social networks (OSN), a node is a real person, someone has a multi-faceted, according to the different sides, one node can belong to different communities. Thus the concept of overlapping community is more suitable for us to study in OSN.This thesis presents two overlapping communities detcetion algorithm for online social network. The target of this thesis is OSN like Twitter, Sina Weibo, Douban and so on. The two algoritm based on two properties of the social network:one is based on the dynamic attributes called Dynamic Attribute Clustering Algorithm(DACA), the other is based on the static properties of social network, called Interest based LPA(IbLPA).The general idea of DACA is as followed:first, divides the whole network into two parts, the dynamic attribute node holds 10% by pre attention, and the rest represents the normal user nodes. Thereafter in accordance with concern the relationship between the average user node clustering dynamic attribute group. Finalize ascertains the results of the overlapping communities division based on the dynamic attributes clustering results. Because of the relationship of follow can be dynamically modified by the nodes in the network, the links between nodes are dynamic, so the algorithm is based on dynamic attributes.The Interest based Label Propagation Algorithm comes from the thought of label propagation algorithm. Based on the use of community overlap propagation algorithm (COPRA), the coefficient to determine whether the node should preserve the label, which can discover overlapping communities. The difference is in the label propagation process is no longer use the " reciprocal factor" to randomly determine whether the label should keep the labels, using the Hop Attenuation and Node Preference algorithm (HANP) to make every label has the ability to characterize the spread of the label, keep each node dissemination process has the ability to spread all tags received. The target of label propagation is a unique concept comes from online social network named "personal label", after a similar dynamic properties clustering process of reducing the total number of tags spread, greatly strengthened the semantic of label propagation algorithm.Two algorithms proposed in this thesis are both from a sociological point, triadic closures, rather than with the morphological characteristics of online social networks. This thesis presents a method determine the accuracy by removing the existing links of the community to let the results of overlapping communities to find a way to rebuild the link. Experiments show that compared to the traditional overlapping community detect algoritm based on complex network or graph theory, although there is a slight difference on the modularity measure, but found the accuracy of the community detected has been enhanced.