Scott Freitas
ML Ph.D. Student at GT

Local Partition in Rich Graphs

Scott Freitas, Nan Cao, Yinglong Xia, Duen Horng (Polo) Chau, Hanghang Tong

This research is an effort to develop visual-graphic interfaces for sense-making of large networks. The goal is to create an algorithmic model and prototype that will allow researchers to study and analyze the hidden patterns in a wide range of networks by identifying local communities around a given seed node using the network topology and attribute information of the graph.

Abstract

Local graph partitioning is a key graph mining tool that allows researchers to identify small groups of interrelated nodes (e.g., people) and their connective edges (e.g., interactions). As local graph partitioning focuses primarily on the graph structure (vertices and edges), it often fails to consider the additional information contained in the attributes. We propose a scalable algorithm to improve local graph partitioning by taking into account both the graph structure and attributes. Experimental results show that our proposed AttriPart algorithm finds up to 1.6x denser local partitions, while running approximately 43x faster than traditional local partitioning techniques (PageRank-Nibble).

Citation

Local Partition in Rich Graphs
Scott Freitas, Nan Cao, Yinglong Xia, Duen Horng (Polo) Chau, Hanghang Tong
IEEE International Conference on Big Data (Big Data). Seattle, Washington, 2018.
Project Demo PDF BibTeX

BibTeX


@INPROCEEDINGS{freitas2018local,
  title={Local Partition in Rich Graphs}, 
  author={Freitas, Scott and Cao, Nan and Xia, Yinglong and Duen Horng, Chau and Tong, Hanghang}, 
  booktitle={IEEE International Conference on Big Data}, 
  year={2018}, 
  publisher={IEEE}
}