Log in

Relevant bibliographies by topics / Dense subgraphs / Journal articles

To see the other types of publications on this topic, follow the link: Dense subgraphs.

Journal articles on the topic 'Dense subgraphs'

Author: Grafiati

Published: 31 May 2022

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

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Dense subgraphs.'

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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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, and other styles

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.

Full text

Abstract:

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, and other styles

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!