P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-06 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:15
6.5 Bibliographic Notes 175presented how communities are evaluated when ground truth exists and
when it does not.6.5 Bibliographic NotesA general survey of community detection in social media can be found in
[Fortunato, 2009] and a review of heterogeneous community detection in
[Tang and Liu, 2010]. In related fields, [Berkhin, 2006;Xu et al., 2005;
Jain et al., 1999] provide surveys of clustering algorithms and [Wasserman
and Faust, 1994] provides a sociological perspective. Comparative analysis
of community detection algorithms can be found in [Lancichinetti and
Fortunato, 2009] and [Leskovec et al., 2010]. The description of explicit
communities in this chapter is due toKadushin [2012].
For member-based algorithms based on node degree, refer to [Kumar
et al., 1999], which provides a systematic approach to finding clique-based
communities with pruning. In algorithms based on node reachability, one
can find communities by finding connected components in the network.
For more information on finding connected components of a graph refer
to [Hopcroft and Tarjan, 1971]. In node similarity, we discussed structural
equivalence, similarity measures, and regular equivalence. More informa-
tion on structural equivalence can be found in [Lorrain and White, 1971;
Leicht et al., 2005], on Jaccard similarity in [Jaccard, 1901], and on regular
equivalence in [Stephen and Martin, 1993].
In group-based methods that find balanced communities, we are often
interested in solving the max-flow min-cut theorem. Linear programming
and Ford-Fulkerson [Cormen, 2009], Edmonds-Karp [Edmonds and Karp,
1972 ], and Push-Relabel [Goldberg and Tarjan, 1988] methods are some
established techniques for solving the max-flow min-cut problem. We dis-
cussed quasi-cliques that help find dense communities. Finding the max-
imum quasi-clique is discussed in [Pattillo et al., 2012]. A well-known
greedy algorithm for finding quasi-cliques is introduced by [Abello et al.,
2002 ]. In their approach a local search with a pruning strategy is performed
on the graph to enhance the speed of quasi-clique detection. They define a
peelstrategy, in which vertices that have some degreekalong with their
incident edges are recursively removed. There are a variety of algorithms
to find dense subgraphs, such as the one discussed in [Gibson et al., 2005]
where the authors propose an algorithm that recursively fingerprints the
graph (shindling algorithm) and creates dense subgraphs. In group-based
methods that find hierarchical communities, we described hierarchical