University of Illinois Urbana-Champaign

Meta-path analysis for community detection in heterogeneous graphs with bound truth labels

Hasan, Aamir

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/104014

Description

Title
Meta-path analysis for community detection in heterogeneous graphs with bound truth labels
Author(s)
Hasan, Aamir
Contributor(s)
Vasudevan, Shobha
Issue Date
2019-05
Keyword(s)
  • Community Detection
  • Heterogeneous Graphs
  • Meta-path
  • Machine Learning
Abstract
Community Detection in heterogeneous graphs has important applications in various fields such as sociology, biology and computer science. Algorithms that are currently used for community detection do not exploit information about the types of edges connecting two nodes and focus entirely on the topology of the graph. We apply the GeneMAPR algorithm that was developed to detect similarities between genes given an input set of known relations between the genes by training regression models using features extracted through meta-path analysis on the graph and generalize it for the purpose of community detection with the aid of ground truth labels. We performed experiments using MAPR to affirm that meta-path analysis can be used to detect communities in homogeneous and heterogeneous graphs. We also conclude that MAPR is able to learn the patterns between nodes provided in the sample set (ground truth labels) and can find similar nodes in the graph to detect meaningful clusters. Additionally, we also analyze MAPR's dependence on its input sample set(s) and connect it to the manner in which it detects communities. While MAPR does not perform as well as other community detection techniques that are based on modularity based edge-cutting, we learned that MAPR can provide important insights into how semantic communities relate to the topology of a graph.
Type of Resource
text
Language
en
Permalink
http://hdl.handle.net/2142/104014

Owning Collections

Senior Theses - Electrical and Computer Engineering PRIMARY
The best of ECE undergraduate research