Research On Influence Maximization Based On Dynamic Overlapping Communities In Competitive Environment

The influence maximization problem is a hot issue in the field of social networks and is widely used in marketing and so on.Existing studies of the influence maximization problem have mainly been conducted on static networks and often consider only one message when simulating the propagation of information.However,social networks are constantly evolving and there are multiple competing messages propagating in the network at the same time.Hence,the dynamic evolutionary properties of social networks and the competitive properties of information propagation are considered,and the research on influence maximization based on dynamic overlapping communities in a competitive environment is conducted.Specifically,firstly,the incremental-based dynamic overlapping community discovery algorithm is proposed to mine the community structure in the network at different points in time;secondly,the community-based influence maximization algorithm in a competitive environment is proposed to determine the seed set in the network at different points in time.The main research of this thesis is as follows:(1)In most incremental-based dynamic community discovery algorithms,traditional methods are used to discover communities in the initial community discovery phase of the network and the incremental scenarios are not sufficiently considered,which results in the poor accuracy of the communities.For this reason,firstly,the Multi-Label Propagation Algorithm based on Information Entropy for community discovery of the initial network is proposed.The algorithm makes use of the sub-cluster structure to optimize the initial labels of nodes and reduce the number of iterations of label updates to improve the efficiency of the algorithm.And the calculation method of node entropy and label value is proposed based on information entropy to avoid the randomness problem caused by asynchronous updates of labels to ensure the stability of the results.Secondly,based on the community structure of the initial network,the Dynamic Overlapping Community Discovery Algorithm based on Comprehensive Similarity is proposed.The algorithm uses three factors: interaction between nodes,attributes,and structure to construct a model for calculating the similarity between nodes and communities and designs incremental processing strategies for four scenarios of dynamic network evolution to improve the accuracy of community identification.Finally,the two algorithms are validated on static and dynamic datasets respectively,and the results show that the algorithms have good results in terms of quality and accuracy of community discovery.(2)In most influence maximization algorithms,the competitive properties of information are ignored,and the efficiency of calculating the marginal influence gain phase of nodes is low due to extensive Monte Carlo simulations.For this reason,firstly,the Competition-based Independent Cascade Expansion Model is proposed.In this model,the competition mechanism is introduced and the model for calculating the probability of activation between nodes structure between nodes is built by using the three factors: topic distribution,interaction,and structure to simulate the real information dissemination process.Secondly,the Community-based Influence Maximization Algorithm in a Competitive Environment is proposed under the idea of game strategy.In this algorithm,the strategy for community pruning and budget allocation is designed to reduce the size of the network,and the acquisition of the influence set of nodes is proposed to avoid tens of thousands of Monte Carlo simulations to improve the efficiency of the algorithm.Finally,the algorithm is validated on two real social network datasets and the results show that the algorithm has good results in terms of propagation range and operational efficiency.