| Social network has become an important communication carrier for everyone in the current information age.Rumor suppression has always been a hot issue in social network.Most of these problems are NP-hard,and approximation algorithms/heuristic algorithms are usually important methods to solve these problems.However,different rumor controlling problems have different theoretical properties,so it is challenging to design approximation algorithms with with high efficiency and guaranteed approximation ratio,as well as general heuristic algorithms with good stability to solve such problems.At the same time,most spread models are too simple and idealized,and it is difficult to reflect the mutual connection of information in the spread process of social networks and the mechanism that affects users.Hence,how to establish the more realistic spread model is the difficulty of research.In addition,it is very meaningful to carry out indepth theoretical analysis on spread model,rumor controlling problem,algorithm and so on,which is helpful to promote the further development of this direction.Therefore based on the influence of social networks,this thesis conducts in-depth research on the spread model,the design of the approximation algorithm and the corresponding theoretical analysis under four kinds of rumor controlling problems.Specifically,this thesis focuses on the following four aspects:(1)Rumor controlling algorithm with boosting-blocking users.This thesis combines boosting users with blocking users,proposes the concept of boosting-blocking users,and further proposes the boosting-blocking cascad model,which can effectively reflect the phenomenon that users receive information in advance and are influenced by the truth.Based on this model,the problem of unconnected Boosting Truth Rumor Controlling(BTRC)is proposed.Then,in view of the monotony and non-submodular BTRC problem,this thesis proposes a multi-hop neighbor optimization strategy,and designs an approximation algorithm by combining the properties of multi-hop neighbors,spread probability and path of rumors.The lower bound on the data-parameter-dependent approximation ratio of the approximation algorithm is not less than(1-1/e)p(u,v)k/(∑v?Bd(T,v)).Where k is a positive integer,T is the initial truth set,p(u,v)is the influence probability in the network,e is a nature constant,v is a node,B is a seed node set and d(T,v)is the length of the shortest directed path from T to v.Furthermore,the idea of connected dominated set is introduced into the cascade model,and the connected boosting-blocking cascade model is proposed.In this model,if only the truth is spread to the first boosting-blocking user,he/she can continue to influence subsequentboosting-blocking users with a high probability.Therefore,compared with the boosting-blocking cascading model,this model can make the cost of spreading the truth smaller.At the same time,this thesis defines the Connected Boosting Truth Rumor Controlling(CBTRC)problem,and uses the connectivity characteristic of multi-hop neighbors to design a multi-hop neighbor heuristic algorithm to find the seed set,so that the desired set is connected.Finally,the effectiveness of the two algorithms is verified by experiments.(2)Rumor controlling algorithm design with cost constraint and location information.This thesis proposes a rumor-truth cascade model in which the credibility of a rumor varies with the number of users influenced by the rumor.Based on this model,this thesis defines the Controlling Rumor with Costs(CRC)problem with cost constraints.Considering that the CRC problem has non-monomonotic and submodular properties,this thesis uses the double random greedy mechanism to design the approximation algorithm,and adds the finite cost greedy mechanism to ensure that the reliability of the seed set meets the cost constraints,making the expectation of the approximation ratio of the algorithm between[1/6,1/2].On the other hand,faced with the situation that some rumors in daily life(such as pyramid selling information)can only be spread offline face-to-face,this thesis uses offline geographic location information networks and online social networks for rumor controlling,and proposes infection independent cascade model and Minimized Rumor with location Information(MRI)problem.This model can effectively reflect the relationship between the probability of users being influenced by rumors and the contact time and contact distance of the rumor spreader.To solve the MRI problem,this thesis uses the dual indexes of distance and influence to design approximation algorithm,so that the designed algorithm has a data-dependent approximation ratio,whose upper bound does not exceed(1-1/e)F(Γ)/(tent-t0).Where t0 and tend are the initial and last check-in times of all users,respectively.Γ is a function of the spread period of the rumor and e is a nature constant.Experiments show that two algorithms can find seed sets under constraints.(3)Rumor controlling algorithm for minimization credibility.This thesis propose rumor-clarifying cascade model,in which each user can be influenced twice at most.This can truly reflect the situation that users are repeatedly swayed by information in real life.Further,this thesis expands the number of users being influenced to any number of times(greater than or equal to three),and proposes a multiple rumor-clarifying cascade model,which makes the model have universality that can be extended to any number of times.At the same time,this thesis proposes the Minimum Credibility Rumor Clarifying(MCRC)problem under the rumor-clarifiying cascade model and the x-times Minimum Credibility Rumor Clarifying(xMCRC)problem under the multiple rumor-clarifying cascade model respectively for the two models.In view of the non-monotonic and submodular properties of these two problems,this thesis proposes the greedy strategy of seed node optimization and the strategy of local increasing confidence,and designs an approximate algorithm based on the longest effective hop number to find the seed set.The approximation ratio of the designed approximation algorithm under the MCRC problem is no less than(1/[?])(1/k)(1-1/e),where ? is a positive number(?≥1),k is a positive integer and e is a nature constant.Experiments show that the proposed algorithm can solve both the MCRC problem and the xMCRC problem.(4)Rumor controlling algorithm for causal rumor enhancement.This thesis proposes a causal rumor enhancement cascade model.In this model,there are two kinds of causal rumors,and nodes in different states have different probabilities of being influenced by these rumors.Moreover,these two kinds of rumors will spread in the network over time,and their influence probabilities will change constantly.Based on this model,the Causal Related Rumors Controlling(CRRC)problem is proposed.In view of the monotonic and non-submodular properties of the CRRC problem,a heuristic algorithm with parameters is designed based on the strategy of combining three-directed circle and node degree.By cleverly proving mathematically the theoretical properties of a three-directed circle,the designed algorithm can be effective and has good stability.Finally,the effectiveness of the proposed algorithm is verified by experiments on large-scale datasets. |
