Journal articles: '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

11

Bourgeois, Nicolas, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, and Vangelis Th Paschos. "Exact and superpolynomial approximation algorithms for the densest k-subgraph problem." European Journal of Operational Research 262, no. 3 (November 2017): 894–903. http://dx.doi.org/10.1016/j.ejor.2017.04.034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Zhang, Peng, and Zhendong Liu. "Approximating Max k-Uncut via LP-rounding plus greed, with applications to Densest k-Subgraph." Theoretical Computer Science 849 (January 2021): 173–83. http://dx.doi.org/10.1016/j.tcs.2020.10.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Liazi, Maria, Ioannis Milis, and Vassilis Zissimopoulos. "A constant approximation algorithm for the densest k-subgraph problem on chordal graphs." Information Processing Letters 108, no. 1 (September 2008): 29–32. http://dx.doi.org/10.1016/j.ipl.2008.03.016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Anwar, Muhammad, Aboul Ella Hassanien, Václav Snás̃el, and Sameh H. Basha. "Subgraph Query Matching in Multi-Graphs Based on Node Embedding." Mathematics 10, no. 24 (December 19, 2022): 4830. http://dx.doi.org/10.3390/math10244830.

Full text

Abstract:

This paper presents an efficient algorithm for matching subgraph queries in a multi-graph based on features-based indexing techniques. The KD-tree data structure represents these nodes’ features, while the set-trie index data structure represents the multi-edges to make queries effectively. The vertex core number, triangle number, and vertex degree are the eight features’ main features. The densest vertex in the query graph is extracted based on these main features. The proposed model consists of two phases. The first phase’s main idea is that, for the densest extracted vertex in the query graph, find the density similar neighborhood structure in the data graph. Then find the k-nearest neighborhood query to obtain the densest subgraph. The second phase for each layer graph, mapping the vertex to feature vector (Vertex Embedding), improves the proposed model. To reduce the node-embedding size to be efficient with the KD-tree, indexing a dimension reduction, the principal component analysis (PCA) method is used. Furthermore, symmetry-breaking conditions will remove the redundancy in the generated pattern matching with the query graph. In both phases, the filtering process is applied to minimize the number of candidate data nodes of the initiate query vertex. The filtering process is applied to minimize the number of candidate data nodes of the initiate query vertex. Finally, testing the effect of the concatenation of the structural features (orbits features) with the meta-features (summary of general, statistical, information-theoretic, etc.) for signatures of nodes on the model performance. The proposed model is tested over three real benchmarks, multi-graph datasets, and two randomly generated multi-graph datasets. The results agree with the theoretical study in both random cliques and Erdos random graph. The experiments showed that the time efficiency and the scalability results of the proposed model are acceptable.

APA, Harvard, Vancouver, ISO, and other styles

15

Manurangsi, Pasin. "Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis." Algorithms 11, no. 1 (January 17, 2018): 10. http://dx.doi.org/10.3390/a11010010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Backer, Jonathan, and J. Mark Keil. "Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs." Information Processing Letters 110, no. 16 (July 2010): 635–38. http://dx.doi.org/10.1016/j.ipl.2010.05.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Huo, Lian-Zhi, and Ping Tang. "A graph-based active learning method for classification of remote sensing images." International Journal of Wavelets, Multiresolution and Information Processing 16, no. 04 (July 2018): 1850023. http://dx.doi.org/10.1142/s0219691318500236.

Full text

Abstract:

Remote sensing (RS) technology provides essential data for monitoring the Earth. To fully utilize the data, image classification is often needed to convert data to information. The success of image classification methods greatly depends on the quality and quantity of training samples. To effectively select more informative training samples, this paper proposes a new active learning (AL) technique for classification of remote sensing (RS) images based on graph theory. A new diversity criterion is proposed based on geometrical features of the support vector machines (SVM) outputs. The diversity selection procedure is converted to the densest k-subgraph [Formula: see text] maximization problem in graph theory. The [Formula: see text] maximization problem is solved by a greedy algorithm. The proposed technique is compared with competing methods adopted in RS community. Experimental tests are performed on very high resolution (VHR) multispectral and hyperspectral images. Experimental results demonstrate that the proposed technique leads to comparable or even better classification accuracies with respect to competing methods on the two datasets.

APA, Harvard, Vancouver, ISO, and other styles

18

Matakos, Antonis, and Aristides Gionis. "Strengthening ties towards a highly-connected world." Data Mining and Knowledge Discovery 36, no. 1 (January 2022): 448–76. http://dx.doi.org/10.1007/s10618-021-00812-1.

Full text

Abstract:

AbstractOnline social networks provide a forum where people make new connections, learn more about the world, get exposed to different points of view, and access information that were previously inaccessible. It is natural to assume that content-delivery algorithms in social networks should not only aim to maximize user engagement but also to offer opportunities for increasing connectivity and enabling social networks to achieve their full potential. Our motivation and aim is to develop methods that foster the creation of new connections, and subsequently, improve the flow of information in the network. To achieve our goal, we propose to leverage the strong triadic closure principle, and consider violations to this principle as opportunities for creating more social links. We formalize this idea as an algorithmic problem related to the densest k-subgraph problem. For this new problem, we establish hardness results and propose approximation algorithms. We identify two special cases of the problem that admit a constant-factor approximation. Finally, we experimentally evaluate our proposed algorithm on real-world social networks, and we additionally evaluate some simpler but more scalable algorithms.

APA, Harvard, Vancouver, ISO, and other styles

19

Bonchi, Francesco, David García-Soriano, Atsushi Miyauchi, and Charalampos E. Tsourakakis. "Finding densest k-connected subgraphs." Discrete Applied Mathematics 305 (December 2021): 34–47. http://dx.doi.org/10.1016/j.dam.2021.08.032.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Galbrun, Esther, Aristides Gionis, and Nikolaj Tatti. "Top-k overlapping densest subgraphs." Data Mining and Knowledge Discovery 30, no. 5 (May 26, 2016): 1134–65. http://dx.doi.org/10.1007/s10618-016-0464-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

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

22

Feige, U., D. Peleg, and G. Kortsarz. "The Dense k -Subgraph Problem." Algorithmica 29, no. 3 (March 2001): 410–21. http://dx.doi.org/10.1007/s004530010050.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

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

24

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

25

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

26

Borgwardt, S., and F. Schmiedl. "Threshold-based preprocessing for approximating the weighted dense k-subgraph problem." European Journal of Operational Research 234, no. 3 (May 2014): 631–40. http://dx.doi.org/10.1016/j.ejor.2013.09.027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

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

28

Chang, Lijun, Mouyi Xu, and Darren Strash. "Efficient maximum k -plex computation over large sparse graphs." Proceedings of the VLDB Endowment 16, no. 2 (October 2022): 127–39. http://dx.doi.org/10.14778/3565816.3565817.

Full text

Abstract:

The k -plex model is a relaxation of the clique model by allowing every vertex to miss up to k neighbors. Designing exact and efficient algorithms for computing a maximum k -plex in a graph has been receiving increasing interest recently. However, the existing algorithms are still inefficient due to having major limitations. We in this paper design a new algorithm kPlexS for the maximum k -plex problem, with three novel contributions. Firstly, we propose a new framework for computing maximum k -plex over large sparse graphs, by iteratively extracting small dense subgraphs from it and then solving each of the extracted dense subgraphs by a branch-and-bound search. Secondly, we propose an efficient reduction algorithm CTCP to reduce the input graph size by exhaustively conducting vertex reduction and edge reduction. CTCP computes a smaller reduced graph and also has a lower time complexity than the existing techniques. Moreover, we iteratively invoke CTCP to reduce the input graph once a vertex has been processed and removed from it. Thirdly, we develop a branch-and-bound algorithm BBMatrix specifically targeting the dense subgraphs that are extracted from the input graph. BBMatrix represents its input graph by an adjacency matrix, and utilizes both first-order (i.e., individual vertices) and second-order information (i.e., pairs of vertices) for reduction and upper bounding. In addition, incremental techniques are proposed to efficiently apply the reduction and upper bounding during the recursion. Extensive empirical studies on large real graphs demonstrate that our algorithm kPlexS outperforms the state-of-the-art algorithms BnB, Maplex, and KpLeX.

APA, Harvard, Vancouver, ISO, and other styles

29

Khot, Subhash. "Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique." SIAM Journal on Computing 36, no. 4 (January 2006): 1025–71. http://dx.doi.org/10.1137/s0097539705447037.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Barman, Debaditya, Subhayan Bhattacharya, Ritam Sarkar, and Nirmalya Chowdhury. "$k$ -Context Technique: A Method for Identifying Dense Subgraphs in a Heterogeneous Information Network." IEEE Transactions on Computational Social Systems 6, no. 6 (December 2019): 1190–205. http://dx.doi.org/10.1109/tcss.2019.2942323.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Gallagher, Suzanne R., and Debra S. Goldberg. "Characterization of known protein complexes using k-connectivity and other topological measures." F1000Research 2 (August 13, 2013): 172. http://dx.doi.org/10.12688/f1000research.2-172.v1.

Full text

Abstract:

Many protein complexes are densely packed, so proteins within complexes often interact with several other proteins in the complex. Steric constraints prevent most proteins from simultaneously binding more than a handful of other proteins, regardless of the number of proteins in the complex. Because of this, as complex size increases, several measures of the complex decrease within protein-protein interaction networks. However, k-connectivity, the number of vertices or edges that need to be removed in order to disconnect a graph, may be consistently high for protein complexes. The property of k-connectivity has been little used previously in the investigation of protein-protein interactions. To understand the discriminative power of k-connectivity and other topological measures for identifying unknown protein complexes, we characterized these properties in known Saccharomyces cerevisiae protein complexes in networks generated both from highly accurate X-ray crystallography experiments which give an accurate model of each complex, and also as the complexes appear in high-throughput yeast 2-hybrid studies in which new complexes may be discovered. We also computed these properties for appropriate random subgraphs. We found that clustering coefficient, mutual clustering coefficient, and k-connectivity are better indicators of known protein complexes than edge density, degree, or betweenness. This suggests new directions for future protein complex-finding algorithms.

APA, Harvard, Vancouver, ISO, and other styles

32

Hébert-Dufresne, Laurent, Guillaume St-Onge, John Meluso, James Bagrow, and Antoine Allard. "Hierarchical team structure and multidimensional localization (or siloing) on networks." Journal of Physics: Complexity 4, no. 3 (July 25, 2023): 035002. http://dx.doi.org/10.1088/2632-072x/ace602.

Full text

Abstract:

Abstract Knowledge silos emerge when structural properties of organizational interaction networks limit the diffusion of information. These structural barriers are known to take many forms at different scales—hubs in otherwise sparse organizations, large dense teams, or global core-periphery structure—but we lack an understanding of how these different structures interact and shape dynamics. Here we take a first theoretical step in bridging the gap between the mathematical literature on localization of spreading dynamics and the more applied literature on knowledge silos in organizational interaction networks. To do so, we introduce a new model that considers a layered structure of teams to unveil a new form of hierarchical localization (i.e. the localization of information at the top or center of an organization) and study its interplay with known phenomena of mesoscopic localization (i.e. the localization of information in large groups), k-core localization (i.e. around denser subgraphs) and hub localization (i.e. around high degree stars). We also include a complex contagion mechanism by considering a general infection kernel which can depend on hierarchical level (influence), degree (popularity), infectious neighbors (social reinforcement) or team size (importance). This very general model allows us to explore the multifaceted phenomenon of information siloing in complex organizational interaction networks and opens the door to new optimization problems to promote or hinder the emergence of different localization regimes.

APA, Harvard, Vancouver, ISO, and other styles

33

Dong, Zheng, Xin Huang, Guorui Yuan, Hengshu Zhu, and Hui Xiong. "Butterfly-core community search over labeled graphs." Proceedings of the VLDB Endowment 14, no. 11 (July 2021): 2006–18. http://dx.doi.org/10.14778/3476249.3476258.

Full text

Abstract:

Community search aims at finding densely connected subgraphs for query vertices in a graph. While this task has been studied widely in the literature, most of the existing works only focus on finding homogeneous communities rather than heterogeneous communities with different labels. In this paper, we motivate a new problem of cross-group community search, namely Butterfly-Core Community (BCC), over a labeled graph, where each vertex has a label indicating its properties and an edge between two vertices indicates their cross relationship. Specifically, for two query vertices with different labels, we aim to find a densely connected cross community that contains two query vertices and consists of butterfly networks, where each wing of the butterflies is induced by a k-core search based on one query vertex and two wings are connected by these butterflies. We first develop a heuristic algorithm achieving 2-approximation to the optimal solution. Furthermore, we design fast techniques of query distance computations, leader pair identifications, and index-based BCC local explorations. Extensive experiments on seven real datasets and four useful case studies validate the effectiveness and efficiency of our BCC and its multi-labeled extension models.

APA, Harvard, Vancouver, ISO, and other styles

34

Sun, Zitan, Xin Huang, Qing Liu, and Jianliang Xu. "Efficient Star-based Truss Maintenance on Dynamic Graphs." Proceedings of the ACM on Management of Data 1, no. 2 (June 13, 2023): 1–26. http://dx.doi.org/10.1145/3589278.

Full text

Abstract:

K-truss is a useful notion of dense subgraphs, which can represent cohesive parts of a graph in a hierarchical way. In practice, in order to enable various truss-based applications to answer queries faster, the edge trussnesses are computed in advance. However, real-world graphs may not always be static and often have edges inserted or removed, leading to costly truss maintenance of recomputing all edge trussnesses. In this paper, we focus on dynamic graphs with star insertions/deletions, where a star insertion can represent a newly joined user with friend connections in social networks or a recently published paper with cited references in citation networks. To tackle such star-based truss maintenance, we propose a new structure of AffBall based on the local structure of an inserted/deleted star motif. With AffBall, we make use of the correlation of inserted edges to compute the trussnesses of the inner edges surrounding the star. Then, we analyze the onion layer of k-truss and conduct truss maintenance for the edges beyond the star, which can be efficiently achieved with a time complexity related to the number of the edges that change the onion layer. Moreover, we extend star-based truss maintenance to handle general updates and single-edge insertions/deletions. Extensive experiments on real-world dynamic graphs verify the effectiveness and efficiency of proposed algorithms against state-of-the-art truss maintenance algorithms.

APA, Harvard, Vancouver, ISO, and other styles

35

Hanaka, Tesshu. "Computing densest k-subgraph with structural parameters." Journal of Combinatorial Optimization 45, no. 1 (December 23, 2022). http://dx.doi.org/10.1007/s10878-022-00927-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Dondi, Riccardo, Mohammad Mehdi Hosseinzadeh, Giancarlo Mauri, and Italo Zoppis. "Top-k overlapping densest subgraphs: approximation algorithms and computational complexity." Journal of Combinatorial Optimization, November 4, 2020. http://dx.doi.org/10.1007/s10878-020-00664-3.

Full text

Abstract:

Abstract A central problem in graph mining is finding dense subgraphs, with several applications in different fields, a notable example being identifying communities. While a lot of effort has been put in the problem of finding a single dense subgraph, only recently the focus has been shifted to the problem of finding a set of densest subgraphs. An approach introduced to find possible overlapping subgraphs is the problem. Given an integer $$k \ge 1$$ k ≥ 1 and a parameter $$\lambda > 0$$ λ > 0 , the goal of this problem is to find a set of k dense subgraphs that may share some vertices. The objective function to be maximized takes into account the density of the subgraphs, the parameter $$\lambda $$ λ and the distance between each pair of subgraphs in the solution. The problem has been shown to admit a $$\frac{1}{10}$$ 1 10 -factor approximation algorithm. Furthermore, the computational complexity of the problem has been left open. In this paper, we present contributions concerning the approximability and the computational complexity of the problem. For the approximability, we present approximation algorithms that improve the approximation factor to $$\frac{1}{2}$$ 1 2 , when k is smaller than the number of vertices in the graph, and to $$\frac{2}{3}$$ 2 3 , when k is a constant. For the computational complexity, we show that the problem is NP-hard even when $$k=3$$ k = 3 .

APA, Harvard, Vancouver, ISO, and other styles

37

Chang, Shih-Chia, Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Shih-Shun Kao, and Ralf Klasing. "On the Hardness and Approximation of the Densest $K$-Subgraph Problem in Parameterized Metric Graphs." SSRN Electronic Journal, 2022. http://dx.doi.org/10.2139/ssrn.4196893.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Joret, Gwenaël, and Adrian Vetta. "Reducing the rank of a matroid." Discrete Mathematics & Theoretical Computer Science Vol. 17 no.2, Discrete Algorithms (September 16, 2015). http://dx.doi.org/10.46298/dmtcs.2135.

Full text

Abstract:

International audience We consider the <i>rank reduction problem</i> for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $k$-cut problem, which admits a 2-approximation algorithm. In this paper we show that the rank reduction problem for transversal matroids is essentially at least as hard to approximate as the densest $k$-subgraph problem. We also prove that, while the problem is easily solvable in polynomial time for partition matroids, it is NP-hard when considering the intersection of two partition matroids. Our proof shows, in particular, that the maximum vertex cover problem is NP-hard on bipartite graphs, which answers an open problem of B. Simeone.

APA, Harvard, Vancouver, ISO, and other styles

39

Koana, Tomohiro, Christian Komusiewicz, and Frank Sommer. "Computing Dense and Sparse Subgraphs of Weakly Closed Graphs." Algorithmica, January 20, 2023. http://dx.doi.org/10.1007/s00453-022-01090-z.

Full text

Abstract:

AbstractA graph G is weakly $$\gamma $$ γ -closed if every induced subgraph of G contains one vertex v such that for each non-neighbor u of v it holds that $$ \vert N(u)\cap N(v) \vert <\gamma $$ | N ( u ) ∩ N ( v ) | < γ . The weak closure $$\gamma (G)$$ γ ( G ) of a graph, recently introduced by Fox et al. (SIAM J Comput 49(2):448–464, 2020), is the smallest number such that G is weakly $$\gamma $$ γ -closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. (2020) on clique enumeration, we show that several problems related to finding dense subgraphs, such as the enumeration of bicliques and s-plexes, are fixed-parameter tractable with respect to $$\gamma (G)$$ γ ( G ) . Moreover, we show that the problem of determining whether a weakly $$\gamma $$ γ -closed graph G has a subgraph on at least k vertices that belongs to a graph class $$\mathcal {G}$$ G which is closed under taking subgraphs admits a kernel with at most $$\gamma k^2$$ γ k 2 vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by $$\gamma +k$$ γ + k where k is the solution size. Furthermore, we show that Independent Dominating Set does not admit a polynomial kernel for constant $$\gamma $$ γ under standard assumptions.

APA, Harvard, Vancouver, ISO, and other styles

40

Tatti, Nikolaj. "Fast computation of distance-generalized cores using sampling." Knowledge and Information Systems, January 25, 2023. http://dx.doi.org/10.1007/s10115-023-01830-9.

Full text

Abstract:

AbstractCore decomposition is a classic technique for discovering densely connected regions in a graph with large range of applications. Formally, a k-core is a maximal subgraph where each vertex has at least k neighbors. A natural extension of a k-core is a (k, h)-core, where each node must have at least k nodes that can be reached with a path of length h. The downside in using (k, h)-core decomposition is the significant increase in the computational complexity: whereas the standard core decomposition can be done in $${{\mathcal {O}}}{\left( m\right) }$$ O m time, the generalization can require $${{\mathcal {O}}}{\left( n^2m\right) }$$ O n 2 m time, where n and m are the number of nodes and edges in the given graph. In this paper, we propose a randomized algorithm that produces an $$\epsilon $$ ϵ -approximation of (k, h) core decomposition with a probability of $$1 - \delta $$ 1 - δ in $${{\mathcal {O}}}{\left( \epsilon ^{-2} hm (\log ^2 n - \log \delta )\right) }$$ O ϵ - 2 h m ( log 2 n - log δ ) time. The approximation is based on sampling the neighborhoods of nodes, and we use Chernoff bound to prove the approximation guarantee. We also study distance-generalized dense subgraphs, show that the problem is NP-hard, provide an algorithm for discovering such graphs with approximate core decompositions, and provide theoretical guarantees for the quality of the discovered subgraphs. We demonstrate empirically that approximating the decomposition complements the exact computation: computing the approximation is significantly faster than computing the exact solution for the networks where computing the exact solution is slow.

APA, Harvard, Vancouver, ISO, and other styles

41

Dondi, Riccardo, and Danny Hermelin. "Computing the k densest subgraphs of a graph." Information Processing Letters, September 2022, 106316. http://dx.doi.org/10.1016/j.ipl.2022.106316.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Siebertz, Sebastian. "Reconfiguration on Nowhere Dense Graph Classes." Electronic Journal of Combinatorics 25, no. 3 (August 10, 2018). http://dx.doi.org/10.37236/7458.

Full text

Abstract:

Let $\mathcal{Q}$ be a vertex subset problem on graphs. In a reconfiguration variant of $\mathcal{Q}$ we are given a graph $G$ and two feasible solutions $S_s, S_t\subseteq V(G)$ of $\mathcal{Q}$ with $|S_s|=|S_t|=k$. The problem is to determine whether there exists a sequence $S_1,\ldots,S_n$ of feasible solutions, where $S_1=S_s$, $S_n=S_t$, $|S_i|\leq k\pm 1$, and each $S_{i+1}$ results from $S_i$, $1\leq i<n$, by the addition or removal of a single vertex.We prove that for every nowhere dense class of graphs and for every integer $r\geq 1$ there exists a polynomial $p_r$ such that the reconfiguration variants of the distance-$r$ independent set problem and the distance-$r$ dominating set problem admit kernels of size $p_r(k)$. If $k$ is equal to the size of a minimum distance-$r$ dominating set, then for any fixed $\epsilon>0$ we even obtain a kernel of almost linear size $\mathcal{O}(k^{1+\epsilon})$. We then prove that if a class $\mathcal{C}$ is somewhere dense and closed under taking subgraphs, then for some value of $r\geq 1$ the reconfiguration variants of the above problems on $\mathcal{C}$ are $\mathsf{W}[1]$-hard (and in particular we cannot expect the existence of kernelization algorithms). Hence our results show that the limit of tractability for the reconfiguration variants of the distance-$r$ independent set problem and distance-$r$ dominating set problem on subgraph closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.

APA, Harvard, Vancouver, ISO, and other styles

43

Dondi, Riccardo, Mohammad Mehdi Hosseinzadeh, and Pietro H. Guzzi. "A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks." Applied Network Science 6, no. 1 (June 5, 2021). http://dx.doi.org/10.1007/s41109-021-00381-8.

Full text

Abstract:

AbstractThe use of networks for modelling and analysing relations among data is currently growing. Recently, the use of a single networks for capturing all the aspects of some complex scenarios has shown some limitations. Consequently, it has been proposed to use Dual Networks (DN), a pair of related networks, to analyse complex systems. The two graphs in a DN have the same set of vertices and different edge sets. Common subgraphs among these networks may convey some insights about the modelled scenarios. For instance, the detection of the Top-k Densest Connected subgraphs, i.e. a set k subgraphs having the largest density in the conceptual network which are also connected in the physical network, may reveal set of highly related nodes. After proposing a formalisation of the approach, we propose a heuristic to find a solution, since the problem is computationally hard. A set of experiments on synthetic and real networks is also presented to support our approach.

APA, Harvard, Vancouver, ISO, and other styles

44

Lv, Zequn, Mei Lu, and Chunqiu Fang. "Density of Balanced 3-Partite Graphs without 3-Cycles or 4-Cycles." Electronic Journal of Combinatorics 29, no. 4 (December 16, 2022). http://dx.doi.org/10.37236/10958.

Full text

Abstract:

Let $C_k$ be a cycle of order $k$, where $k\ge 3$. Let ex$(n, n, n, \{C_{3}, C_{4}\})$ be the maximum number of edges in a balanced $3$-partite graph whose vertex set consists of three parts, each has $n$ vertices that has no subgraph isomorphic to $C_3$ or $C_4$. We construct dense balanced 3-partite graphs without 3-cycles or 4-cycles and show that ex$(n, n, n, \{C_{3}, C_{4}\})\ge (\frac{6\sqrt{2}-8}{(\sqrt{2}-1)^{3/2}}+o(1))n^{3/2}$.

APA, Harvard, Vancouver, ISO, and other styles

45

Luo, Cong, Jie Ma, and Tianchi Yang. "On the maximum number of edges in -critical graphs." Combinatorics, Probability and Computing, July 24, 2023, 1–12. http://dx.doi.org/10.1017/s0963548323000238.

Full text

Abstract:

Abstract A graph is called $k$ -critical if its chromatic number is $k$ but every proper subgraph has chromatic number less than $k$ . An old and important problem in graph theory asks to determine the maximum number of edges in an $n$ -vertex $k$ -critical graph. This is widely open for every integer $k\geq 4$ . Using a structural characterisation of Greenwell and Lovász and an extremal result of Simonovits, Stiebitz proved in 1987 that for $k\geq 4$ and sufficiently large $n$ , this maximum number is less than the number of edges in the $n$ -vertex balanced complete $(k-2)$ -partite graph. In this paper, we obtain the first improvement in the above result in the past 35 years. Our proofs combine arguments from extremal graph theory as well as some structural analysis. A key lemma we use indicates a partial structure in dense $k$ -critical graphs, which may be of independent interest.

APA, Harvard, Vancouver, ISO, and other styles

46

Habib, Wafaa M. A., Hoda M. O. Mokhtar, and Mohamed E. El-Sharkawi. "Discovering top-weighted k-truss communities in large graphs." Journal of Big Data 9, no. 1 (April 3, 2022). http://dx.doi.org/10.1186/s40537-022-00588-1.

Full text

Abstract:

AbstractCommunity Search is the problem of querying networks in order to discover dense subgraphs-communities-that satisfy given query parameters. Most community search models consider link structure and ignore link weight while answering the required queries. Given the importance of link weight in different networks, this paper considers both link structure and link weight to discover top-r weighted k-truss communities via community search. The top-weighted k-truss communities are those communities with the highest weight and the highest cohesiveness within the network. All recent studies that considered link weight discover top-weighted communities via global search and index-based search techniques. In this paper three different algorithms are proposed to scale-up the existing approaches of weighted community search via local search. The performance evaluation shows that the proposed algorithms significantly outperform the existing state-of-the-art algorithms over different datasets in terms of search time by several orders of magnitude.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Densest k-subgraph'

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