Готові списки джерел за темами / Dense subgraphs / Статті в журналах

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

Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Dense subgraphs.
Автор: Grafiati
Опубліковано: 31 травня 2022

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

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

Ознайомтеся з топ-50 статей у журналах для дослідження на тему "Dense subgraphs".

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

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

Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.

1

Wu, Bo, and Haiying Shen. "Mining connected global and local dense subgraphs for bigdata." International Journal of Modern Physics C 27, no. 07 (May 24, 2016): 1650072. http://dx.doi.org/10.1142/s0129183116500728.

Повний текст джерела
Анотація:
The problem of discovering connected dense subgraphs of natural graphs is important in data analysis. Discovering dense subgraphs that do not contain denser subgraphs or are not contained in denser subgraphs (called significant dense subgraphs) is also critical for wide-ranging applications. In spite of many works on discovering dense subgraphs, there are no algorithms that can guarantee the connectivity of the returned subgraphs or discover significant dense subgraphs. Hence, in this paper, we define two subgraph discovery problems to discover connected and significant dense subgraphs, propose polynomial-time algorithms and theoretically prove their validity. We also propose an algorithm to further improve the time and space efficiency of our basic algorithm for discovering significant dense subgraphs in big data by taking advantage of the unique features of large natural graphs. In the experiments, we use massive natural graphs to evaluate our algorithms in comparison with previous algorithms. The experimental results show the effectiveness of our algorithms for the two problems and their efficiency. This work is also the first that reveals the physical significance of significant dense subgraphs in natural graphs from different domains.
Стилі APA, Harvard, Vancouver, ISO та ін.
2

Hooi, Bryan, Kijung Shin, Hemank Lamba, and Christos Faloutsos. "TellTail: Fast Scoring and Detection of Dense Subgraphs." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 4150–57. http://dx.doi.org/10.1609/aaai.v34i04.5835.

Повний текст джерела
Анотація:
Suppose you visit an e-commerce site, and see that 50 users each reviewed almost all of the same 500 products several times each: would you get suspicious? Similarly, given a Twitter follow graph, how can we design principled measures for identifying surprisingly dense subgraphs? Dense subgraphs often indicate interesting structure, such as network attacks in network traffic graphs. However, most existing dense subgraph measures either do not model normal variation, or model it using an Erdős-Renyi assumption - but this assumption has been discredited decades ago. What is the right assumption then? We propose a novel application of extreme value theory to the dense subgraph problem, which allows us to propose measures and algorithms which evaluate the surprisingness of a subgraph probabilistically, without requiring restrictive assumptions (e.g. Erdős-Renyi). We then improve the practicality of our approach by incorporating empirical observations about dense subgraph patterns in real graphs, and by proposing a fast pruning-based search algorithm. Our approach (a) provides theoretical guarantees of consistency, (b) scales quasi-linearly, and (c) outperforms baselines in synthetic and ground truth settings.
Стилі APA, Harvard, Vancouver, ISO та ін.
3

Rozenshtein, Polina, Nikolaj Tatti, and Aristides Gionis. "Finding Dynamic Dense Subgraphs." ACM Transactions on Knowledge Discovery from Data 11, no. 3 (April 14, 2017): 1–30. http://dx.doi.org/10.1145/3046791.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
4

Semertzidis, Konstantinos, Evaggelia Pitoura, Evimaria Terzi, and Panayiotis Tsaparas. "Finding lasting dense subgraphs." Data Mining and Knowledge Discovery 33, no. 5 (November 28, 2018): 1417–45. http://dx.doi.org/10.1007/s10618-018-0602-x.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
5

Mathieu, Claire, and Michel de Rougemont. "Large very dense subgraphs in a stream of edges." Network Science 9, no. 4 (December 2021): 403–24. http://dx.doi.org/10.1017/nws.2021.17.

Повний текст джерела
Анотація:
AbstractWe study the detection and the reconstruction of a large very dense subgraph in a social graph with n nodes and m edges given as a stream of edges, when the graph follows a power law degree distribution, in the regime when $m=O(n. \log n)$ . A subgraph S is very dense if it has $\Omega(|S|^2)$ edges. We uniformly sample the edges with a Reservoir of size $k=O(\sqrt{n}.\log n)$ . Our detection algorithm checks whether the Reservoir has a giant component. We show that if the graph contains a very dense subgraph of size $\Omega(\sqrt{n})$ , then the detection algorithm is almost surely correct. On the other hand, a random graph that follows a power law degree distribution almost surely has no large very dense subgraph, and the detection algorithm is almost surely correct. We define a new model of random graphs which follow a power law degree distribution and have large very dense subgraphs. We then show that on this class of random graphs we can reconstruct a good approximation of the very dense subgraph with high probability. We generalize these results to dynamic graphs defined by sliding windows in a stream of edges.
Стилі APA, Harvard, Vancouver, ISO та ін.
6

McCarty, Rose. "Dense Induced Subgraphs of Dense Bipartite Graphs." SIAM Journal on Discrete Mathematics 35, no. 2 (January 2021): 661–67. http://dx.doi.org/10.1137/20m1370744.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
7

Asahiro, Yuichi, Refael Hassin, and Kazuo Iwama. "Complexity of finding dense subgraphs." Discrete Applied Mathematics 121, no. 1-3 (September 2002): 15–26. http://dx.doi.org/10.1016/s0166-218x(01)00243-8.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
8

Tibély, Gergely. "Criterions for locally dense subgraphs." Physica A: Statistical Mechanics and its Applications 391, no. 4 (February 2012): 1831–47. http://dx.doi.org/10.1016/j.physa.2011.09.040.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
9

Balister, Paul, Béla Bollobás, Julian Sahasrabudhe, and Alexander Veremyev. "Dense subgraphs in random graphs." Discrete Applied Mathematics 260 (May 2019): 66–74. http://dx.doi.org/10.1016/j.dam.2019.01.032.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
10

Pyber, L. "Regular subgraphs of dense graphs." Combinatorica 5, no. 4 (December 1985): 347–49. http://dx.doi.org/10.1007/bf02579250.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
11

Sariyüce, Ahmet Erdem, and Ali Pinar. "Fast hierarchy construction for dense subgraphs." Proceedings of the VLDB Endowment 10, no. 3 (November 2016): 97–108. http://dx.doi.org/10.14778/3021924.3021927.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
12

Pyber, L., V. Rodl, and E. Szemeredi. "Dense Graphs without 3-Regular Subgraphs." Journal of Combinatorial Theory, Series B 63, no. 1 (January 1995): 41–54. http://dx.doi.org/10.1006/jctb.1995.1004.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
13

Rödl, Vojtěch, and Mathias Schacht. "Complete Partite subgraphs in dense hypergraphs." Random Structures & Algorithms 41, no. 4 (June 25, 2012): 557–73. http://dx.doi.org/10.1002/rsa.20441.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
14

Jiang, Tao, and Andrew Newman. "Small Dense Subgraphs of a Graph." SIAM Journal on Discrete Mathematics 31, no. 1 (January 2017): 124–42. http://dx.doi.org/10.1137/15m1007598.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
15

Kühn, Daniela, Deryk Osthus, and Anusch Taraz. "Large planar subgraphs in dense graphs." Journal of Combinatorial Theory, Series B 95, no. 2 (November 2005): 263–82. http://dx.doi.org/10.1016/j.jctb.2005.04.004.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
16

Rozenshtein, Polina, Francesco Bonchi, Aristides Gionis, Mauro Sozio, and Nikolaj Tatti. "Finding events in temporal networks: segmentation meets densest subgraph discovery." Knowledge and Information Systems 62, no. 4 (October 3, 2019): 1611–39. http://dx.doi.org/10.1007/s10115-019-01403-9.

Повний текст джерела
Анотація:
Abstract In this paper, we study the problem of discovering a timeline of events in a temporal network. We model events as dense subgraphs that occur within intervals of network activity. We formulate the event discovery task as an optimization problem, where we search for a partition of the network timeline into k non-overlapping intervals, such that the intervals span subgraphs with maximum total density. The output is a sequence of dense subgraphs along with corresponding time intervals, capturing the most interesting events during the network lifetime. A naïve solution to our optimization problem has polynomial but prohibitively high running time. We adapt existing recent work on dynamic densest subgraph discovery and approximate dynamic programming to design a fast approximation algorithm. Next, to ensure richer structure, we adjust the problem formulation to encourage coverage of a larger set of nodes. This problem is NP-hard; however, we show that on static graphs a simple greedy algorithm leads to approximate solution due to submodularity. We extend this greedy approach for temporal networks, but we lose the approximation guarantee in the process. Finally, we demonstrate empirically that our algorithms recover solutions with good quality.
Стилі APA, Harvard, Vancouver, ISO та ін.
17

BAADER, SEBASTIAN, and ALEXANDRA KJUCHUKOVA. "Symmetric quotients of knot groups and a filtration of the Gordian graph." Mathematical Proceedings of the Cambridge Philosophical Society 169, no. 1 (April 10, 2019): 141–48. http://dx.doi.org/10.1017/s0305004119000136.

Повний текст джерела
Анотація:
AbstractWe define a metric filtration of the Gordian graph by an infinite family of 1-dense subgraphs. The nth subgraph of this family is generated by all knots whose fundamental groups surject to a symmetric group with parameter at least n, where all meridians are mapped to transpositions. Incidentally, we verify the Meridional Rank Conjecture for a family of knots with unknotting number one yet arbitrarily high bridge number.
Стилі APA, Harvard, Vancouver, ISO та ін.
18

Esperet, Louis, Ross J. Kang, and Stéphan Thomassé. "Separation Choosability and Dense Bipartite Induced Subgraphs." Combinatorics, Probability and Computing 28, no. 5 (February 26, 2019): 720–32. http://dx.doi.org/10.1017/s0963548319000026.

Повний текст джерела
Анотація:
AbstractWe study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This strengthens results of Molloy and Thron and, partially, of Alon. One attempt to drop the bipartiteness assumption precipitates a natural class of Ramsey-type questions, of independent interest. For example, does every triangle-free graph of minimum degree d contain a bipartite induced subgraph of minimum degree Ω(log d) as d→∞?
Стилі APA, Harvard, Vancouver, ISO та ін.
19

Komusiewicz, Christian, Falk Hüffner, Hannes Moser, and Rolf Niedermeier. "Isolation concepts for efficiently enumerating dense subgraphs." Theoretical Computer Science 410, no. 38-40 (September 2009): 3640–54. http://dx.doi.org/10.1016/j.tcs.2009.04.021.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
20

Andersen, Reid. "A local algorithm for finding dense subgraphs." ACM Transactions on Algorithms 6, no. 4 (August 2010): 1–12. http://dx.doi.org/10.1145/1824777.1824780.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
21

Dammak, Mouna, Mahmoud Mejdoub, and Chokri Ben Amar. "Histogram of dense subgraphs for image representation." IET Image Processing 9, no. 3 (March 1, 2015): 184–91. http://dx.doi.org/10.1049/iet-ipr.2014.0189.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
22

Warnke, Lutz. "Dense subgraphs in the H-free process." Discrete Mathematics 311, no. 23-24 (December 2011): 2703–7. http://dx.doi.org/10.1016/j.disc.2011.08.008.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
23

Kostochka, A., and L. Pyber. "Small topological complete subgraphs of “dense” graphs." Combinatorica 8, no. 1 (March 1988): 83–86. http://dx.doi.org/10.1007/bf02122555.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
24

Lazarev, Denis O., and Nikolay N. Kuzyurin. "Dense subgraphs of power-law random graphs." Moscow Journal of Combinatorics and Number Theory 10, no. 1 (January 16, 2021): 1–11. http://dx.doi.org/10.2140/moscow.2021.10.1.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
25

Liu, Jia Cai, Xue Qun Shang, Ya Meng, and Miao Wang. "Mining Maximal Dense Subgraphs in Uncertain PPI Network." Applied Mechanics and Materials 135-136 (October 2011): 609–15. http://dx.doi.org/10.4028/www.scientific.net/amm.135-136.609.

Повний текст джерела
Анотація:
Several studies have shown that the prediction of protein function using PPI data is promising. However, the PPI data generated from experiments are noisy, incomplete and inaccurate, which promotes to represent PPI dataset as an uncertain graph. In this paper, we proposed a novel algorithm to mine maximal dense subgraphs efficiently in uncertain PPI network. It adopted several techniques to achieve efficient mining. An extensive experimental evaluation on yeast PPI network demonstrated that our approach had good performance in terms of precision and efficiency.
Стилі APA, Harvard, Vancouver, ISO та ін.
26

Tang, Qingsong, Yuejian Peng, Xiangde Zhang, and Cheng Zhao. "On Graph-Lagrangians of Hypergraphs Containing Dense Subgraphs." Journal of Optimization Theory and Applications 163, no. 1 (November 26, 2013): 31–56. http://dx.doi.org/10.1007/s10957-013-0485-3.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
27

Ma, Shuai, Renjun Hu, Luoshu Wang, Xuelian Lin, and Jinpeng Huai. "An Efficient Approach to Finding Dense Temporal Subgraphs." IEEE Transactions on Knowledge and Data Engineering 32, no. 4 (April 1, 2020): 645–58. http://dx.doi.org/10.1109/tkde.2019.2891604.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
28

McKAY, BRENDAN D. "Subgraphs of Dense Random Graphs with Specified Degrees." Combinatorics, Probability and Computing 20, no. 3 (January 27, 2011): 413–33. http://dx.doi.org/10.1017/s0963548311000034.

Повний текст джерела
Анотація:
Let d = (d1, d2, . . ., dn) be a vector of non-negative integers with even sum. We prove some basic facts about the structure of a random graph with degree sequence d, including the probability of a given subgraph or induced subgraph.Although there are many results of this kind, they are restricted to the sparse case with only a few exceptions. Our focus is instead on the case where the average degree is approximately a constant fraction of n.Our approach is the multidimensional saddle-point method. This extends the enumerative work of McKay and Wormald (1990) and is analogous to the theory developed for bipartite graphs by Greenhill and McKay (2009).
Стилі APA, Harvard, Vancouver, ISO та ін.
29

Wang, Jiabing, Rongjie Wang, Jia Wei, Qianli Ma, and Guihua Wen. "Finding dense subgraphs with maximum weighted triangle density." Information Sciences 539 (October 2020): 36–48. http://dx.doi.org/10.1016/j.ins.2020.06.004.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
30

Toida, S. "A decomposition of a graph into dense subgraphs." IEEE Transactions on Circuits and Systems 32, no. 6 (June 1985): 583–89. http://dx.doi.org/10.1109/tcs.1985.1085757.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
31

Sariyüce, Ahmet Erdem, C. Seshadhri, Ali Pinar, and Ümit V. Çatalyürek. "Nucleus Decompositions for Identifying Hierarchy of Dense Subgraphs." ACM Transactions on the Web 11, no. 3 (July 12, 2017): 1–27. http://dx.doi.org/10.1145/3057742.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
32

Nikiforov, Vladimir. "Complete r-partite subgraphs of dense r-graphs." Discrete Mathematics 309, no. 13 (July 2009): 4326–31. http://dx.doi.org/10.1016/j.disc.2009.01.008.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
33

Kwan, Matthew, Shoham Letzter, Benny Sudakov, and Tuan Tran. "Dense Induced Bipartite Subgraphs in Triangle-Free Graphs." Combinatorica 40, no. 2 (January 16, 2020): 283–305. http://dx.doi.org/10.1007/s00493-019-4086-0.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
34

Bozorgtabar, Behzad, and Roland Goecke. "Efficient multi-target tracking via discovering dense subgraphs." Computer Vision and Image Understanding 144 (March 2016): 205–16. http://dx.doi.org/10.1016/j.cviu.2015.11.013.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
35

Wang, Zhuo, Weiping Wang, Chaokun Wang, Xiaoyan Gu, Bo Li, and Dan Meng. "Community Focusing: Yet Another Query-Dependent Community Detection." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 329–37. http://dx.doi.org/10.1609/aaai.v33i01.3301329.

Повний текст джерела
Анотація:
As a major kind of query-dependent community detection, community search finds a densely connected subgraph containing a set of query nodes. As density is the major consideration of community search, most methods of community search often find a dense subgraph with many vertices far from the query nodes, which are not very related to the query nodes. Motivated by this, a new problem called community focusing (CF) is studied. It finds a community where the members are close and densely connected to the query nodes. A distance-sensitive dense subgraph structure called β-attention-core is proposed to remove the vertices loosely connected to or far from the query nodes, and a combinational density is designed to guarantee the density of a subgraph. Then CF is formalized as finding a subgraph with the largest combinational density among the β-attention-core subgraphs containing the query nodes with the largest β. Thereafter, effective methods are devised for CF. Furthermore, a speed-up strategy is developed to make the methods scalable to large networks. Extensive experimental results on real and synthetic networks demonstrate the performance of our methods.
Стилі APA, Harvard, Vancouver, ISO та ін.
36

Duong, Quang-huy, Heri Ramampiaro, Kjetil Nørvåg, and Thu-lan Dam. "Density Guarantee on Finding Multiple Subgraphs and Subtensors." ACM Transactions on Knowledge Discovery from Data 15, no. 5 (June 26, 2021): 1–32. http://dx.doi.org/10.1145/3446668.

Повний текст джерела
Анотація:
Dense subregion (subgraph & subtensor) detection is a well-studied area, with a wide range of applications, and numerous efficient approaches and algorithms have been proposed. Approximation approaches are commonly used for detecting dense subregions due to the complexity of the exact methods. Existing algorithms are generally efficient for dense subtensor and subgraph detection, and can perform well in many applications. However, most of the existing works utilize the state-or-the-art greedy 2-approximation algorithm to capably provide solutions with a loose theoretical density guarantee. The main drawback of most of these algorithms is that they can estimate only one subtensor, or subgraph, at a time, with a low guarantee on its density. While some methods can, on the other hand, estimate multiple subtensors, they can give a guarantee on the density with respect to the input tensor for the first estimated subsensor only. We address these drawbacks by providing both theoretical and practical solution for estimating multiple dense subtensors in tensor data and giving a higher lower bound of the density. In particular, we guarantee and prove a higher bound of the lower-bound density of the estimated subgraph and subtensors. We also propose a novel approach to show that there are multiple dense subtensors with a guarantee on its density that is greater than the lower bound used in the state-of-the-art algorithms. We evaluate our approach with extensive experiments on several real-world datasets, which demonstrates its efficiency and feasibility.
Стилі APA, Harvard, Vancouver, ISO та ін.
37

FOX, JACOB, and BENNY SUDAKOV. "Decompositions into Subgraphs of Small Diameter." Combinatorics, Probability and Computing 19, no. 5-6 (June 9, 2010): 753–74. http://dx.doi.org/10.1017/s0963548310000040.

Повний текст джерела
Анотація:
We investigate decompositions of a graph into a small number of low-diameter subgraphs. Let P(n, ε, d) be the smallest k such that every graph G = (V, E) on n vertices has an edge partition E = E0 ∪ E1 ∪ ⋅⋅⋅ ∪ Ek such that |E0| ≤ εn2, and for all 1 ≤ i ≤ k the diameter of the subgraph spanned by Ei is at most d. Using Szemerédi's regularity lemma, Polcyn and Ruciński showed that P(n, ε, 4) is bounded above by a constant depending only on ε. This shows that every dense graph can be partitioned into a small number of ‘small worlds’ provided that a few edges can be ignored. Improving on their result, we determine P(n, ε, d) within an absolute constant factor, showing that P(n, ε, 2) = Θ(n) is unbounded for ε < 1/4, P(n, ε, 3) = Θ(1/ε2) for ε > n−1/2 and P(n, ε, 4) = Θ(1/ε) for ε > n−1. We also prove that if G has large minimum degree, all the edges of G can be covered by a small number of low-diameter subgraphs. Finally, we extend some of these results to hypergraphs, improving earlier work of Polcyn, Rödl, Ruciński and Szemerédi.
Стилі APA, Harvard, Vancouver, ISO та ін.
38

KANG, DONG YEAP. "Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs." Combinatorics, Probability and Computing 28, no. 3 (November 5, 2018): 423–64. http://dx.doi.org/10.1017/s0963548318000469.

Повний текст джерела
Анотація:
Mader proved that every strongly k-connected n-vertex digraph contains a strongly k-connected spanning subgraph with at most 2kn - 2k2 edges, where equality holds for the complete bipartite digraph DKk,n-k. For dense strongly k-connected digraphs, this upper bound can be significantly improved. More precisely, we prove that every strongly k-connected n-vertex digraph D contains a strongly k-connected spanning subgraph with at most kn + 800k(k + Δ(D)) edges, where Δ(D) denotes the maximum degree of the complement of the underlying undirected graph of a digraph D. Here, the additional term 800k(k + Δ(D)) is tight up to multiplicative and additive constants. As a corollary, this implies that every strongly k-connected n-vertex semicomplete digraph contains a strongly k-connected spanning subgraph with at most kn + 800k2 edges, which is essentially optimal since 800k2 cannot be reduced to the number less than k(k - 1)/2.We also prove an analogous result for strongly k-arc-connected directed multigraphs. Both proofs yield polynomial-time algorithms.
Стилі APA, Harvard, Vancouver, ISO та ін.
39

Ishigami, Yoshiyasu. "Almost-Spanning Subgraphs with Bounded Degree in Dense Graphs." European Journal of Combinatorics 23, no. 5 (July 2002): 583–612. http://dx.doi.org/10.1006/eujc.2002.0576.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
40

Ebsen, Oliver, Giulia S. Maesaka, Christian Reiher, Mathias Schacht, and Bjarne Schülke. "Embedding spanning subgraphs in uniformly dense and inseparable graphs." Random Structures & Algorithms 57, no. 4 (August 24, 2020): 1077–96. http://dx.doi.org/10.1002/rsa.20957.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
41

Bazgan, Cristina, Janka Chlebíková, and Clément Dallard. "Graphs without a partition into two proportionally dense subgraphs." Information Processing Letters 155 (March 2020): 105877. http://dx.doi.org/10.1016/j.ipl.2019.105877.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
42

Böhme, Thomas, and Alexandr Kostochka. "Many disjoint dense subgraphs versus large k-connected subgraphs in large graphs with given edge density." Discrete Mathematics 309, no. 4 (March 2009): 997–1000. http://dx.doi.org/10.1016/j.disc.2008.01.010.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
43

Liu, Hairong, Longin Jan Latecki, and Shuicheng Yan. "Fast Detection of Dense Subgraphs with Iterative Shrinking and Expansion." IEEE Transactions on Pattern Analysis and Machine Intelligence 35, no. 9 (September 2013): 2131–42. http://dx.doi.org/10.1109/tpami.2013.16.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
44

Hernandez, Cecilia, Carlos Mella, Gonzalo Navarro, Alvaro Olivera-Nappa, and Jaime Araya. "Protein complex prediction via dense subgraphs and false positive analysis." PLOS ONE 12, no. 9 (September 22, 2017): e0183460. http://dx.doi.org/10.1371/journal.pone.0183460.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
45

Böttcher, Julia, Mathias Schacht, and Anusch Taraz. "Spanning 3-colourable subgraphs of small bandwidth in dense graphs." Journal of Combinatorial Theory, Series B 98, no. 4 (July 2008): 752–77. http://dx.doi.org/10.1016/j.jctb.2007.11.005.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
46

Lee, Anthony J. T., Ming-Chih Lin, and Chia-Ming Hsu. "Mining Dense Overlapping Subgraphs in weighted protein–protein interaction networks." Biosystems 103, no. 3 (March 2011): 392–99. http://dx.doi.org/10.1016/j.biosystems.2010.11.010.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
47

Gudapati, Naga V. C., Enrico Malaguti, and Michele Monaci. "In search of dense subgraphs: How good is greedy peeling?" Networks 77, no. 4 (March 20, 2021): 572–86. http://dx.doi.org/10.1002/net.22034.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
48

McDiarmid, Colin, Alex Scott, and Paul Withers. "The component structure of dense random subgraphs of the hypercube." Random Structures & Algorithms 59, no. 1 (February 12, 2021): 3–24. http://dx.doi.org/10.1002/rsa.20990.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
49

Ma, Chenhao, Yixiang Fang, Reynold Cheng, Laks V. S. Lakshmanan, Wenjie Zhang, and Xuemin Lin. "Efficient Directed Densest Subgraph Discovery." ACM SIGMOD Record 50, no. 1 (June 15, 2021): 33–40. http://dx.doi.org/10.1145/3471485.3471494.

Повний текст джерела
Анотація:
Given a directed graph G, the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G, whose density is the highest among all the subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a threethousand- edge graph, it takes three days for one of the best exact algorithms to complete. In this paper, we develop an efficient and scalable DDS solution. We introduce the notion of [x, y]-core, which is a dense subgraph for G, and show that the densest subgraph can be accurately located through the [x, y]-core with theoretical guarantees. Based on the [x, y]-core, we develop both exact and approximation algorithms. We have performed an extensive evaluation of our approaches on eight real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.
Стилі APA, Harvard, Vancouver, ISO та ін.
50

Sanei-Mehri, Seyed-Vahid, Apurba Das, Hooman Hashemi, and Srikanta Tirthapura. "Mining Largest Maximal Quasi-Cliques." ACM Transactions on Knowledge Discovery from Data 15, no. 5 (June 26, 2021): 1–21. http://dx.doi.org/10.1145/3446637.

Повний текст джерела
Анотація:
Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Enumerating quasi-cliques from a graph is a robust way to detect densely connected structures with applications in bioinformatics and social network analysis. However, enumerating quasi-cliques in a graph is a challenging problem, even harder than the problem of enumerating cliques. We consider the enumeration of top- k degree-based quasi-cliques and make the following contributions: (1) we show that even the problem of detecting whether a given quasi-clique is maximal (i.e., not contained within another quasi-clique) is NP-hard. (2) We present a novel heuristic algorithm K ernel QC to enumerate the k largest quasi-cliques in a graph. Our method is based on identifying kernels of extremely dense subgraphs within a graph, followed by growing subgraphs around these kernels, to arrive at quasi-cliques with the required densities. (3) Experimental results show that our algorithm accurately enumerates quasi-cliques from a graph, is much faster than current state-of-the-art methods for quasi-clique enumeration (often more than three orders of magnitude faster), and can scale to larger graphs than current methods.
Стилі APA, Harvard, Vancouver, ISO та ін.
Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!

До бібліографії