Research On Graph Mining Based On The Physarum-inspired Model

As an important data structure,graph models are often used to describe the complex relationships in the nature and society.With the development of information technology,graph is used to model the networks around us,such as social networks,traffic networks and protein networks.Graph structures relate to various aspects of people`s lives.And graph mining is helpful to optimize recommended systems,design high effective networks,predict the functions of proteins and so on.How to mine graph data effectively has been a research hotspot.With the development of graph mining,many algorithms are proposed for those graph mining tasks.In terms of the basic strategies,those algorithms fall into two categories: optimization-based algorithms and heuristic algorithms.However,optimization-based algorithms show a low effectiveness when solving largescale problems,and heuristic algorithms are easy to fall into the local optimum.How to improve the accuracy and effectiveness of graph mining algorithms is a significant challenge.Bio-inspired computing is a crucial part of algorithms developing.In recent research,a slime,Physarum,shows a self-organizing and selfoptimizing abilities,and draws more and more attentions.Based on the Physarum-inspired model,this thesis propose optimized strategies and algorithms for improving the effectiveness of graph mining algorithms.This thesis focuses on the sub-graph mining and graph clustering(i.e.,multicast routing problem and community mining).First,we further develop the Physarum mathematical model(PM)to expand its scope of applications.And then,based on the characteristics of PM,this thesis proposes novel operators of algorithms for optimizing current algorithms.The main contributions of this thesis are listed as follows.1)Multicast routing problem is a typical sub-graph mining problem.For solving multicast routing problem,we first modify the PM to build the shortest path tree.Moreover,a novel operator is proposed for PM to reduce the time complexity.With the modified PM,a novel crossover operator,named PMcrossover,is proposed to optimize genetic algorithms for multicast routing problem.Three typical genetic algorithms and four datasets are employed to estimate the effectiveness of proposed PMcrossover.Experiments verify that PMcrossover can improve the effectiveness and search abilities of genetic algorithms.2)Community mining is a representational graph clustering problem.Aiming to solve such problem,this thesis proposed an Physarum-based computational framework for community mining,which optimizes two kinds of evolutionary algorithms and one kind of heuristic algorithm.For further releasing the potential ability of PM on community mining,we modify the Physarum network model to cursorily distinguish intercommunity edges from intra-community edges.Then,the recognition of Physarum model is integrated into the initial process of genetic algorithms and heuristic factors of ant colony algorithms.Based on the priori knowledge of the Physarum model,an optimized strategy is proposed in this thesis.And inspired by the feedback system in Physarum mathematical model,we build a new feedback flow in the dynamic process of Markov clustering algorithms(MCL).With modifying the other operators in the MCL,a novel Physaruminspired is proposed.Extensive experiments on 12 real-world datasets verify the effectiveness and scalability of proposed strategies and algorithms.Over all,this thesis further develops the abilities of Physarum model on graph mining,and combines Physarum model with other algorithms to solve presentational graph mining problems.Extensive experiments show the effectiveness of proposed strategy and algorithms.