Several Influence Maximization Problems In Social Networks

Network science is an emerging discipline that originated in the late twentieth century.It utilizes systems science,complexity science,and graph theory to characterize the interactive relationships among different components within complex systems.Social networks are characterized by the relationships between individual participants,which are represented as nodes and edges within a graph,such as cooperation between individuals or competition between companies.The Influence Maximization(IM)problem aims to identifying a group of nodes that can maximize the spread of influence across a network.The identification of such critical nodes holds significant potential for various scenarios,such as viral marketing,epidemic prevention,and prevention of cascading(e.g.,power grid,communication network)failures.As social networks have evolved to encompass larger scale,more types,wider scope,and increasingly complex structures,IM problems have diversified and emerged as a significant field of research.This paper explores three types of IM problems based on different semantic backgrounds,including classical IM,robust IM(RIM)under uncertain contexts,and influence minimization: rumor blocking(RB)problems.Below are detailed descriptions and innovations.In the Classic IM problem,conventional algorithms for identifying influential nodes encounter two significant challenges: the curse of scales and generalization issues.This study discovers that employing snapshots based on the independent cascade(IC)model can effectively integrates propagation parameters and network structure.Based on this finding,a more adaptive algorithm called the Probability-Driven Structure-Aware(PDSA)is proposed,which also considers the elimination of the influence “overlap effect” during solving process.On the other hand,a parameter estimation method utilizing centrality measurements(e.g.,degree,betweenness,closeness,and Page Rank centrality)is proposed,which assigns higher probabilities of activating nodes with low centrality to nodes with high centrality.Experiments conducted on six benchmark networks with varying topologies demonstrate that: 1)the PDSA algorithm outperforms other state-of-the-art algorithms across all combinations of network topologies and parameters;2)the PDSA algorithm maintains an acceptable polynomial time complexity while ensuring its effectiveness.The primary focus of the Robust IM problem lies in the modeling and computation of IM under uncertain parameter settings.This problem encounters challenges in establishing robust optimal objective functions and efficient solving approaches.This study introduces an objective function based on the computation of the Shapley value,a concept derived from game theory.The objective is to identify nodes that exhibit the best propagation effect under the worst parameter conditions(i.e.,minimizing the Shapley value).Furthermore,a singleprogram multi-data parallel computing framework is introduced to improve efficiency during parameter space exploration.Finally,the study proposes the Robust Sha Pley value-based Influential Node(RSPIN)algorithm.Experiments conducted on nine benchmark networks demonstrate that: 1)the worst-case scenario occurs when the edge probability is set to the endpoint of the perturbation interval;2)the proposed RSPIN algorithm outperforms other state-of-the-art methods in selecting seed nodes under the worst-case scenario;3)the introduction of the parallel framework reduces the estimation time of robust Shapley value to 1/6on average.The RB problem primarily focuses on minimizing the dissemination of negative effects,such as rumors.Due to the significant disruptions caused to network topologies by directly blocking nodes or edges,an alternative approach is adopted in this study,which involves introducing positive information(e.g.,truth)to combat rumors.However,previous research efforts in characterizing competitive propagation scenarios have been relatively limited and incomplete,lacking appropriate solving algorithms that accommodate the characteristics of rumor propagation.Therefore,this study proposes a competitive independent cascade model that takes into account conformity,information delay,and information authority comprehensively.Additionally,two innovative algorithms,namely the Conformity-aware Demand Degree(CDD)algorithm and the Rumor-aware Betweenness First(RBF)algorithm,are introduced.Experiments conducted on seven benchmark networks demonstrate that: 1)the proposed algorithms outperform other state-of-the-art methods in terms of containment effect and running speed;2)authoritative truth information plays a critical role in competing with rumors,relying on these truth-seeds will generate negative feedback when their credibility ratio is less than a specific threshold.