Measuring Influential Nodes And Maximizing Spreading Influence In Complex Networks

Measuring the most influential nodes and maximizing influence in complex networks have received significant attention from the field of network science in recent years,which has the considerable significance for controlling the outbreak of epidemics,enhancing the effect of advertisements,optimizing information dissemination,identifying the influential individual in social networks.At present,the measure of influential nodes mainly locates nodes that play an important role in information dissemination through the network topology such as neighborhood,location and path.Many classical centrality methods have been widely applied for identifying influential nodes,such as the degree centrality,betweenness centrality,closeness centrality,Katz centrality,k-shell centrality,etc.However,these methods are mostly independent of each other,and ignore the role of information dissemination on identifying influential nodes.In view of the above discussion,this paper combines the network topology and propagation dynamics,then proposes the centrality methods for evaluating influential nodes from two aspects:network propagation and epidemics control.Meanwhile,we further study the influence maximization algorithm with the coverage and discount strategy,and effectively solve the problem of selecting decentralized seeds.The main contributions of this paper are summarized as follows:(1)We put forward a new neighborhood core centrality method based on information entropy of path diversity from the perspective of information propagation.Different from the k-shell decomposition that selects nodes in the highest-order shell as the seeds,this method introduces the conception of path diversity into the traditional k-shell decomposition to identify and to measure influential nodes,while integrating the nodes' position and local neighborhood information with the propagation dynamics.The experimental results in Jazz,C.elegans,Email show that,compared with other methods like degree centrality,betweenness centrality,closeness centrality,k-shell centrality and neighborhood core centrality,the proposed method can identify influential nodes more accurately and rank influential nodes more finely.(2)We propose a betweenness centrality and closeness centrality methods based on intermediate hops from the perspective of epidemics control.Firstly,a discrete propagation model without immune strategy is put forward.This model can describe the dynamic evolution of epidemics spreading and the microscopic state of nodes.Experimental results in 1000-node scale of the artificial scale-free network and artificial small world network show that,compared with degree centrality,the nodes with betweenness centrality and closeness centrality can more effectively quarantine the final affected scale and accelerate spreading speed,respectively.Meanwhile,community structures of networks will also play a certain negative impact for global diffusion across communities.(3)We propose a new influence maximization algorithm based on 2-step neighborhood and overlapping effect.On the basis of independent cascade model,the concept of limited propagation distance is introduced and a limited distance independent cascade model(LDIC)that can effectively simulate the real information propagation is proposed.This model reasonably explained the validity of adopting 2-step neighborhood to locate seeds.Therefore,a neighborhood influence discount heuristic algorithm(NIDH)based on 2-step neighborhood is put forward.It performs discount calculation for nodes within 2 steps after selecting a seed in each round;as a result,the spreading influences of surrounding nodes are weakened and the seeds are decentralized as much as possible.Moreover,NIDH considers the propagation probability of each edge to calculate the spreading influences.Experimental results in two directed networks(NetConmm and Celegan)show that,NIDH algorithm can more accurately locate seeds with larger spreading ability.(4)We propose a new influence maximization algorithm based on neighborhood coreness centrality.Using this method,a node in the high-order shell with the largest neighborhood coreness and an uncovered status will be selected as the seed in each round.In addition,the neighbors within the same shell layer of this seed will be covered,and the neighborhood coreness of the neighbors outside the shell layer will be discounted in the subsequent round.Therefore,a neighborhood coreness cover and discount heuristic algorithm(NCCDH)to identify a set of influential and decentralized seeds is put forward.NCCDH utilizes the characteristics of high-order shell nodes that are closely clustered with each other,which not only prevent many nodes with overlapping spheres in the high-order shell from being selected as the seeds but also give a reasonable assessment for that nodes with large degree in the periphery of the network.Experimental results in large scale networks including Hamsterster,Ca-GrQc and COND-MAT show that,with increasing spreading probability,the NCCDH outperforms other benchmarks in terms of the affected scale and spreading speed under the SIR and SI models.More importantly,the time complexity of this approach is superior.