More Like this

1. Maximal Directed Quasi-Clique Mining

   Guo, Guimu; Yan, Da; Yuan, Lyuheng; Khalil, Jalal; Long, Cheng; Jiang, Zhe; Zhou, Yang (January 2022, Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE))

   Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing $$(\gamma_1, \gamma_2)$$-quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal $$(\gamma_1, \gamma_2)$$-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-$$k$$ large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores. 

   more » « less
2. YACC: A Framework Generalizing TuránShadow for Counting Large Cliques

   Shweta Jain, Hanghang Tong (April 2022, SDM2022)

   Clique-counting is a fundamental problem that has application in many areas eg. dense subgraph discovery, community detection, spam detection, etc. The problem of k-clique-counting is difficult because as k increases, the number of k-cliques goes up exponentially. Enumeration algorithms (even parallel ones) fail to count k-cliques beyond a small k. Approximation algorithms, like TuránShadow have been shown to perform well upto k = 10, but are inefficient for larger cliques. The recently proposed Pivoter algorithm significantly improved the state-of-the-art and was able to give exact counts of all k-cliques in a large number of graphs. However, the clique counts of some graphs (for example, com-lj) are still out of reach of these algorithms. We revisit the TuránShadow algorithm and propose a generalized framework called YACC that leverages several insights about real-world graphs to achieve faster clique-counting. The bottleneck in TuránShadow is a recursive subroutine whose stopping condition is based on a classic result from extremal combinatorics called Turán's theorem. This theorem gives a lower bound for the k-clique density in a subgraph in terms of its edge density. However, this stopping condition is based on a worst-case graph that does not reflect the nature of real-world graphs. Using techniques for quickly discovering dense subgraphs, we relax the stopping condition in a systematic way such that we get a smaller recursion tree while still maintaining the guarantees provided by TuránShadow. We deploy our algorithm on several real-world data sets and show that YACC reduces the size of the recursion tree and the running time by over an order of magnitude. Using YACC, we are able to obtain clique counts for several graphs for which clique-counting was infeasible before, including com-lj. 

   more » « less
3. Mining Largest Maximal Quasi-Cliques

   https://doi.org/10.1145/3446637  

   Sanei-Mehri, Seyed-Vahid; Das, Apurba; Hashemi, Hooman; Tirthapura, Srikanta (June 2021, ACM Transactions on Knowledge Discovery from Data)

   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. 

   more » « less
4. Lipschitz-free Spaces on Finite Metric Spaces

   https://doi.org/10.4153/S0008414X19000087  

   Dilworth, Stephen J.; Kutzarova, Denka; Ostrovskii, Mikhail I. (June 2020, Canadian Journal of Mathematics)

   null (Ed.)

   Abstract Main results of the paper are as follows: (1) For any finite metric space $$M$$ the Lipschitz-free space on $$M$$ contains a large well-complemented subspace that is close to $$\ell _{1}^{n}$$ . (2) Lipschitz-free spaces on large classes of recursively defined sequences of graphs are not uniformly isomorphic to $$\ell _{1}^{n}$$ of the corresponding dimensions. These classes contain well-known families of diamond graphs and Laakso graphs. Interesting features of our approach are: (a) We consider averages over groups of cycle-preserving bijections of edge sets of graphs that are not necessarily graph automorphisms. (b) In the case of such recursive families of graphs as Laakso graphs, we use the well-known approach of Grünbaum (1960) and Rudin (1962) for estimating projection constants in the case where invariant projections are not unique. 

   more » « less
5. Many Cliques with Few Edges

   https://doi.org/10.37236/9550  

   Kirsch, Rachel; Radcliffe, A. J. (January 2021, The Electronic Journal of Combinatorics)

   null (Ed.)

   Recently Cutler and Radcliffe proved that the graph on $$n$$ vertices with maximum degree at most $$r$$ having the most cliques is a disjoint union of $$\lfloor n/(r+1)\rfloor$$ cliques of size $r+1$ together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with $$m$$ edges and maximum degree at most $$r$$, the graph that has the most cliques of size at least two is the disjoint union of $$\bigl\lfloor m \bigm/\binom{r+1}{2} \bigr\rfloor$$ cliques of size $r+1$ together with the colex graph using the remainder of the edges. 

   more » « less