Database Reference
In-Depth Information
[15] S. Suri and S. Vassilivitskii, “Counting triangles and the curse of the last reducer,”
Proc. WWW Conference
(2011).
[16] H. Tong, C. Faloutsos, and J.-Y. Pan, “Fast random walk with restart and its applications,”
ICDM
2006, pp.
613-622.
[17] C.E. Tsourakakis, U. Kang, G.L. Miller, and C. Faloutsos, “DOULION: counting triangles in massive graphs with
a coin,”
Proc. Fifteenth ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining
(2009).
[18] P. Valduriez and H. Boral, “Evaluation of recursive queries using join indices,”
Expert Database Conf.
(1986),
pp. 271-293.
[19] U. von Luxburg, “A tutorial on spectral clustering,”
Statistics and Computing
17:4 (2007), 2007, pp. 395-416.
[20] J. Yang and J. Leskovec, “Overlapping community detection at scale: a nonnegative matrix factorization ap-
proach,”
ACM Intl. Conf. on Web Search and Data Mining
, 2013.
[21] J. Yang, J. McAuley, J. Leskovec, “Detecting cohesive and 2-mode communities in directed and undirected net-
works,”
ACM Intl. Conf. on Web Search and Data Mining
, 2014.
[22] J. Yang, J. McAuley, J. Leskovec, “Community detection in networks with node attributes,”
IEEE Intl. Conf. on
Data Mining
, 2013.
1
It is important to understand that we do not mean a
generated
subgraph - one formed by selecting some nodes and in-
cluding all edges. In this context, we only require that there be edges between any pair of nodes on different sides. It
is also possible that some nodes on the same side are connected by edges as well.
2
Thus, technically, our algorithm is only optimal in the sense of expected running time, not worst-case running time.
However, hashing of large numbers of items has an extremely high probability of behaving according to expectation,
and if we happened to choose a hash function that made some buckets too big, we could rehash until we found a good
hash function.
3
Do not confuse this simple numerical ordering of the nodes with the order
≺
that we discussed in
Section 10.7.2
and
which involved the degrees of the nodes. Here, node degrees are not computed and are not relevant.
4
Technically, this definition gives us the
reflexive and transitive closure
of the graph, since
Path
(
v, v
) is always con-
sidered true, even if there is no cycle that contains
v
.
5
While we cannot compute the transitive closure completely, we can still learn a great deal about the structure of a
graph, provided there are large strongly connected components. For example, the Web graph experiments discussed in
Section 5.1.3
were done on a graph of about 200 million nodes. Although they never listed all the pairs of nodes in the
transitive closure, they were able to describe the structure of the Web.
