Research On Optimizing Effects Of Information Diffusion In Social Networks

With the rapid development of Internet technology,people entered the Internet era.As a new Internet application,social network satisfies the social needs of human beings.As a result,social network has become an important platform for sharing information.The convenience of information diffusion in social networks brings both opportunities and challenges.On the one hand,social network promotes social communication,faci-litates the people's lives and brings new commercial modes.On the other hand,social network becomes the source of internet public opinion events.Therefore,it is critical to explore the patterns of information diffusion in social networks,which plays a key role for monitoring public opinions,social administration and commercial reform etc.To this end,we studied the methods for optimizing effects of information diffusion in social networks from three aspects,the dynamics of information diffusion,the static structure of networks,and combing both the dynamics of information diffusion and the static structure of networks,which correspond to three research problems respecti-vely,i.e,information coverage maximization problem,the unified framework of dense subgraphs extraction,and activity maximization problem.Specifically,Our contributi-ons can be summarized as follows.First,we studied information coverage maximization problem form the perspective of the dynamics of information diffusion.Traditional influence maximization problem only considers active nodes in the process of information diffusion,and neglects the va-lues of inactive nodes.However,inactive nodes include many nodes that are aware of the information being propagated.Thus,to explore the effect of information diffusion,and better measure the coverage of information diffusion,we must consider the trans-mitters(active nodes)and the readers(informed nodes)simultaneously.To this end,we proposed a novel problem called information coverage maximization,which aims to maximize the expected number of active nodes and informed nodes.To better un-derstand the property of this problem,we fully analyzed the computational complexity of the problem and the submodularity of the objective function.Based on these results,we designed three solutions and verified the performance of the proposed algorithms on three real world data sets.The experimental results confirmed the difference between influence maximization and the proposed information coverage maximization problem.Last,we further explored how to decide the relative values of the informed nodes and generalized the information coverage maximization problem.Second,we studied the dense subgraph extraction problem from the perspective of the static structures of social networks.Social users often connect to each other and form communities in social networks.In fact,social networks are consist of different kinds of communities.For a single user,different communities mean different social circles.Thus,to explore users' social circles,we need to extract dense subgraphs of different size and density.Although quite a few algorithms have been proposed to extract dense subgraphs,how to systematically explore the tradeoffs between density and size of the extracted subgraphs is still untouched.To fill this gap,based on quadratic program-ming,we proposed a unified framework for dense subgraphs extraction.We analyzed the framework from the perspective of both numerical optimization and graph theory.We also extended SEA algorithm to solve the problem.We conducted experiments on four real world data sets to evaluate the proposed framework.The experimental results confirmed that the framework extracted subgraphs of different size and density.Last,we combined the dynamics of information diffusion and static structure of social networks and studied activity maximization problem.All the optimization pro-blems based on influence propagation were from the perspective of "nodes" and tried to exploit the value of nodes as separate individuals.They did not consider connections between nodes.However,there are complicated structures formed by nodes.There will be different kinds of interactions among nodes during the process of information diffusion.Therefore,to explore the interaction effect induced by information diffusion and measure the activity of the information being propagated,we need to reconsider the problem from the perspective of "edge" and model the interactions among nodes.To this end,we proposed activity maximization problem,which focuses on the activity caused by the information diffused and tried to maximize the interaction strength among the active nodes.To fully understand the problem,we comprehensively analyzed the properties of the problem.We proved the computational complexity of the problem,dis cussed the approximability of the problem and studied the modularity of the objective function.We also designed a lower bound and an upper bound of the objective function and analyzed the properties of the lower bound and the upper bound.Next,we proposed a sampling method to obtain the unbiased estimations of the activity,the lower bound and the upper bound.We designed a polling based algorithm and derived a data depen-dent approximation ratio.We verified the proposed algorithm on two real world data sets and two synthetic data sets.The experimental results confirmed the effectiveness and the efficiency of the proposed algorithm.