Influence Maximization Of Social Networks Based On Triadic Closure

Social networks(Weibo and Twitter,etc.)play an essential role in daily communication among people.Information and ideas could be spread widely in a shorttime in a social network,which presents new opportunities for enabling large-scale and prevalent viral marketing.The influence maximization problem is an important research area in social networks,which aims to select the most influential nodes(i.e.,seed nodes)to maximize the number of influenced nodes(called influence spread)after the propagation reaches a steady state in a social network.The propagation model is the basis of influence maximization.However,the current traditional independent cascade models usually set the propagation probability to a fixed value or the reciprocal of the degree of the influenced node,which is too ideal to distinguish the difference of individual influence well.Besides,most existing heuristic influence maximization algorithms need to update the expected influence of all remaining nodes in the seed selection process,which is inefficient to update and not suitable for large-scale social networks.In addition,the existing adaptive influence maximization based on the partial feedback need to obtain the state information of all neighbor nodes within a given number of hops of the target node,which is difficult to implement in large-scale networks.To address the above problems,the following research work is carried out in this thesis.(1)The widely used IC models share the same propagation probability within a large number of adjacent node pairs,which is too ideal.To solve this problem,this thesis first proposes a novel edge propagation probability calculation method based on triadic closure weighting and derives a Triadic Closure based Independent Cascade model.The model utilizes the triadic closure structure to assign the corresponding propagation probability to each node pair.Experimental results show that the model can achieve at least 85%,or even up to 97%,of the propagation probability of discrimination.Thus,our proposed model could reflect the differences of individuals propagation abilities and easily capture influential nodes that should be identified.(2)Most heuristic algorithms for influence maximization need to update the expected influence of all remaining nodes in the seed selection process,resulting in high computation cost.To address this problem,this thesis further proposes heuristic influence maximization algorithm named Triadic Closure based Influence Maximization.Based on the proposed model,the algorithm evaluates the influence expectation of a node by integrating the triadic closure weighted propagation probability and the triadic closure weighted degree.Especially,an efficient influence update strategy is also proposed.In the seed selection process,only the most influential node that has not been updated in the current round needs to be updated,which significantly improves the update efficiency.Besides,we further provide theoretical proofs to guarantee the correctness of this updating strategy.Experimental results show that the proposed algorithm can significantly reduce the complexity through an efficient updating strategy with a comparable influence spread to the approximation IM algorithms.Besides,the proposed algorithm also exhibits stable performance under other IC models including UIC and WIC,exhibiting good stability and generality.(3)The adaptive influence maximization based on partial feedback needs to obtain the state information of all neighboring nodes within a given number of hops of the target node.To address this problem,this thesis proposes Triadic Closure and Probabilistic Speculation based Adaptive Influence Maximization.The algorithm is based on the general partial feedback model,which only needs to obtain the state information of some neighbor nodes within a given number of hops,and the algorithm reasonably speculates the state of unknown neighbor nodes within a given number of hops based on this known information,which effectively makes up for the shortage of feedback information.In addition,the algorithm also considers the problem of decreasing closeness of the residual network of the adaptive IM algorithm,and introduces a "triadic closure" structure to calculate the ternary closure weighted degree value that represents the closeness between nodes,so that for the gradually sparse network,the seed node with a larger influence range can be selected in each round.The experimental results show that the proposed adaptive IM algorithm outperforms other adaptive IM algorithms under general partial feedback,and the influence range gradually approaches that of the adaptive IM algorithm under full feedback as the degree of feedback increases.Thus,the adaptive IM algorithm proposed can balance the cost of feedback information and the performance of the influence range.The ablation experiments also demonstrate the effectiveness of the unknown node state speculation described in this thesis.The thesis has a total of 30 figures,15 tables,and 85 references.