Bibliografías temáticas / Densest k-subgraph

Literatura académica sobre el tema "Densest k-subgraph"

Autor: Grafiati
Publicado: 6 de septiembre de 2023

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Índice

Consulte las listas temáticas de artículos, libros, tesis, actas de conferencias y otras fuentes académicas sobre el tema "Densest k-subgraph".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Artículos de revistas sobre el tema "Densest k-subgraph"

1

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

Texto completo
Resumen
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.
Los estilos APA, Harvard, Vancouver, ISO, etc.
2

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
3

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
4

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
5

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

Texto completo
Resumen
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.
Los estilos APA, Harvard, Vancouver, ISO, etc.
6

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
7

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
8

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

Texto completo
Resumen
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.
Los estilos APA, Harvard, Vancouver, ISO, etc.
9

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

Texto completo
Resumen
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.
Los estilos APA, Harvard, Vancouver, ISO, etc.
10

Konar, Aritra y 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, n.º 4 (28 de junio de 2022): 4075–82. http://dx.doi.org/10.1609/aaai.v36i4.20325.

Texto completo
Resumen
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.
Los estilos APA, Harvard, Vancouver, ISO, etc.
Más fuentes

Tesis sobre el tema "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.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
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.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
3

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

Texto completo
Resumen
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.
Los estilos APA, Harvard, Vancouver, ISO, etc.

Capítulos de libros sobre el tema "Densest k-subgraph"

1

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
2

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
3

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
4

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
5

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
6

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
7

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
8

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
9

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
10

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.

Actas de conferencias sobre el tema "Densest k-subgraph"

1

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
2

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
3

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
4

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
5

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
6

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
7

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
8

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
9

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
10

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
También puede estar interesado en las bibliografías ampliadas sobre el tema "Densest k-subgraph" para tipos de fuentes particulares:
Artículos de revistas
Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!

Pasar a la bibliografía