Research On Three Types Of Cluster Discovery Algorithms In Social Networks

In the study of social networks, the study of influence propagation problem occupies an important position, and it has been the focus of the research. But most existing works neglected the fact that the location information can play an important role in influence propagation problem of social networks.Many real-world applications such as location-aware word-of-mouth marketing have location-aware requirement. Therefore, the article introduces geographical location factor into social networks, and respectively studies minimizing seed set selection problem, profit maximization seed set selection problem, and influential event organizers selection problem. We make the following contributions.1. We introduce geographical location factor into a traditional minimizing seed set selection problem(J-MIN-Seed), and propose a minimizing seed set selection algorithm problemin the location-aware social network. We study the problem deeply, and prove that the problem is NP-hard, and propose a naive greedy algorithm MS-Greedy. Although MS-Greedy has approximate guarantee, its computation is rather large. In order to meet the needs of online query, we then propose another two effective algorithms Bound-based and Partition-Assembly-based. Experimental results on real data show that our algorithms can solve the location-awareJ-MIN-Seed problem effectively.2. We introduce geographical location factor into a traditional profit maximization problem, and propose a profit maximization seed set selection algorithm problemin the location-aware social network. We integrate value and price factors with the classic IC model, and proposea new IC-V model. We prove that the problem under IC-V model is NP-hard. We propose a greedy algorithm Greedy, and integrate three price strategies with algorithm Greedy, then propose three algorithms to solve this article problem. Finally, makea number of experiments on real datasets verify the efficiency of the three algorithms.3. We introduce geographical location factor into a traditional influential event organizers selection problem, and propose an influential event organizers selection algorithm problemin the location-aware social network. First, we detail the importance of the prolem by exampling, formalize the problem and prove that it is NP-hard.Second, based on the previous work, we use two existinggreedy algorithms to solve the problem.Because the greedy algorithm would miss results, we further propose two approximate- on algorithms.Finally, makea number of experiments on real datasets, compare above four algorithms, and prove the effectiveness and efficiency of the algorithm.