• Calendar

February 14, Tuesday
12:00 – 13:00

World Wide Web, the Internet, biology PPI networks, and social networks, are only a few examples of networks that contain characteristic patterns, termed network motifs, which occur far more often than in randomized networks with the same degree sequence. Our first set of results is related to motif local counting, namely, counting the number of motifs a vertex is part of. We present several efficient algorithms that approximate the local number of occurrences of k-length cycles and k-length cycles with a chord, where k = O(log n). We also provide efficient algorithms that approximate the local number of occurrences of all motifs of size of at most four.Our second set of results relates to general approximate motif counting. We design sublinear algorithm for approximating the number of copies of constant-size stars in a graph. We prove that our algorithm is tight up to polylogarithmic factors. Our work extends the work of Feige and Goldreich and Ron on approximating the number of edges (or average degree) in a graph. In addition, we give some (negative) results on approximating the number of triangles and on approximating the number of length-3-paths in sublinear time.