Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


38151.pdf (11.65 MB)

ETD Abstract Container

Abstract Header

Mining for Frequent Community Structures using Approximate Graph Matching

Kolli, Lakshmi Priya
http://orcid.org/0000-0001-5309-1637
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623166375110273

Abstract Details

2021, MS, University of Cincinnati, Engineering and Applied Science: Computer Science.
Large amounts of graph data are produced every day in many areas such as Social networks, Bioinformatics, and Recommendation engines. The primary goal of graph mining is to \textit{discover knowledge} from this data. Frequent Subgraph Mining (FSM) is an important graph mining task that seeks to identify frequently occurring subgraphs, either in a single graph or in a collection of graphs. FSM has a wide range of applications including biological sciences networks, social interaction networks, and collaboration networks. Most of the existing work for FSM has focused on finding subgraphs that are identical copies of each other. However, many applications require that we find sets of subgraphs whose members are only approximately similar to each other. In this thesis, we propose a new framework for Frequent Community Structures Mining where the subgraphs match only approximately. Our approach differs from most of the existing FSM algorithms in its following two important aspects: (i) the way in which candidate subgraphs are generated, and (ii) the way in which candidate subgraphs are matched for similarity. In our approach, we use Random Walks and Markovian Clustering for finding community structures, generate unique signatures to these communities, and compare two communities using the Dynamic Time-Warp Edit Distance technique. We demonstrate the working methodology by implementing it on networks from various domains and validate our results by comparing the topological characteristics of the identified subgraphs and showing that our approach successfully extracts the communities that are indeed very close to each other in structure.
Raj Bhatnagar, Ph.D. (Committee Chair)
Gowtham Atluri, Ph.D. (Committee Member)
Tesfaye Mersha, Ph.D. (Committee Member)
Ali Minai, Ph.D. (Committee Member)
101 p.
Computer Science
Frequent subgraph mining; Approximate Graph Matching; Random Walks; Markov Clustering; Graph Edit Distance; KL Divergence

Recommended Citations

Citations

  • Kolli, L. P. (2021). Mining for Frequent Community Structures using Approximate Graph Matching [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623166375110273

    APA Style (7th edition)

  • Kolli, Lakshmi Priya. Mining for Frequent Community Structures using Approximate Graph Matching. 2021. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623166375110273.

    MLA Style (8th edition)

  • Kolli, Lakshmi Priya. "Mining for Frequent Community Structures using Approximate Graph Matching." Master's thesis, University of Cincinnati, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623166375110273

    Chicago Manual of Style (17th edition)

ucin1623166375110273
38
© 2021, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.