Local Partition in Rich Graphs

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

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 PDF 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}
}