Database Reference
In-Depth Information
The Girvan-Newman Algorithm is from [
6
]. Finding communities by searching for
domized algorithms for triangle finding.
ANF.
Implementation of transitive closure using MapReduce or similar systems is discussed in
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,”
[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
[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.