Log in

Relevant bibliographies by topics / Densest k-subgraph

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'Densest k-subgraph'

Author: Grafiati

Published: 6 September 2023

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Densest k-subgraph.'

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 "Densest k-subgraph"

1

Sun, Bintao, Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. "KClist++." Proceedings of the VLDB Endowment 13, no. 10 (June 2020): 1628–40. http://dx.doi.org/10.14778/3401960.3401962.

Full text

Abstract:

The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology, finance, as well as social network analysis. The k -clique densest subgraph problem is a generalization of the densest subgraph problem, where the objective is to find a subgraph maximizing the ratio between the number of k -cliques in the subgraph and its number of nodes. It includes as a special case the problem of finding subgraphs with largest average number of triangles ( k = 3), which plays an important role in social network analysis. Moreover, algorithms that deal with larger values of k can effectively find quasi-cliques. The densest subgraph problem can be solved in polynomial time with algorithms based on maximum flow, linear programming or a recent approach based on convex optimization. In particular, the latter approach can scale to graphs containing tens of billions of edges. While finding a densest subgraph in large graphs is no longer a bottleneck, the k -clique densest subgraph remains challenging even when k = 3. Our work aims at developing near-optimal and exact algorithms for the k -clique densest subgraph problem on large real-world graphs. We give a surprisingly simple procedure that can be employed to find the maximal k -clique densest subgraph in large-real world graphs. By leveraging appealing properties of existing results, we combine it with a recent approach for listing all k -cliques in a graph and a sampling scheme, obtaining the state-of-the-art approaches for the aforementioned problem. Our theoretical results are complemented with an extensive experimental evaluation showing the effectiveness of our approach in large real-world graphs.

APA, Harvard, Vancouver, ISO, and other styles

2

Calude, Cristian S., Michael J. Dinneen, and Richard Hua. "Quantum solutions for densest k-subgraph problems." Journal of Membrane Computing 2, no. 1 (February 4, 2020): 26–41. http://dx.doi.org/10.1007/s41965-019-00030-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Nonner, Tim. "PTAS for Densest $$k$$ k -Subgraph in Interval Graphs." Algorithmica 74, no. 1 (November 13, 2014): 528–39. http://dx.doi.org/10.1007/s00453-014-9956-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Liazi, Maria, Ioannis Milis, Fanny Pascual, and Vassilis Zissimopoulos. "The densest k-subgraph problem on clique graphs." Journal of Combinatorial Optimization 14, no. 4 (March 21, 2007): 465–74. http://dx.doi.org/10.1007/s10878-007-9069-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

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

6

Roupin, Frederic, and Alain Billionnet. "A deterministic approximation algorithm for the Densest k-Subgraph Problem." International Journal of Operational Research 3, no. 3 (2008): 301. http://dx.doi.org/10.1504/ijor.2008.017534.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Sotirov, Renata. "On solving the densest k-subgraph problem on large graphs." Optimization Methods and Software 35, no. 6 (March 25, 2019): 1160–78. http://dx.doi.org/10.1080/10556788.2019.1595620.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Guo, Chuan-Hao, Yuan Guo, and Bei-Bei Liu. "Doubly Nonnegative and Semidefinite Relaxations for the Densest k-Subgraph Problem." Entropy 21, no. 2 (January 24, 2019): 108. http://dx.doi.org/10.3390/e21020108.

Full text

Abstract:

The densest k-subgraph (DkS) maximization problem is to find a set of k vertices with maximum total weight of edges in the subgraph induced by this set. This problem is in general NP-hard. In this paper, two relaxation methods for solving the DkS problem are presented. One is doubly nonnegative relaxation, and the other is semidefinite relaxation with tighter relaxation compare with the relaxation of standard semidefinite. The two relaxation problems are equivalent under the suitable conditions. Moreover, the corresponding approximation ratios’ results are given for these relaxation problems. Finally, some numerical examples are tested to show the comparison of these relaxation problems, and the numerical results show that the doubly nonnegative relaxation is more promising than the semidefinite relaxation for solving some DkS problems.

APA, Harvard, Vancouver, ISO, and other styles

9

Xu, Yichen, Chenhao Ma, Yixiang Fang, and Zhifeng Bao. "Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery." Proceedings of the ACM on Management of Data 1, no. 2 (June 13, 2023): 1–27. http://dx.doi.org/10.1145/3589314.

Full text

Abstract:

The densest subgraph problem (DSP) is of great significance due to its wide applications in different domains. Meanwhile, diverse requirements in various applications lead to different density variants for DSP. Unfortunately, existing DSP algorithms cannot be easily extended to handle those variants efficiently and accurately. To fill this gap, we first unify different density metrics into a generalized density definition. We further propose a new model, c-core, to locate the general densest subgraph and show its advantage in accelerating the searching process. Extensive experiments show that our c-core-based optimization can provide up to three orders of magnitude speedup over baselines. Moreover, we study an important variant of DSP under a size constraint, namely the densest-at-least-k-subgraph (DalkS) problem. We propose an algorithm based on graph decomposition, and it is likely to give a solution that is at least 0.8 of the optimal density in our experiments, while the state-of-the-art method can only ensure a solution with density at least 0.5 of the optimal density. Our experiments show that our DalkS algorithm can achieve at least 0.99 of the optimal density for over one-third of all possible size constraints.

APA, Harvard, Vancouver, ISO, and other styles

10

Konar, Aritra, and Nicholas D. Sidiropoulos. "The Triangle-Densest-K-Subgraph Problem: Hardness, Lovász Extension, and Application to Document Summarization." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 4 (June 28, 2022): 4075–82. http://dx.doi.org/10.1609/aaai.v36i4.20325.

Full text

Abstract:

We introduce the triangle-densest-K-subgraph problem (TDKS) for undirected graphs: given a size parameter K, compute a subset of K vertices that maximizes the number of induced triangles. The problem corresponds to the simplest generalization of the edge based densest-K-subgraph problem (DKS) to the case of higher-order network motifs. We prove that TDKS is NP-hard and is not amenable to efficient approximation, in the worst-case. By judiciously exploiting the structure of the problem, we propose a relaxation algorithm for the purpose of obtaining high-quality, sub-optimal solutions. Our approach utilizes the fact that the cost function of TDKS is submodular to construct a convex relaxation for the problem based on the Lovász extension for submodular functions. We demonstrate that our approaches attain state-of-the-art performance on real-world graphs and can offer substantially improved exploration of the optimal density-size curve compared to sophisticated approximation baselines for DKS. We use document summarization to showcase why TDKS is a useful generalization of DKS.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Densest k-subgraph"

1

Wu, Yubao. "Efficient and Effective Local Algorithms for Analyzing Massive Graphs." Case Western Reserve University School of Graduate Studies / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=case1454451336.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Sariyuce, Ahmet Erdem. "Fast Algorithms for Large-Scale Network Analytics." The Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1429825578.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Khanna, Yash. "Robust Algorithms for recovering planted structures in Semi-random instances." Thesis, 2021. https://etd.iisc.ac.in/handle/2005/5096.

Full text

Abstract:

In this thesis, we study algorithms for three fundamental graph problems. These are NP-hard problems which have not been understood completely as there is a signifiicant gap between the algorithmic and the hardness fronts or the hardness factor in the worst-case is pretty large. Thus it is natural to study them in random and semi-random models. This falls under the area of "Beyond worst-case Analysis". We describe these problems now. In the first part, we study the Densest k-subgraph problem (DkS). Given an undirected graph G, the DkS problem asks to compute a set S \subseteq V of cardinality S \leq k such that the weight of edges inside S is maximized. This is a fundamental NP-hard problem whose approximability, in spite of many decades of research, is yet to be settled. We study this problem in models of instances with a planted dense graph and algorithms to recover it. In the second part, we study the Planted Clique problem, i.e., plant a clique instead of an arbitrary dense subgraph in a semi-random model. This model generalizes some of the above models but we get much stronger guarantees of recovery for this special subcase. And finally in the third part, we study the Independent Set problem in r-uniform hypergraphs (r \geq 2), which poses the following question: given a hypergraph, and a subset of vertices such that any r vertices of the set do not have an edge between them. The maximization version of this problem features as one of the Karp's original twenty-one NP-complete problems [Kar72]. Our semi-random models are inspired from the Feige-Kilian model [FK01]. This is a well known model and has been studied along with its many variants in the works of Steinhardt [Ste17], McKenzie et al. [MMT20], etc. for a variety of graph problems including graph coloring [CO07], graph partitioning problems [MMV12, MMV14, MNS16, LV18, LV19], independent set problem [FK01, Ste17, CSV17, MMT20] etc. to name a few. Random and semi-random models of instances have been studied for the Densest k-subgraph problem and the Planted Clique problem (along with its many variants) in the works of [McS01, BCC+10, Ame15, HWX16b, BA19] etc. All of our algorithms are based on rounding a semidefinite program (SDP). Our goal is to study these hard problems in semi-random models which helps us identify some "easier" instances where we can design approximation algorithms with "good" factors (say as compared to the worst-case models). Moreover, our algorithm recovers a "significant" part of the planted solution for a large range of parameters of these models.

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Densest k-subgraph"

1

Chen, Danny Z., Rudolf Fleischer, and Jian Li. "Densest k-Subgraph Approximation on Intersection Graphs." In Approximation and Online Algorithms, 83–93. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-18318-8_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Bourgeois, Nicolas, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, and Vangelis Th Paschos. "Exact and Approximation Algorithms for Densest k-Subgraph." In WALCOM: Algorithms and Computation, 114–25. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-36065-7_12.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Nonner, Tim. "PTAS for Densest k-Subgraph in Interval Graphs." In Lecture Notes in Computer Science, 631–41. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22300-6_53.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Gonzales, Sean, and Theresa Migler. "The Densest k Subgraph Problem in b-Outerplanar Graphs." In Complex Networks and Their Applications VIII, 116–27. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-36687-2_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Zhang, Peng, and Zhendong Liu. "Approximating Max k-Uncut via LP-rounding Plus Greed, with Applications to Densest k-Subgraph." In Algorithmic Aspects in Information and Management, 161–72. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-57602-8_15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Chen, Wenbin, Lingxi Peng, Jianxiong Wang, Fufang Li, and Maobin Tang. "Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset." In Combinatorial Optimization and Applications, 566–73. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-26626-8_41.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Chen, Xujin, Xiaodong Hu, and Changjun Wang. "Finding Connected Dense $$k$$ -Subgraphs." In Lecture Notes in Computer Science, 248–59. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-17142-5_22.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Nikolentzos, Giannis, Polykarpos Meladianos, Yannis Stavrakas, and Michalis Vazirgiannis. "K-Clique-Graphs for Dense Subgraph Discovery." In Machine Learning and Knowledge Discovery in Databases, 617–33. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-71249-9_37.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Dondi, Riccardo, Pietro Hiram Guzzi, and Mohammad Mehdi Hosseinzadeh. "Top-k Connected Overlapping Densest Subgraphs in Dual Networks." In Complex Networks & Their Applications IX, 585–96. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-65351-4_47.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Valari, Elena, Maria Kontaki, and Apostolos N. Papadopoulos. "Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections." In Lecture Notes in Computer Science, 213–30. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31235-9_14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Densest k-subgraph"

1

Tsourakakis, Charalampos. "The K-clique Densest Subgraph Problem." In WWW '15: 24th International World Wide Web Conference. Republic and Canton of Geneva, Switzerland: International World Wide Web Conferences Steering Committee, 2015. http://dx.doi.org/10.1145/2736277.2741098.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Braverman, Mark, Young Kun Ko, Aviad Rubinstein, and Omri Weinstein. "ETH Hardness for Densest-k-Subgraph with Perfect Completeness." In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. http://dx.doi.org/10.1137/1.9781611974782.86.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Jones, Chris, Aaron Potechin, Goutham Rajendran, and Jeff Xu. "Sum-of-Squares Lower Bounds for Densest k-Subgraph." In STOC '23: 55th Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM, 2023. http://dx.doi.org/10.1145/3564246.3585221.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Manurangsi, Pasin. "Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph." In STOC '17: Symposium on Theory of Computing. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3055399.3055412.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Bhaskara, Aditya, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou. "Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph." In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2012. http://dx.doi.org/10.1137/1.9781611973099.34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Tasnádi, Zoltán, and Noémi Gaskó. "An Ant Colony Optimisation Approach to the Densest k-Subgraph Problem*." In 2022 24th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC). IEEE, 2022. http://dx.doi.org/10.1109/synasc57785.2022.00039.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Huang, Nan. "A QUBO Formulation For the K-densest Common Subgraph Isomorphism Problem Via Quantum Annealing." In 2020 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE). IEEE, 2020. http://dx.doi.org/10.1109/csde50874.2020.9411586.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Chang, Shih-Chia, Li-Hsuan Chen, Ling-Ju Hung, Shih-Shun Kao, and Ralf Klasing. "The Hardness and Approximation of the Densest k-Subgraph Problem in Parameterized Metric Graphs." In 2020 International Computer Symposium (ICS). IEEE, 2020. http://dx.doi.org/10.1109/ics51289.2020.00034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Guo, Chuanhao, and Liping Tang. "A New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph." In 2018 International Conference on Mathematics, Modelling, Simulation and Algorithms (MMSA 2018). Paris, France: Atlantis Press, 2018. http://dx.doi.org/10.2991/mmsa-18.2018.70.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Nasir, Muhammad Anis Uddin, Aristides Gionis, Gianmarco De Francisci Morales, and Sarunas Girdzijauskas. "Fully Dynamic Algorithm for Top- k Densest Subgraphs." In CIKM '17: ACM Conference on Information and Knowledge Management. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3132847.3132966.

Full text

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!