  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 in large networks. A growing body of work has been
adopting local expansion methods in order to identify the community members
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). The algorithm
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. We further
provide theoretical analysis on the local spectral properties, bounding the
measure of tightness of extracted community in terms of the eigenvalues of
graph Laplacian.
  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 seed set
quality and quantity would affect the performance are provided.
