Title page for ETD etd-04132009-134102

Type of Document Master's Thesis
Author Basuchowdhuri, Partha
URN etd-04132009-134102
Title Greedy Methods for Approximate Graph Matching with Applications for Social Network Analysis
Degree Master of Science in Systems Science (M.S.S.S.)
Department Computer Science
Advisory Committee
Advisor Name Title
Jianhua Chen Committee Chair
Peter P. Chen Committee Member
Sukhamay Kundu Committee Member
  • Sub-Graph Mining
  • Seed
  • Social Network Analysis
Date of Defense 2009-03-17
Availability unrestricted
In this thesis, we study greedy algorithms for approximate sub-graph matching with attributed graphs. Such algorithms find one or multiple copies of a sub-graph pattern from a bigger data graph through approximate matching. One intended application of sub-graph matching method is in Social Network Analysis for detecting potential terrorist groups from known terrorist activity patterns. We propose a new method for approximate sub-graph matching which utilizes degree information to reduce the search space within the incremental greedy search framework. In addition, we have introduced the notion of a “seed” in incremental greedy method that aims to find a good initial partial match. Simulated data based on terrorist profiles database is used in our experiments that compare the computational efficiency and matching accuracy of various methods. The experiment results suggest that with increasing size of the data graph, the efficiency advantage of degree-based method becomes more significant, while degree-based method remains as accurate as incremental greedy. Using a “seed” significantly improves matching accuracy (at the cost of decreased efficiency) when the attribute values in the graphs are deceptively noisy. We have also investigated a method that allows to expand a matched sub-graph from the data graph to include those nodes strongly connected to the current match.
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Partha_CSThesis.pdf 546.36 Kb 00:02:31 00:01:18 00:01:08 00:00:34 00:00:02

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.