The Research On Influence Maximization Based On Community Closeness And Directed Acyclic Graph

With the rapid development of online social networks,information has entered the era of networking,which has led to constant changes in the way information is diffused.Influence maximization(IM)is a key issue in the research of information diffusion.It aims to find the most influential users in social networks to maximize their influence.Because this problem has important application value in marketing,advertising,public opinion warning and social stability,it has caused extensive research in academia in recent years.To solve the IM problem,the greedy algorithm was first proposed.The algorithm has high accuracy,but at the same time has a high time complexity and cannot be applied to a large-scale network.In order to solve the problem of high time complexity of traditional greedy algorithms,a large number of IM approximation algorithms and heuristic methods have been proposed.In recent years,some studies have used small-scale community structures to improve operating efficiency while ensuring accuracy.These algorithms usually use the influence of nodes in the community to approximate their influence on the entire network.However,existing community-based methods only consider the number of nodes in the community and ignore the connection density of the edges in the community,and these methods can only be applied to non-overlapping community structures.At present,most researches on influence maximization only focus on homogeneous information networks,that is,only one object type and one relationship type are included.Heterogeneous information networks containing multiple object types and multiple relationship types describe the real social network more accurately and meticulously,depict the subtle relationship between different types of objects,and express richer semantic information,thus contributing to the study of influence maximization.However,the structure of heterogeneous information networks is very complex,so the existing influence maximization algorithms cannot be applied to heterogeneous information networks directly.In order to solve the above problems,the work of this thesis mainly includes the following three aspects:(1)Aiming at the problem of influence maximization in homogeneous information networks,this thesis proposes a Community Closeness-based Influence Maximization Algorithm(CCIM)in homogeneous information networks.The algorithm considers the micro-level impact of point-to-point and the meso-level impact of the point on the community.When measuring the meso-level impact,it not only considers the impact within the community and the impact between communities,but also considers the number of nodes in the community and the connection density between nodes,so as to use the community structure to measure the influence of the nodes more accurately and maximize the influence.(2)Aiming at the problem of influence maximization in heterogeneous information networks,this thesis proposes a DAG-based Influence Maximization Algorithm(DAGIM)in heterogeneous information networks.This algorithm uses a large amount of information and strong expressive DAG structure to describe the complex relationship between different types of objects.It can effectively reduce the complexity of heterogeneous information networks while retaining the heterogeneity of information.The DAGIM algorithm first constructs a DAG structure for a node,and then measures the influence of the node based on the DAG structure and dynamically selects the most influential node to maximize the influence.(3)Verify the performance of the CCIM algorithm on one synthetic dataset and three real datasets,and verify the performance of the DAGIM algorithm on two real heterogeneous information network datasets.The CCIM algorithm experimental evaluation content includes verifying the effectiveness of the CCIM algorithm,exploring the effects of algorithm parameters on algorithm performance,and studying the impact of community weights and closeness on algorithm performance.The content of experimental evaluation of DAGIM algorithm includes verifying the effectiveness of DAGIM algorithm and analyzing the impact of complex DAG structure on the performance of DAGIM algorithm.The experimental results verify that the CCIM and DAGIM algorithms proposed in this paper are superior to the baseline algorithms.