Research On Information Propagation Algorithms In Social Networks

Recently, with the rapid development of the network and social network sites, such as Facebook and Twitter, social networks have become a platform for people to communicate and share information. It has many features, such as convenience and wide-ranging of influence. Companies can promote products effectively and government can block rumors on this platform. In the process of information propagation in social networks, such as product promotion, choosing less users with large influence capacity to spread messages not only can advertise product fast, but also reduce the cost, which can bring the profit maximize. Based on t his consideration, the thesis focuses on analyzing the relationship between the cost of spreading the message and the influence coverage in social networks.The thesis aims to solve two problems: Influence Maximization(IM) problem and Minimum Cost Information Dissemination(MCID) problem. The MCID problem is proposed on the basis of IM problem after many previous researches. To the MCID problem, this paper proposes a cost function. The cost concludes two aspects: First, the cost means the number of source nodes, the MCID problem is to find a minimum set of source nodes, the influence coverage reaches the requirement; Second, the cost means the payment the set of source nodes needs, the MCID problem is to find a set of source nodes with the minimum payment s, the influence coverage reaches the requirement.To the IM problem, we analyze and summarize the existed influence maximization algorithms. The thesis presents an influence maximization algorithm based on HISS(h-hop Independent Set Scheme, HISS)(HISS-IM), It considers the combined influence power of the whole set of the source nodes. The hops between these nodes in this set are at least h+1, which aimed at avoiding the overlapped influence between source nodes.To the MCID problem, this thesis first presents a minimum cost node selection algorithm based on HISS(HISS-MCID). It first chooses candidates of source nodes combined with the weight and the cost of nodes. Then the thesis proposes an evaluation function to verify the influence of nodes and get the final source nodes from the candidates. Meanwhile, the thesis designs a node selection algorithm based on Information Propagation Model(IPMA) to solve the MCID problem. When selecting nodes, it considers the cost of nodes and uses the information propagation model to select the source nodes. Finally, combined with the centrality of social networks, the thesis designs another node selection algorithm based on the ratio of nodes' weight and cost. When selecting nodes, it chooses the node with high ratio.This thesis verified the performance of our approach with real-world datasets and compared with the typical IM algorithms. And we apply the Independent Cascade Model and Weight Cascade Model to model the process of information propagation. In total, to the IM problem, the proposed approach HISS-IM can guarantee the performance is better than other algorithms with different influence probabilities between users. With the same number of source nodes, the influence coverage of HISS-IM approach is higher, especially in the requirement of higher influence coverage. To MCID problem with linear cost function, the difference of performance between the proposed algorithms is not obvious. Within the same influence coverage, the IPMA algorithm needs less cost than other algorithms. To MCID problem with constant cost function, the HISS-MCID approach is better with different influence probabilities between users. With the same influence coverage, it needs less source nodes.