Research On Influence Maximization Algorithm Based On Heterogeneous Network

In reality,networks are ubiquitous,transportation network,social network,biological network,power network,academic network and so on,various networks emerge in endlessly,and the scale of networks tends to widen.Therefore,many network analysis techniques play important roles in many research fields,such as link prediction,information diffusion and community detection.In recent years,affected by practical problems like "word-of-mouth effect","rumor control" and "viral marketing",the study of influence maximization has drawn more and more attention and become a new research hotspot.Influence maximization can identify a certain number of influential nodes to maximize from a given network.These nodes can influence the most nodes in the network under a given information diffusion model,so as to achieve the purpose of the widest influence spread in the network.Most existing influence maximization algorithms focus on homogeneous networks,and ignore the importance of heterogeneity and the attributes of different types of nodes in heterogeneous networks.Since the real-life networks are almost all heterogeneous networks and existing algorithms based on homogeneous networks are greatly limited in practical applications,it is of great significance to study influence maximization algorithms on heterogeneous networks.The structure of heterogeneous networks is complex and the scale is gradually increasing,so how to leverage the complex heterogeneous structural characteristics and the attributes of different types of nodes to study influence maximization problem in heterogeneous networks is of great challenge and urgency in the real world.In the face of the problem,this paper proposes two influence maximization algorithms based on heterogeneous network,named MAHE-IM and SCHGT-IM,which integrate complex multiple relationships,advanced topological structural characteristics,and different types of node characteristics in heterogeneous networks from different angles to fully capture the heterogeneity of heterogeneous networks respectively.They can capture the heterogeneity of heterogeneous networks to identify high-influence nodes in heterogeneous networks effectively.The main research work and contributions of this dissertation are as follows:(1)Propose the influence maximization algorithm based on multiple aggregation of heterogeneous relation embedding,named MAHE-IM(Multiple Aggregation of Heterogeneous Relation Embedding for IM).The algorithm applies heterogeneous network embeddings under different meta paths with different lengths to capture the complex multi-relational structure and semantic features of heterogeneous networks,and proposes a weighted mechanism to characterize the global and local properties of multiple relations.The node set with high influence is selected by the relevancy and number of occurrences for nodes(seed set).In order to evaluate MAHE-IM more comprehensively,in addition to comparing with the four existing influence maximization methods,we extend fourteen common homogeneous and heterogeneous network embedding methods to influence maximization problem and compare them with the MAHE-IM algorithm in the experiments.The experimental results show that the seed set selected by the MAHE-IM algorithm has better influence performance and less running time on five heterogeneous networks.In addition,we also systematically compared with other algorithms in terms of the iteration number of the information diffusion model,the attributes of the seed set,the size of the seed set and so on,which further verify the effectiveness of MAHE-IM algorithm.In order to facilitate users interested in this area,we develop a webserver of MAHE-IM algorithm.The platform not only includes MAHE-IM algorithm,but also contains the implementations of our extended other influence maximization models.(2)The influence maximization algorithm based on self-supervised clustered heterogeneous graph transformer,named SCHGT-IM(Self-Supervised Clustered Heterogeneous Graph Transformer for IM).The influence maximization problem is closely related to the network advanced topological structural features,and the clustering characteristics can effectively capture the complex network structure.However,the existing clustering-based influence maximization algorithms on heterogeneous networks has not been considered and studied.On the other hand,meta-path-based methods require that researchers learn enough about datasets and have a lot of prior knowledge.Facing these two challenges,we fuse the attribute graph clustering method with the heterogeneous graph transformer method,and apply the self-supervised training method to propose the SCHGT-IM method.The algorithm combines node-type,edge-type and cluster-type meta relations to extract the heterogeneous structure information and node heterogeneity,and finally obtain the seed set by the relevancy of nodes.In addition,we propose a clustered cascade model(CC model)as information diffusion model,which makes the process of information diffusion more in line with real life.We compare with the five existing influence maximization methods and conduct comprehensive experiments on three heterogeneous networks,and the experimental results show that SCHGT-IM algorithm is superior to other algorithms in terms of influence propagation and algorithm efficiency.