426
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Detection of overlapping communities is explored in [20], [21], and [22].
Counting triangles using MapReduce was discussed in [15]. The method
descirbed here is from [1], which also gives a technique that works for any
subgraph. [17] discusses randomized algorithms for triangle ﬁnding.
The ANF Algorithm was ﬁrst investigated in [12]. [4] gives an additional
speedup to ANF.
The Smart Transitive-Closure Algorithm was discovered by [7] and [18] in-
dependently. Implementation of transitive closure using MapReduce or similar
systems is discussed in [2].
An open-source C++ implementation of many of the algorithms described
in this chapter can be found in the SNAP library [14].
1. F. N. Afrati, D. Fotakis, and J. D. Ullman, “Enumerating subgraph in-
stances by map-reduce,”
http://ilpubs.stanford.edu:8090/1020
2. F.N. Afrati and J.D. Ullman, “Transitive closure and recursive Datalog
implemented on clusters,” in Proc. EDBT (2012).
3. L. Backstrom and J. Leskovec, “Supervised random walks: predicting and
recommending links in social networks,” Proc. Fourth ACM Intl. Conf.
on Web Search and Data Mining (2011), pp. 635–644.
4. P. Boldi, M. Rosa, and S. Vigna, “HyperANF: approximating the neigh-
bourhood function of very large graphs on a budget,” Proc. WWW Con-
ference (2011), pp. 625–634.
5. S. Fortunato, “Community detection in graphs,” Physics Reports 486:3–5
(2010), pp. 75–174.
6. M. Girvan and M.E.J. Newman, “Community structure in social and bi-
ological networks,” Proc. Natl. Acad. Sci. 99 (2002), pp. 7821–7826.
7. Y.E. Ioannidis, “On the computation of the transitive closure of relational
operators,” Proc. 12th Intl. Conf. on Very Large Data Bases, pp. 403–411.
8. G. Jeh and J. Widom, “Simrank: a measure of structural-context similar-
ity,” Proceedings of the eighth ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining (2002), pp. 538–543.
9. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, “Trawling
the Web for emerging cyber-communities, Computer Networks 31:11–16
(May, 1999), pp. 1481–1493.
10. J. Leskovec, K.J. Lang, A. Dasgupta, and M.W. Mahoney, “Community
structure in large networks: natural cluster sizes and the absence of large
well-deﬁned clusters,” http://arxiv.org/abs/0810.1355.
