Random Walk On Multi-relational Heterogeneous Networks

With the rapid development of information technology and multimedia technology,the connections and interactions between entities in various fields have become more frequent,forming a huge network(graph).Analysis and mining on the graphs can reveal many hidden knowledge and information,such as discovering potential links,discovering communities,and so on.Therefore,graph-based mining has become a hot topic for research.There has been varies research on graph mining based on homogeneous graphs.However,in reality,there are many types of entities and the interaction between network objects is complex.For example,entities in a microblog social network include users and blog posts;interactions between entities include following,comment,and forwarding.Such complex networks need heterogeneous graphs to portray.Random walk based on Markov chain simulates the user's transition on graph to obtain the visit probability of each node,and further assists in related research such as sorting,recommendation,and knowledge discovery.Due to the various types of nodes and edges,the random walks based on heterogeneous networks is more difficult.Researchers have designed a high-order Markov process on multi-relational graphs(MultiRank).However,these methods do not distinguish the influence of different types of relationships on the random walk process,which is obviously inconsistent with the actual situation,and the results are also inaccurate.This thesis studies the random walk on multi-relational heterogeneous graph.Based on tensor,a series of algorithms are proposed to solve the random walk in the multi-relational graph.The main contents of this thesis are as follows:(1)This thesis establishes the intra-relation transition probability and inter-relation transition probability respectively to reveal the transition between the entities within same relationship and the transition between different relationships.By using the prior knowledge,SemiRank establishes a loss function to obtain the inter-relation transition probability thus constrains the random sufur to choose which relationship to transition.The experimental results show that the method can achieve better results than MultiRank algorithm.(2)Considering the structure of the multi-relational graph and the attributes of the nodes and edges,TRWRank develops an optimization problem to obtain the intra-relation transition probability and the inter-relation transition probability to guide the random walk on the multi-relational graph.A supervised learning task is formulated so that the random surfer is more likily to visit the important nodes.Experiments show that the TRWRank algorithm can further improve the performance of the results.(3)ClusterRank combines graph clustering and weak ties theory to obtain the importance of different types of relationships to guide the random walk in multi-relational graph.This method clusters nodes in multi-relational graphs and calculats the proportion of weak ties in each type of relationship,so that the importance of different types of relationships can be obtained.This algorithm does not need prior knowledge makes it more applicable than the first two algorithms.Experiments show that ClusterRank performs better than MultiRank.