Relevant bibliographies by topics / Subgraph Counting

Academic literature on the topic 'Subgraph Counting'

Author: Grafiati
Published: 10 December 2022
Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Subgraph Counting.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Subgraph Counting"

1

Ribeiro, Pedro, Pedro Paredes, Miguel E. P. Silva, David Aparicio, and Fernando Silva. "A Survey on Subgraph Counting." ACM Computing Surveys 54, no. 2 (April 2021): 1–36. http://dx.doi.org/10.1145/3433652.

Full text
Abstract:
Computing subgraph frequencies is a fundamental task that lies at the core of several network analysis methodologies, such as network motifs and graphlet-based metrics, which have been widely used to categorize and compare networks from multiple domains. Counting subgraphs is, however, computationally very expensive, and there has been a large body of work on efficient algorithms and strategies to make subgraph counting feasible for larger subgraphs and networks. This survey aims precisely to provide a comprehensive overview of the existing methods for subgraph counting. Our main contribution is a general and structured review of existing algorithms, classifying them on a set of key characteristics, highlighting their main similarities and differences. We identify and describe the main conceptual approaches, giving insight on their advantages and limitations, and we provide pointers to existing implementations. We initially focus on exact sequential algorithms, but we also do a thorough survey on approximate methodologies (with a trade-off between accuracy and execution time) and parallel strategies (that need to deal with an unbalanced search space).
APA, Harvard, Vancouver, ISO, and other styles
2

Zhang, Hao, Jeffrey Xu Yu, Yikai Zhang, Kangfei Zhao, and Hong Cheng. "Distributed subgraph counting." Proceedings of the VLDB Endowment 13, no. 12 (August 2020): 2493–507. http://dx.doi.org/10.14778/3407790.3407840.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Sze, Lawrence. "The number of edges on generalizations of Paley graphs." International Journal of Mathematics and Mathematical Sciences 27, no. 2 (2001): 111–23. http://dx.doi.org/10.1155/s0161171201002071.

Full text
Abstract:
Evans, Pulham, and Sheenan computed the number of complete4-subgraphs of Paley graphs by counting the number of edges of the subgraph containing only those nodesxfor whichxandx−1are quadratic residues. Here we obtain formulae for the number of edges of generalizations of these subgraphs using Gaussian hypergeometric series and elliptic curves. Such formulae are simple in several infinite families, including those studied by Evans, Pulham, and Sheenan.
APA, Harvard, Vancouver, ISO, and other styles
4

FÜRER, MARTIN, and SHIVA PRASAD KASIVISWANATHAN. "Approximately Counting Embeddings into Random Graphs." Combinatorics, Probability and Computing 23, no. 6 (July 9, 2014): 1028–56. http://dx.doi.org/10.1017/s0963548314000339.

Full text
Abstract:
LetHbe a graph, and letCH(G) be the number of (subgraph isomorphic) copies ofHcontained in a graphG. We investigate the fundamental problem of estimatingCH(G). Previous results cover only a few specific instances of this general problem, for example the case whenHhas degree at most one (the monomer-dimer problem). In this paper we present the first general subcase of the subgraph isomorphism counting problem, which is almost always efficiently approximable. The results rely on a new graph decomposition technique. Informally, the decomposition is a labelling of the vertices such that every edge is between vertices with different labels, and for every vertex all neighbours with a higher label have identical labels. The labelling implicitly generates a sequence of bipartite graphs, which permits us to break the problem of counting embeddings of large subgraphs into that of counting embeddings of small subgraphs. Using this method, we present a simple randomized algorithm for the counting problem. For all decomposable graphsHand all graphsG, the algorithm is an unbiased estimator. Furthermore, for all graphsHhaving a decomposition where each of the bipartite graphs generated is small and almost all graphsG, the algorithm is a fully polynomial randomized approximation scheme.We show that the graph classes ofHfor which we obtain a fully polynomial randomized approximation scheme for almost allGincludes graphs of degree at most two, bounded-degree forests, bounded-width grid graphs, subdivision of bounded-degree graphs, and major subclasses of outerplanar graphs, series-parallel graphs and planar graphs of large girth, whereas unbounded-width grid graphs are excluded. Moreover, our general technique can easily be applied to proving many more similar results.
APA, Harvard, Vancouver, ISO, and other styles
5

McKay, Brendan D., and Stanisław P. Radziszowski. "Subgraph Counting Identities and Ramsey Numbers." Journal of Combinatorial Theory, Series B 69, no. 2 (March 1997): 193–209. http://dx.doi.org/10.1006/jctb.1996.1741.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Roth, Marc. "Parameterized Counting of Partially Injective Homomorphisms." Algorithmica 83, no. 6 (March 11, 2021): 1829–60. http://dx.doi.org/10.1007/s00453-021-00805-y.

Full text
Abstract:
AbstractWe study the parameterized complexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorphisms, subgraph counting and, more generally, counting of answers to equi-join queries with inequalities. Our main result presents an exhaustive complexity classification for the problem in fixed-parameter tractable and $$\#\mathsf {W[1]}$$ # W [ 1 ] -complete cases. The proof relies on the framework of linear combinations of homomorphisms as independently discovered by Chen and Mengel (PODS 16) and by Curticapean, Dell and Marx in the recent breakthrough result regarding the exact complexity of the subgraph counting problem (STOC 17). Moreover, we invoke Rota’s NBC-Theorem to obtain an explicit criterion for fixed-parameter tractability based on treewidth. The abstract classification theorem is then applied to the problem of counting locally injective graph homomorphisms from small pattern graphs to large target graphs. As a consequence, we are able to fully classify its parameterized complexity depending on the class of allowed pattern graphs.
APA, Harvard, Vancouver, ISO, and other styles
7

Bressan, Marco. "Faster algorithms for counting subgraphs in sparse graphs." Algorithmica 83, no. 8 (February 22, 2021): 2578–605. http://dx.doi.org/10.1007/s00453-021-00811-0.

Full text
Abstract:
AbstractGiven a k-node pattern graph H and an n-node host graph G, the subgraph counting problem asks to compute the number of copies of H in G. In this work we address the following question: can we count the copies of H faster if G is sparse? We answer in the affirmative by introducing a novel tree-like decomposition for directed acyclic graphs, inspired by the classic tree decomposition for undirected graphs. This decomposition gives a dynamic program for counting the homomorphisms of H in G by exploiting the degeneracy of G, which allows us to beat the state-of-the-art subgraph counting algorithms when G is sparse enough. For example, we can count the induced copies of any k-node pattern H in time $$2^{O(k^2)} O(n^{0.25k + 2} \log n)$$ 2 O ( k 2 ) O ( n 0.25 k + 2 log n ) if G has bounded degeneracy, and in time $$2^{O(k^2)} O(n^{0.625k + 2} \log n)$$ 2 O ( k 2 ) O ( n 0.625 k + 2 log n ) if G has bounded average degree. These bounds are instantiations of a more general result, parameterized by the degeneracy of G and the structure of H, which generalizes classic bounds on counting cliques and complete bipartite graphs. We also give lower bounds based on the Exponential Time Hypothesis, showing that our results are actually a characterization of the complexity of subgraph counting in bounded-degeneracy graphs.
APA, Harvard, Vancouver, ISO, and other styles
8

Liu, Xin, and Yangqiu Song. "Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 7 (June 28, 2022): 7594–602. http://dx.doi.org/10.1609/aaai.v36i7.20725.

Full text
Abstract:
Graph neural networks (GNNs) and message passing neural networks (MPNNs) have been proven to be expressive for subgraph structures in many applications. Some applications in heterogeneous graphs require explicit edge modeling, such as subgraph isomorphism counting and matching. However, existing message passing mechanisms are not designed well in theory. In this paper, we start from a particular edge-to-vertex transform and exploit the isomorphism property in the edge-to-vertex dual graphs. We prove that searching isomorphisms on the original graph is equivalent to searching on its dual graph. Based on this observation, we propose dual message passing neural networks (DMPNNs) to enhance the substructure representation learning in an asynchronous way for subgraph isomorphism counting and matching as well as unsupervised node classification. Extensive experiments demonstrate the robust performance of DMPNNs by combining both node and edge representation learning in synthetic and real heterogeneous graphs.
APA, Harvard, Vancouver, ISO, and other styles
9

Che, Yulin, Zhuohang Lai, Shixuan Sun, Yue Wang, and Qiong Luo. "Accelerating truss decomposition on heterogeneous processors." Proceedings of the VLDB Endowment 13, no. 10 (June 2020): 1751–64. http://dx.doi.org/10.14778/3401960.3401971.

Full text
Abstract:
Truss decomposition is to divide a graph into a hierarchy of subgraphs, or trusses. A subgraph is a k -truss ( k ≥ 2) if each edge is in at least k --- 2 triangles in the subgraph. Existing algorithms work by first counting the number of triangles each edge is in and then iteratively incrementing k to peel off the edges that will not appear in ( k + 1)-truss. Due to the data and computation intensity, truss decomposition on billion-edge graphs takes hours to complete on a commodity computer. We propose to accelerate in-memory truss decomposition by (1) compacting intermediate results to optimize memory access, (2) dynamically adjusting the computation based on data characteristics, and (3) parallelizing the algorithm on both the multicore CPU and the GPU. In particular, we optimize the triangle enumeration with data skew handling, and determine at runtime whether to pursue peeling or direct triangle counting to obtain a certain k -truss. We further develop a CPU-GPU co-processing strategy in which the CPU first computes intermediate results and sends the compacted results to the GPU for further computation. Our experiments on real-world datasets show that our implementations outperform the state of the art by up to an order of magnitude. Our source code is publicly available at https://github.com/RapidsAtHKUST/AccTrussDecomposition.
APA, Harvard, Vancouver, ISO, and other styles
10

WANLESS, IAN M. "Counting Matchings and Tree-Like Walks in Regular Graphs." Combinatorics, Probability and Computing 19, no. 3 (February 10, 2010): 463–80. http://dx.doi.org/10.1017/s0963548309990678.

Full text
Abstract:
The number of closed tree-like walks in a graph is closely related to the moments of the roots of the matching polynomial for the graph. Thus, by counting these walks up to a given length it is possible to find approximations for the matching polynomial. This approach has been used in two separate problems involving asymptotic enumerations of 1-factorizations of regular graphs. Nevertheless, a systematic way to count the required walks had not previously been found.In this paper we give an algorithm to count closed tree-like walks in a regular graph up to a given length. For smallm, this provides expressions for the number ofm-matchings in the graph in terms of the numbers of copies of certain small subgraphs that appear in the graph. The simplest of these expressions were already known, having been rediscovered by numerous authors usingad hocmethods. We offer the first general method for producing the expressions. We also find generating functions that isolate the contribution from the simplest kind of subgraph – namely a single cycle of arbitrary length.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Subgraph Counting"

1

Peebles, John Lee Thompson Jr. "Sublinear-time algorithms for counting star subgraphs with applications to join selectivity estimation." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/103746.

Full text
Abstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 37-43).
We study the problem of estimating the value of sums of the form ... when one has the ability to sample xi ;> 0 with probability proportional to its magnitude. When p = 2, this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case when {x} is the degree sequence of a graph, which corresponds to counting the number of p-stars in a graph when one has the ability to sample edges randomly. Our algorithm for a ...-multiplicative approximation of Sp has query and time complexities ... Here, m = ... is the number of edges in the graph, E2 Sp or equivalently, half the number of records in the database table. Similarly, n is the number of vertices in the graph and the number of unique values in the database table. We also provide tight lower bounds (up to polylogarithmic factors) in almost all cases, even when {xi} is a degree sequence and one is allowed to use the structure of the graph to try to get a better estimate. We are not aware of any prior lower bounds on the problem of join selectivity estimation. For the graph problem, prior work which assumed the ability to sample only vertices uniformly gave algorithms with matching lower bounds [Gonen, Ron, and Shavitt. SIAM J. Comput., 25 (2011), pp. 1365-14111. With the ability to sample edges randomly, we show that one can achieve faster algorithms for approximating the number of star subgraphs, bypassing the lower bounds in this prior work. For example, in the regime where ... , our upper bound is ... in contrast to their ... lower bound when no random edge queries are available. In addition, we consider the problem of counting the number of directed paths of length two when the graph is directed. This problem is equivalent to estimating the selectivity of a join query between two distinct tables. We prove that the general version of this problem cannot be solved in sublinear time. However, when the ratio between in-degree and out-degree is bounded-or equivalently, when the ratio between the number of occurrences of values in the two columns being joined is bounded-we give a sublinear time algorithm via a reduction to the undirected case.
by John Lee Thompson Peebles, Jr.
S.M.
APA, Harvard, Vancouver, ISO, and other styles
2

Grácio, Luciano Polónia Gonçalves. "From Supergraph Generation To Subgraph Counting." Master's thesis, 2019. https://hdl.handle.net/10216/126194.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Branquinho, Henrique Jorge Santos. "Counting Subgraphs in Streaming Networks." Master's thesis, 2020. https://hdl.handle.net/10216/133054.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Branquinho, Henrique Jorge Santos. "Counting Subgraphs in Streaming Networks." Dissertação, 2020. https://hdl.handle.net/10216/133054.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Paredes, Pedro Miguel Reis Bento. "Counting subgraphs: from static to dynamic networks." Master's thesis, 2017. https://repositorio-aberto.up.pt/handle/10216/107381.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Paredes, Pedro Miguel Reis Bento. "Counting subgraphs: from static to dynamic networks." Dissertação, 2017. https://repositorio-aberto.up.pt/handle/10216/107381.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Subgraph Counting"

1

Yang, Yi, Da Yan, Shuigeng Zhou, and Guimu Guo. "Parallel Clique-Like Subgraph Counting and Listing." In Conceptual Modeling, 484–97. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-33223-5_40.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Henzinger, Monika, Andrea Lincoln, and Barna Saha. "The Complexity of Average-Case Dynamic Subgraph Counting." In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 459–98. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2022. http://dx.doi.org/10.1137/1.9781611977073.23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Branquinho, Henrique, Luciano Grácio, and Pedro Ribeiro. "StreamFaSE: An Online Algorithm for Subgraph Counting in Dynamic Networks." In Complex Networks & Their Applications IX, 688–99. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-65351-4_55.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Amini, Omid, Fedor V. Fomin, and Saket Saurabh. "Counting Subgraphs via Homomorphisms." In Automata, Languages and Programming, 71–82. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02927-1_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Chanchary, Farah, and Anil Maheshwari. "Counting Subgraphs in Relational Event Graphs." In WALCOM: Algorithms and Computation, 194–206. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-30139-6_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Kane, Daniel M., Kurt Mehlhorn, Thomas Sauerwald, and He Sun. "Counting Arbitrary Subgraphs in Data Streams." In Automata, Languages, and Programming, 598–609. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31585-5_53.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Kloks, T., D. Kratsch, and H. Müller. "Finding and counting small induced subgraphs efficiently." In Graph-Theoretic Concepts in Computer Science, 14–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-60618-1_62.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Suganami, Shuya, Toshiyuki Amagasa, and Hiroyuki Kitagawa. "Accelerating All 5-Vertex Subgraphs Counting Using GPUs." In Lecture Notes in Computer Science, 55–70. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-59003-1_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Grácio, Luciano, and Pedro Ribeiro. "An Efficient Approach for Counting Occurring Induced Subgraphs." In Complex Networks X, 33–45. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-14459-3_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Ribeiro, Pedro, Fernando Silva, and Luís Lopes. "A Parallel Algorithm for Counting Subgraphs in Complex Networks." In Biomedical Engineering Systems and Technologies, 380–93. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-18472-7_30.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Subgraph Counting"

1

Liu, Xin, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. "Neural Subgraph Isomorphism Counting." In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3394486.3403247.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

eddin, Ahmad Naser, and Pedro Ribeiro. "Scalable subgraph counting using MapReduce." In SAC 2017: Symposium on Applied Computing. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3019612.3019744.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Slota, George M., and Kamesh Madduri. "Fast Approximate Subgraph Counting and Enumeration." In 2013 42nd International Conference on Parallel Processing (ICPP). IEEE, 2013. http://dx.doi.org/10.1109/icpp.2013.30.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Bordino, Ilaria, Debora Donato, Aristides Gionis, and Stefano Leonardi. "Mining Large Networks with Subgraph Counting." In 2008 Eighth IEEE International Conference on Data Mining (ICDM). IEEE, 2008. http://dx.doi.org/10.1109/icdm.2008.109.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Zhao, Kangfei, Jeffrey Xu Yu, Hao Zhang, Qiyan Li, and Yu Rong. "A Learned Sketch for Subgraph Counting." In SIGMOD/PODS '21: International Conference on Management of Data. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3448016.3457289.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Wang, Hanchen, Rong Hu, Ying Zhang, Lu Qin, Wei Wang, and Wenjie Zhang. "Neural Subgraph Counting with Wasserstein Estimator." In SIGMOD/PODS '22: International Conference on Management of Data. New York, NY, USA: ACM, 2022. http://dx.doi.org/10.1145/3514221.3526163.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Chakaravarthy, Venkatesan T., Michael Kapralov, Prakash Murali, Fabrizio Petrini, Xinyu Que, Yogish Sabharwal, and Baruch Schieber. "Subgraph Counting: Color Coding Beyond Trees." In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2016. http://dx.doi.org/10.1109/ipdps.2016.122.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Aparicio, David Oliveira, Pedro Manuel Pinto Ribeiro, and Fernando Manuel Augusto da Silva. "Parallel Subgraph Counting for Multicore Architectures." In 2014 IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA). IEEE, 2014. http://dx.doi.org/10.1109/ispa.2014.14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Ribeiro, Pedro, Fernando Silva, and Luis Lopes. "Efficient Parallel Subgraph Counting Using G-Tries." In 2010 IEEE International Conference on Cluster Computing (CLUSTER). IEEE, 2010. http://dx.doi.org/10.1109/cluster.2010.27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Chen, Langshi, Jiayu Li, Cenk Sahinalp, Madhav Marathe, Anil Vullikanti, Andrey Nikolaev, Egor Smirnov, Ruslan Israfilov, and Judy Qiu. "SubGraph2Vec: Highly-Vectorized Tree-like Subgraph Counting." In 2019 IEEE International Conference on Big Data (Big Data). IEEE, 2019. http://dx.doi.org/10.1109/bigdata47090.2019.9006037.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Subgraph Counting' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography