Research On Mining Algorithms On Compact Subgraphs

Graphs are widely used for modeling relationships in various fields,such as sociology,bioinformatics,infrastructure,and the World Wide Web.Real-life graphs are usually globally sparse but locally compact,i.e.,the average degree is often quite small.Therefore,how to mine these tight subgraphs in a large-scale graph network is a very popular research topic,which can help people find the key nodes or groups in the graph.Many compact subgraph models have been given in current research,such as k-core,ktruss,clique,etc.,but these are only considering the topology of the graph.And the nodes(entities)or edges(relationships)in real network graphs often have important properties.For example,an author in a collaborative network has his research area;proteins have their own properties such as molecular function,biological process and cellular composition.When studying these network graphs one should not simply consider only the structural relationships in the graph,but also fully explore those nodes or groups with important properties.Although there are many new models and algorithms to mine tight subgraphs with attributes,network models are very complex and diverse under different domains,so there are many emerging network models that have yet to be explored.In addition,some works have been able to solve the tight subgraph mining problem,but the algorithms are not computationally efficient,so it is difficult to apply to large-scale graphs(containing hundreds of millions of edges).To address these problems,this paper focuses on compact subgraph mining algorithms on dynamic bipartite graphs,multi-valued networks,and graphs with weights.In dynamic bipartite graphs,all nodes are divided into two non-overlapping groups,and nodes or edges are dynamically changed(inserted/removed).For this model,this paper proposes a metric called α(β)-core value,which can reflect the closeness of a node in a bipartite graph and help enumerate the α(β)-core in a bipartite graph.This paper first gives a way to calculate the α(β)-core of nodes,and then goes on to give a kernel maintenance algorithm to dynamically update the kernel values of all nodes,thus avoiding double computation.For multi-valued networks,each node contains attributes of multiple dimensions.In this paper,the skyline model is used to consider the node attributes,and an efficient algorithm is proposed to compute the skyline compact subgraphs in multi-valued networks.In order to solve the problem that the efficiency of the algorithm grows exponentially with the increase of dimensionality,this paper also proposes a dimensionality reduction algorithm using the maximum entropy model.For weighted graphs,especially network graphs with weights of both nodes and edges,this paper proposes a model called the very large(S,C,K)-clique based on kclique to find the compact subgraphs with large weights of both nodes and edges,and in addition gives an efficient algorithm and two indexes to compute the very large(S,C,K)-clique in the graph.The experimental results also validate the effectiveness of the model and the efficiency of the algorithm.