Zaloguj się

Gotowe bibliografie tematyczne / Densest k-subgraph

Spis treści

Artykuły w czasopismach
Rozprawy doktorskie
Części książek
Streszczenia konferencji

Gotowa bibliografia na temat „Densest k-subgraph”

Autor: Grafiati

Data publikacji: 6 września 2023

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Zobacz listy aktualnych artykułów, książek, rozpraw, streszczeń i innych źródeł naukowych na temat „Densest k-subgraph”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Artykuły w czasopismach na temat "Densest k-subgraph"

1

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

2

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

4

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

5

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

6

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

7

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

8

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

9

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

10

Konar, Aritra, i 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, nr 4 (28.06.2022): 4075–82. http://dx.doi.org/10.1609/aaai.v36i4.20325.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

Więcej źródeł

Rozprawy doktorskie na temat "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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

Części książek na temat "Densest k-subgraph"

1

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

2

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

Nonner, Tim. "PTAS for Densest k-Subgraph in Interval Graphs". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

4

Gonzales, Sean, i Theresa Migler. "The Densest k Subgraph Problem in b-Outerplanar Graphs". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

5

Zhang, Peng, i Zhendong Liu. "Approximating Max k-Uncut via LP-rounding Plus Greed, with Applications to Densest k-Subgraph". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

6

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

7

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

8

Nikolentzos, Giannis, Polykarpos Meladianos, Yannis Stavrakas i Michalis Vazirgiannis. "K-Clique-Graphs for Dense Subgraph Discovery". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

9

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

10

Valari, Elena, Maria Kontaki i Apostolos N. Papadopoulos. "Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Streszczenia konferencji na temat "Densest k-subgraph"

1

Tsourakakis, Charalampos. "The K-clique Densest Subgraph Problem". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

2

Braverman, Mark, Young Kun Ko, Aviad Rubinstein i Omri Weinstein. "ETH Hardness for Densest-k-Subgraph with Perfect Completeness". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

4

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

5

Bhaskara, Aditya, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan i Yuan Zhou. "Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

6

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

7

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

8

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

9

Guo, Chuanhao, i Liping Tang. "A New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph". W 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.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

10

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!