Influence Propogation And Influence Maximization In Online Social Networks

With the increasing popularity of various Internet applications, such as social network sits, blog, Micro blog and so on, all kinds of online social networks come into being. In social network, users act as receiver, maker and disseminator of information, which accelerates the spread of information. Now, social networks have become a huge dissemination platform, allowing information to impact on a large population in a short period of time. However, to fully utilize these social networks as information dissemination platforms, two challenges, namely, influence diffusion model and influence maximization, have to be met. The former is to model the diffusion process of information in social networks, and the latter is the method of finding those influential individuals efficiently in a large-scale social network.In the context of the wide applications of online social networks, this dissertation conducts in-depth research on the above-mentioned two aspects, influence diffusion model and influence maximization.First of all, the community detection is addressed in the paper. Based on the locality of information diffusion in social networks, a new community detection algorithm named DC_ID is proposed. The algorithm consists of two stages, partition and combination. During the first stage, all nodes’ influence in the network is estimated, and then the most influential non-community node is chosen as the seed. Its influence is expanded along the diffusion paths layer by layer. Finally, the local community with the seed node as it core will be found. During the second stage, the closeness of two local communities will be evaluated with their “combination entropy”. When the combination entropy of any two communities is higher than some predefined threshold, they will be merged into one.In the next place, aiming at the inefficiency of the influence maximization algorithm, based on the community structure of a social network, a cooperative game theoretic algorithm(CGINA) for influence maximization problem is proposed. In CGINA, the information diffusion is considered to be a cooperative game with transferable utility. With the Shapley value in game theory, the number of key nodes for each community is allocated. Finally, key nodes will be mined in these communities. Empirical studies show that the algorithm is efficient and powerful.Once again, the influence maximization based on nodes’ preference is studied, based on the different preference of the nodes in network for the information with different themes, a two-stage L_GAUP algorithm for influence maximization is proposed. In the first stage, based on the node’s preference for the information theme, a sub-graph can be got. Comparing with the other nodes, nodes in the sub-graph have higher preference values. In the second stage, based on the greedy strategy, the top-k influential nods will be mined in the sub-graph. Experimental results show that L_GAUP is more efficient and powerful than other benchmark algorithms.Then, taking into account the phenomenon that negative opinions may emerge and propagate in social networks, a new model – linear threshold model with negative opinions(LTN) is proposed in this study. Subsequently, some properties of the LTN model, such as monotonicity and sub-modularity have been proved. With these two properties, a greedy approximate algorithm with a ratio of(1-1/e) and three improved algorithms, LTN_New Greedy, LTN_CELF and LTN_Mixed Greedy for influence maximization on the LTN model have been proposed.In the end, based on a competitive influence diffusion model-COICM(Campaign-Oblivious Independent Cascade Model, COICM), the IBM(influence blocking maximization, IBM) problem has been studied. To improve the efficiency of the IBM algorithm, based on the locality of information diffusion, a community-based IMB algorithm CB_IBM has been proposed.