  Large graphs arise in a number of contexts and understanding their structure
and extracting information from them is an important research area. Early
algorithms on mining communities have focused on the global structure, and
often run in time functional to the size of the entire graph. Nowadays, as we
often explore networks with billions of vertices and find communities of size
hundreds, it is crucial to shift our attention from macroscopic structure to
microscopic structure when dealing with large networks. A growing body of work
has been adopting local expansion methods in order to identify the community
from a few exemplary seed members.
  In this paper, we propose a novel approach for finding overlapping
communities called LEMON (Local Expansion via Minimum One Norm). Different from
PageRank-like diffusion methods, LEMON finds the community by seeking a sparse
vector in the span of the local spectra such that the seeds are in its support.
We show that LEMON can achieve the highest detection accuracy among
state-of-the-art proposals. The running time depends on the size of the
community rather than that of the entire graph. The algorithm is easy to
implement, and is highly parallelizable.
  Moreover, given that networks are not all similar in nature, a comprehensive
analysis on how the local expansion approach is suited for uncovering
communities in different networks is still lacking. We thoroughly evaluate our
approach using both synthetic and real-world datasets across different domains,
and analyze the empirical variations when applying our method to inherently
different networks in practice. In addition, the heuristics on how the quality
and quantity of the seed set would affect the performance are provided.
