Short-Term Positive Influence Maximization Problem In Signed Networks

Complex network is a nonlinear system composed of a large number of nodes and edges,which has a wide range of applications in many fields,such as social networks,transportation networks,protein interaction networks,etc.Influence maximization problem is one of the most classic problems in complex networks,which has been applied in marketing strategy,disease control,public opinion control and other aspects.In recent years,researchers have conducted numerous studies on the influence maximization problem,but most of them are based on unsigned networks,in which only exists positive relationships.However,in real networks,individuals can have both positive and negative relationships with each other,which is known as a signed network.Furthermore,the time factor plays an important role in information diffusion,and maximizing the spread of information or behavior in a short time has more practical applications.Therefore,considering both polarity of edges and time factor in the network,we study the problem of short-term positive influence maximization in signed networks(abbreviated to S-PIM problem).Short-term positive influence maximization problem in signed networks refers to the problem of selecting some nodes to maximize the spread of positive information or behavior in the signed networks during a given time period t.Thus,how to calculate the positive influence of nodes is a critical issue.In this paper,we extend the classical infectious disease SIR model to signed network and use it as the diffusion model.Considering the time t factor,when t is small,we try to find the short-term positive influence of nodes.When t approaches infinity,we try to find the long-term positive influence of nodes.We conduct experiments in three real signed networks to verify the difference between short-term propagation and long-term propagation and show the necessary of considering this S-PIM problem.To solve short-term positive influence maximization problem in signed networks,we propose two methods:2-order positive degree metric and greedy strategy.According to the principle of "the enemy of the enemy is a friend,the friend of the enemy is an enemy",we propose a local evaluation index of nodes—2-order positive degree.Experimental results on Slashdot,Epinions and Wikipedia show that the 2-order positive degree metric performs better than the compared centrality metrics in identifying short-term influential nodes.Furthermore,we prove that short-term positive influence function has monotonicity and submodularity,thus the greedy algorithm is proposed whose approximation ratio is 1-1/ε.We apply both 2-order positive degree metric and greedy algorithm on Wikipedia,verifying that the average positive influence produced by the seed set selected by both methods is close.However,2-order positive degree metric is less time consuming and therefore more suitable for large-scale networks.