Research On Graph Aggregation Algorithm And Aggregated Graph Quality Evaluation Algorithm

Many real world datasets can be modeled as graphs, such as road networks,social networks, biological networks, and web graphs, where nodes represent objectsand edges indicate relationships between nodes. As graph model is applied in variousapplications, large amounts of graph data have been generated, and usually there aremillions of nodes and billions of edges in one graph. There are mass information inthese large scale graph data, which is hardly to understand and analysis by visualizingor handworks for users. Therefore, recent years researchers are interested in how toaggregate the nodes of a large graph into some groups, and construct a concise graphbut efficiently reflect the structural and attributive information of original graphs,called"aggregated graph", hence help users to understand and analysis theunderlying characteristics of large graphs. The process of generating aggregatedgraphs is called"graph aggregation". Graph aggregation plays an important role inthe management, analysis and visualization of graph data. However, there are veryfew research results in graph aggregation. Moreover, the existing results are far fromsystematic. Those algorithms'main shortages are: 1) dependent on specificapplications; 2) only considering partial information of graph, such as structures orattributes of original graphs; 3) having strict constraints on users'interactions andfeedbacks; 4) ignore the relationships between nodes in aggregated graphs.To this end, this paper proposes a new graph aggregation algorithm on directedgraphs with time complexity O(|V|log|V| + |E|), where |V| and |E| are the numbers ofvertices and edges, respectively. The algorithm guarantees the time complexity of thealgorithm while produces high quality aggregation graphs by means of LocalitySensitive Hashing (LSH) and an entropy based partitioning methods. This algorithmproposes a new quality measuring function for aggregated graphs, whichcharacterizes the diversity, coverage, conciseness and utility of aggregated graphs.Compared with existing evaluation measures, the quality evaluation measures foraggregated graphs of this paper focuses on the utility in real applications more.Experiments on real datasets demonstrate the effectiveness of the algorithm.