Title: Local Partition in Rich Graphs,
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). Because local graph partitioning is
primarily focused on the network structure of the graph (vertices and edges),
it often fails to consider the additional information contained in the
attributes. In this paper we propose---(i) a scalable algorithm to improve
local graph partitioning by taking into account both the network structure of
the graph and the attribute data and (ii) an application of the proposed local
graph partitioning algorithm (AttriPart) to predict the evolution of local
communities (LocalForecasting). Experimental results show that our proposed
AttriPart algorithm finds up to 1.6$\times$ denser local partitions, while
running approximately 43$\times$ faster than traditional local partitioning
techniques (PageRank-Nibble). In addition, our LocalForecasting algorithm shows
a significant improvement in the number of nodes and edges correctly predicted
over baseline methods.