Pattern mining in large graph database

• Main Author: Foon, Samuel Hoe Mun.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Pattern recognition
• Online Access: http://hdl.handle.net/10356/48577
• Institution: Nanyang Technological University

The structure of large networks models and Internet graphs in the autonomous system can be characterized according to their degree distribution, partitioning them into more dense but smaller parts called sub graphs, which results obtained would be being easier to analyze and be able to find clusters of important vertices. K-Core decomposition is a widely used approach to analyze complex networks as its algorithm complexity is O(max(n, e) )where n is the number of vertices and e is the number of lines(edges or arcs). The number of lines indicates the interaction or connection level of each vertex to others in this network. Previous based visual representation for computational geometry are usually 2D or in a spherical representation. It is a very interesting aspect to explore and implement 3D visualization of core decomposition to show the structure of network more vividly to broad audience, which will in turn aid and speed up the understanding of large networks structure and thus making new observations and discovery of new patterns. In this project, the k-core decomposition algorithm will be studied and implemented to perform core characterization. The objective is to implement the decomposition algorithm and the present the vertices in the 3-Dimensional environment for visualization and analytical purposes. The algorithm will accept data sets of graph details stored in flat files in the form of textual format, it will analyze the graphset and partition them into smaller parts called sub graphs according to their degree, which will then be preprocessed and plotted in 3- Dimensional space for visualization in the layout according to their hierarchy, where visualization is the conversion of data into a visual format so that the characteristics of the data and the relationships among data items can be easily perceived and analyzed by human.