Segmentation And Computing Platform Of Large-scale Graph

Graph is a unified model to describe relationships between entities in the real world. Many real life problems such as spam net detection, friend recommendation, advertising and marketing can be researched by building a graph model. The universality of graph model makes it a hot spot for discovering functionality and property of many real systems. As a result, graph management becomes one of the hostest topic in the research field of data management.Based on the fact that community structure is widely available in real large scale graph data, this dessertation studied two issues in large graph analysis:graph segementation and distributed computing platform.Specifically, this dissertation proposed a fast randomized community detection algorithm by utilizing structure similarity and DFS encoding to solve the speed performance issue in large scale graph community detection. To overcome the difficulty in analyzing large graph by visualization, the dissertation leveraged fast community detection algorithms to build visualizing system. The idea of the system is to visualize the graph by layers from global community structures to local details. It does not only provides a way to visualize large scale graph, but also provides a platform to examine community detection algorithm visually. Finally, distributed graph computing platform was studied in order to fill the vacancy of open source implementation. By taking advantage of heterogeneous structure and convergency characteristic of some graph algorithm, the dissertation proposed a new graph computing framework that not only inherited reliability of Hadoop but improved usability and performance for graph algorithm implementation as well.