Database Reference
In-Depth Information
The Girvan-Newman Algorithm is from [ 6 ]. Finding communities by searching for
complete bipartite graphs appears in [ 9 ] .
Normalized cuts for spectral analysis were introduced in [ 13 ]. [ 19 ] is a survey of spectral
methods for finding clusters, and [ 5 ] is a more general survey of community finding in
graphs. [ 10 ] is an analysis of communities in many networks encountered in practice.
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 ran-
domized algorithms for triangle finding.
The ANF Algorithm was first investigated in [ 12 ]. [ 4 ] gives an additional speedup to
ANF.
The Smart Transitive-Closure Algorithm was discovered by [ 7 ] and [ 18 ] independently.
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 instances 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 net-
works,” 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 neighbourhood function of very large graphs on
a budget,” Proc. WWW Conference (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 biological 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 similarity,” Proceedings of the eighth ACM
SIGKDD Intl. Conf. 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-defined clusters,” http://arxiv.org/abs/0810.1355 .
[11] S. Melnik, H. Garcia-Molina, and E. Rahm, “Similarity flooding: a versatile graph matching algorithm and its
application to schema matching, Proc. Intl. Conf. on Data Engineering (2002), pp. 117-128.
[12] C.R. Palmer, P.B. Gibbons, and C. Faloutsos, “ANF: a fast and scalable tool for data mining in massive graphs,”
Proc. Eighth ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining (2002), pp. 81-90.
[13] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Trans. on Pattern Analysis and Machine
Intelligence ,” 22:8 (2000), pp. 888- 905.
Search WWH ::




Custom Search