Research On The Measurement And Maximization Of The Influence Of Social Network Nodes

With the popularity of the Internet and Web 2.0,Online Social Networks have replaced the traditional media as the most important medium of information dissemination and the main platform for mass communication.The abilities of people to transmit and obtain information have been unprecedentedly improved.The information rapidly diffuses through the interactions between users and dynamically evolves under the influence of users,which forms public opinions that cannot be ignored.The important nodes have great influence on the structure and function of a network.We can better understand the characteristics of complex systems and control them by mining the influential nodes.Additionally,influence analysis has important applications in the fields of social network information transmission,link prediction,public health,incident detection and advertising.Researchers have carried out a tremendous amount of work and achieved fruitful results.However,with the expansion of social networks,the explosive growth of users and the convergence of heterogeneous networks,many new challenges have come to the research field.(1)With the explosion of amount of data,the efficiency of algorithms needs to be improved.Since well performing methods based on global attributes of a network will become very time consuming.They are not applicable to large social networks.Algorithms based on local attributes perform well at finding cluster center nodes but are not efficient enough in mining nodes acting as “bridge”.The problem of how to identify the appropriate influence factors and how to accurately and efficiently recognize the most influential nodes should be addressed.(2)Traditionally,existing algorithms apply a multivariate function with variables that are node influence measures.As the function is fixed,the universalities of these algorithms are limited.Learning to rank can be used to measure node influence.The new universal node influence algorithms based on learning to rank should be researched.(3)In social networks,some relations between users are friendly,but others are hostile.The unbalanced edges of social networks play an important role in node influence.The existing research results lack any analysis of the interaction mechanism between the node influence and unbalanced edges.Therefore,research on computing structure balance and mining unbalanced edges should be performed.The effects of unbalanced edges on the node influence need to be further discussed.(4)The information propagation rate between users is the result of the interaction of many factors,such as the synergy between users,the status and behavior of the spreaders and the distance between the seed node and neighboring nodes.The existing research seldomly consider the factors above,and so it is urgent to develop a spreading model that is more in line with the actual information diffusion.In a large network,how to design an efficient influence maximization algorithm based on the new propagation model,is also an important challenge for researchers.Supported by the National Natural Science Foundation of China,this paper conducts an indepth study on the node influence measurement and influence maximization based on theme of influence spreading in social networks.First,we analyzed the features of the influential nodes and discuss the correlation between the clustering coefficient and node influence.Then,we propose a novel measure,which is called the normalized local centrality(NLC),to measure the node influence by utilizing both the local centrality of a node and its local clustering coefficient.Second,based on the above NLC measure,we propose a multi-index measure based on the Listwise approach and the network representation.Third,we research the structure balance of signed networks and proposed a new cultural algorithm named the CA-SNB to compute the degree of unbalance of signed networks.Then,we discuss the relationship between the node influence and unbalanced edges.The results provide theoretical support for the application of metrics from unsigned social networks to signed networks.Last,we proposed a novel diffusion model called the synergism-based three-step cascade model(TSSCM)and develop an algorithm for solving the Influence maximization problem with the TSSCM.The main research contents and innovations of this paper are listed as follows.(1)We propose a novel measure based on normalized local structural attributes,which is called the normalized local centrality.To address the challenge of the exponential growth of networks,we analyzed the features of influential nodes and discussed the correlation between the clustering coefficient and node influence.Then we proposed a novel measure,which is called the normalized local centrality(NLC),to measure the node influence by utilizing both the local centrality of a node and its local clustering coefficient.Unlike existing influence measures based on a local network,the NLC synthetically considers the topological information of the local network around a node and the influence feedback of the nearest neighboring nodes of the node.Specifically,the local network around a node consists of the node and its four-order neighbors.The topological information of a local network includes the number of nodes in the network and the topological connection between nodes.The influence feedback of the nearest neighboring node is reflected in the weighted sum of the relative influence of the nearest neighbor node.To avoid the introduction of new parameters,a normalized function was designed to normalize the indexes of the local network,which remedied the additional costs that are incurred for the parameter determination of some measures,such as the LSC.We compared the performance of the NLC in the susceptible–infected–recovered(SIR)model with the performance of the DC,BC,CC,KS,LC and LSC.The experimental results of the eight networks demonstrated that the performance of the NLC is superior to that of the other six measures with little increase in the computational time.(2)We propose a multi-index measure based on the Listwise approach and the network representation.The existing multi-index node influence measures combined indexes by using their weighted sums or a function of several variables.On the one hand this operation would introduce new parameters and increase the complexity of the method.On the other hand,it is difficult to guarantee that the algorithm is suitable for all kinds of social networks with fixed function patterns.Based on all the above,we propose a multi-index measure based on the Listwise approach and the network representation.The measure includes three node influence metrics: the NLC that was proposed in the previous chapter to mine the features of the local network,the BIGCLAM model to find the nodes that function as “bridges” and the local clustering coefficient to reflect the importance of neighbors.To effectively fuse the three metrics,we introduced the Listwise approach to learning to rank.We take the above three measures as learning features,obtain the final parameter values through cross-verification and construct a multi-index measurement model.The experimental results showed that the model can obtain a more accurate sequence of node influence.Compared with other algorithms,the top-k nodes that are sorted by the model can lead to more extensive influence propagation.Our algorithm has stronger practicability and is robust when simulating the noise data set of a Sybil attack.(3)We propose a new cultural algorithm named the CA-SNB to compute the degree of unbalance of signed networks and analyze the relationship between the unbalanced edges and node influence.The friendly and antagonistic relationship between nodes in social networks is a factor that cannot be ignored in the analysis of nodes influence.We research the structural balance of signed networks and propose a new cultural algorithm named the CA-SNB to compute the degree of unbalance of signed networks.We address the network structural balance problem with an optimization view.The objective function was constructed based on the Ising spin glass model.A novel culture algorithm named the CA-SNB was proposed to solve the optimization problem.The CA-SNB is a double layer algorithm including the population space and the belief space.The evolution of the population space and belief space is based on the Genetic Algorithm and greedy strategy respectively.The belief space of the CA-SNB obtains the experience knowledge from the evolution of the population,and feedback is used to guide the population's evolution,which improves the search efficiency and accelerates the convergence of the evolution.Experiments on social and biological networks showed the excellent effectiveness and efficiency of the proposed method.Then,we create a network with edges that obey the Bernoulli distribution and convinced the conclusion “The signed networks move toward structural balance”.We discuss the relationship between the node influence and unbalanced edges.This work provides a method for the research of many key problems,such as the application of the influence measure from the unsigned network to the signed network,the node influence measurement based on the signed network,social network recommendations and public opinion analysis.(4)We propose a novel diffusion model called the synergism-based three-step cascade model(TSSCM)and develop an algorithm for solving the influence maximization problem with the TSSCM.The synergism of neighboring nodes plays an important role in information propagation dynamics.Many studies have found that synergism enhances the transmission probability and promotes explosive spreading.Furthermore,some real information diffusion findings have supported the hypothesis that influence gradually dissipates and ceases to have a noticeable effect on people beyond the social frontier of three degrees of separation,which is called intrinsic decay.Based on the above,we proposed a novel diffusion model named the synergism-based three-step cascade model(TSSCM)and developed an algorithm named the three-layer collective influence with synergism(CI_TSL)for solving the Influence maximization problem with the TSSCM.The CI_TSL perfectly defined the influence accumulation phenomenon by incorporating the CI formulation and spreading dynamics with synergism.Experiments on five real large-scale social networks demonstrated the efficacy of our method,which achieved competitive results in terms of influence spreading and running time compared to the four other algorithms that were tested.