Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 9 of 9 for “"subgraph counting"”.
-
Parameterised algorithms for counting subgraphs, matchings, and monochromatic partitions
Counting the number of solutions to a computational problem is at least as hard as deciding whether a solution exists. In fact, it is often much harder. However, in theory, as well as in practice, it is often of interest to determine the number of solutions to computational problems. In this …
-
Empirical Study of Two Hypothesis Test Methods for Community Structure in Networks
… which works for dense graph. Another one is the subgraph counting method proposed by Gao and Lafferty (2017a), valid for sparse network. In this paper, firstly, we empirically study the BS or GL methods to see whether either of them works for moderately sparse network; secondly, we propose a …
-
Models of streaming computation
… tractable. These include: • New algorithms for counting triangles in the insertion-only and linear sketching models, along with tight (up to log factors) lower bounds. • A quantum streaming algorithm for counting triangles, giving the first quantum advantage for a natural one-pass streaming …
-
Monochromatic Subgraphs in Multiplex Networks
… we study the joint distribution of monochromatic subgraphs for dense multiplex networks, that is, networks with multiple layers. Specifically, given a finite collection of graphs $H_1,\ldots,H_d$, we derive the asymptotic joint distribution of $\bm T_n:= (T(H_1, G_n^{(1)}),\ldots, T(H_d, …
-
Time Windowed Data Structures
… problems,window reporting problemsandwindow counting problems.Considering an RE graph G=(|V|=n, |E|=m) as the input, where each edge inEhas a unique positive timestamp, we present data structures to answer the following window problems; (a) decision problems for monotone graph properties, …
-
Graph analytics and subset selection problems in machine learning
… relevant to modern machine learning research: 1) Subgraph counting and 2) High-dimensional subset selection. The former can be used to construct features for performing graph analytics. The latter has applications in sparse modeling such as feature selection, sparse regression, and interpretable …
-
A Study on Privacy Preserving Data Publishing With Differential Privacy
… private noise over the result of several subgraph queries on a graph dataset. Besides, to ensure expected utility, by selecting a maximal noise level $\theta$, our proposed system can generate noisy result with expected utility. Comparing with existing models for several subgraph counting …
-
Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation
… verification. We begin by studying the 4-cycle counting problem in the fully dynamic model and show an improvement over the previous best algorithm, demonstrating that the previously assumed natural bound was not tight. In the sublinear setting, we examine the problem of estimating matching size …