  In this paper we discuss a very simple approach of combining content and link
information in graph structures for the purpose of community discovery, a
fundamental task in network analysis. Our approach hinges on the basic
intuition that many networks contain noise in the link structure and that
content information can help strengthen the community signal. This enables ones
to eliminate the impact of noise (false positives and false negatives), which
is particularly prevalent in online social networks and Web-scale information
networks.
  Specifically we introduce a measure of signal strength between two nodes in
the network by fusing their link strength with content similarity. Link
strength is estimated based on whether the link is likely (with high
probability) to reside within a community. Content similarity is estimated
through cosine similarity or Jaccard coefficient. We discuss a simple mechanism
for fusing content and link similarity. We then present a biased edge sampling
procedure which retains edges that are locally relevant for each graph node.
The resulting backbone graph can be clustered using standard community
discovery algorithms such as Metis and Markov clustering.
  Through extensive experiments on multiple real-world datasets (Flickr,
Wikipedia and CiteSeer) with varying sizes and characteristics, we demonstrate
the effectiveness and efficiency of our methods over state-of-the-art learning
and mining approaches several of which also attempt to combine link and content
analysis for the purposes of community discovery. Specifically we always find a
qualitative benefit when combining content with link analysis. Additionally our
biased graph sampling approach realizes a quantitative benefit in that it is
typically several orders of magnitude faster than competing approaches.
