New results for the detection of bicliques
George Manoussakis* · 2024
Read New results for the detection of bicliques by George Manoussakis* (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11234.txt.
Introduction
George Manoussakis offers this 2024 set of results on finding bicliques in graphs. A biclique is a complete two-sided connection pattern: every node on one side linked to every node on the other. Detecting the largest or all maximal bicliques underlies tasks from data mining to biology. Building on known algorithms, the paper sharpens several of them. Most gains target graphs whose maximum degree is small, a constant in many real networks, where the improved running times bite hardest.
Catalog record
| CREATOR | George Manoussakis* |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-11234
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New results for the detection of bicliques George Manoussakis* Abstract Building on existing algorithms and results, we offer new insights and algorithms for various problems related to detecting maximal and maximum bicliques. Most of these results focus on graphs with small maximum degree, providing improved complexities when this parameter is constant; a common characteristic in real-world graphs. 1 Introduction Identifying all bicliques in a graph has been a notable area of research because of its varied applications. This problem is significant in theoretical computer science and also contributes to fields such as data mining, bioinformatics, and social network analysis, where comprehending the complex relationships between entities is essential. For instance, in computational biology, enumerating bicliques has various applications, particularly in biclustering—a data mining technique that simultaneously clusters rows and columns of a matrix to uncover submatrices of related data. This process is closely linked to biclique enumeration in graph theory, where each biclique corresponds to a bicluster, representing strongly connected subsets of entities across two dimensions, see [ 1 ] , [ 2 ] for instance. The problem also finds application in community identification, which aims to uncover clusters of nodes within a network that are more tightly connected to each other than to the rest of the network, revealing structures such as social groups or functional modules. This task is particularly complex in dynamic networks where relationships evolve over time. For instance, in [ 3 ] , the authors address this challenge by using bicliques to track and identify changing communities, thereby providing insights into the evolving nature of social interactions. 2 State of the art An algorithm is considered to have polynomial time delay if the time elapsed between the output of two bicliques is at most polynomial in the size of the input. The complexity of these algorithms is typically described in terms of the time delay. We refer to algorithms that exhibit complexity polynomial in the parameters of the graph and the output size, but are not classified as polynomial time delay, as polynomial output sensitive algorithms. In the scope of this paper we will simply call such algorithms output sensitive. There are a few contributions for the enumeration of maximal non-induced bicliques. Eppstein [ 4 ] proposes a fixed parameter tractable algorithm running in time \mathcal{O}(a^{3}2^{2a}n) where a is the arboricity of the input graph (the arboricity is a graph parameter within a constant factor of the degeneracy). Eppstein also proves that the maximum number of maximal non-induced bicliques is lower bounded by \Omega(2^{a}n/a) and upper bounded by \mathcal{O}(2^{2a}n) . Alexe et al. [ 5 ] propose various solutions for the problem. They propose an output sensitive algorithm with complexity \mathcal{O}(n^{2}\alpha^{2}) with n the order of the graph and \alpha the number of maximal non induced bicliques. They also give a polynomial time delay algorithm with complexity \mathcal{O}(n^{3}) . Additionnaly, Dias et al. [ 6 ] propose an algorithm with complexity \mathcal{O}(n^{3}) . Results also exist for the enumeration of maximal bicliques when the input graph is subject to certain restrictions. For instance when it is bipartite, Makino and Uno [ 7 ] propose a polynomial time delay algorithm with delay \mathcal{O}(\Delta^{2}) (with \Delta the maximum degree of the graph). Damaschke [ 8 ] also provides polynomial time delay algorithms for bipartite graphs with special degree distributions. Note that when the input graph is bipartite, all bicliques are necessarily induced. Concerning the problem of detecting and counting maximum bicliques, there have been several contributions. For example, Gaspers et al. [ 9 ] present an \mathcal{O}(1.2109^{n}) algorithm for finding a maximum biclique, as well as an \mathcal{O}(1.2377^{n}) algorithm for counting all maximum bicliques. 3 Our contributions In Section 4.2 , we demonstrate that by leveraging existing combinatorial arguments and incorporating a few straightforward observations, we can develop an \mathcal{O}(\Delta^{2}) output-sensitive algorithm for enumerating all maximal non-induced bicliques in general graphs. To the best of our knowledge, the best-known algorithm to date has complexity that is polynomial in the order of the graph and the output size. In Section 4.3 , we focus on detecting and counting maximum bicliques. We show that a maximum biclique in a graph G can be found in time \mathcal{O}(nc^{\Delta}\Delta^{\mathcal{O}(1)}) , given an algorithm to find a maximum biclique in time \mathcal{O}(c^{n}n^{\mathcal{O}(1)}) . In practice, by applying a result from Gaspers et al. [ 9 ] , which shows that finding a maximum biclique is equivalent to finding a maximum independent set, and using, for example, the \mathcal{O}(1.2109^{n}) algorithm of Robson [ 10 ] , we obtain an \mathcal{O}(n\cdot 1.2109^{\Delta}) algorithm for this problem. This is stated in Theorem 2 . In a similar fashion, and using results from [ 9 , 10 , 11 ] , we demonstrate that all maximum bicliques can be counted in time \mathcal{O}(n\cdot 1.2377^{\Delta}) , and extend these results to bicliques of size k . These results are stated in Theorem 3 and Corollary 2 . 4 Results 4.1 Notations We consider graphs of the form G=(V,E) which are simple, undirected, with n vertices and m edges. If X\subseteq V , the subgraph of G induced by X is denoted by G[X] . If X\subset V , then X is a proper subgraph of G . When not clear from the context, the vertex set of G will be denoted by V(G) . The set N(x) is called the open neighborhood of the vertex x and consists of the vertices adjacent to x in G . Given an ordering \sigma=v_{1},...,v_{n} of the vertices of G , set V_{i} consists of the vertices following v_{i} including itself in this ordering, that is, the set \{v_{i},v_{i+1},...,v_{n}\} . In the ordering \sigma , the rank of v_{i} , denoted by \sigma(v_{i}) , is its position in the ordering ( i in that case). By [n] , we denote the set of integers \{1,2,...,n\} . The distance between two vertices u , v is the length of the shortest path from u to v . Let N_{i}^{k}(v)=V_{i}\cap N^{k}(v) where N^{k}(v) is the set of vertices at distance k from v (we consider in the paper that N^{1}_{i}(v_{i}) and N_{i}(v_{i}) are equal). 4.2 Enumeration of non induced maximal bicliques In this section we are interested in the problem of enumerating non-induced maximal bicliques. As discussed in the state of the art section, there are a few results for this question. It is important to notice that the problem can be related to the problem of enumerating induced bicliques in bipartite graphs. To see that, we introduce a construction that has been referenced in several papers in various forms. This construction links the problem of enumerating maximal non-induced bicliques in general graphs to the task of enumerating induced bicliques in bipartite graphs. The one we present has been introduced, to the best of our knowledge, in Dias et al. [ 6 ] . Similar constructions have been proposed, for instance in for general graphs and in for for oriented graphs. The construction of et al. [ 6 ] that we consider in this section is as follows. Definition 1 . Let G=(V,E) be a graph. We construct a new bipartite graph G_{1}=(V_{1},E_{1}) . Let V^{\prime} be a duplicate of the vertices of