Готові списки джерел за темами / Subgraph Counting

Добірка наукової літератури з теми "Subgraph Counting"

Автор: Grafiati

Опубліковано: 10 грудня 2022

Оновлено: 28 січня 2023

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Зміст

Статті в журналах
Дисертації
Частини книг
Тези доповідей конференцій

Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Subgraph Counting".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Статті в журналах з теми "Subgraph Counting"

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

Більше джерел

Дисертації з теми "Subgraph Counting"

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.

Повний текст джерела

Анотація:

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 та ін.

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Частини книг з теми "Subgraph Counting"

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Тези доповідей конференцій з теми "Subgraph Counting"

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!