1

A Change-Sensitive Algorithm for Maintaining
Maximal Bicliques in a Dynamic Bipartite Graph

arXiv:1707.08272v1 [] 26 Jul 2017

Apurba Das, Srikanta Tirthapura, Senior Member, IEEE,
Abstract—We consider the maintenance of maximal bicliques from a dynamic bipartite graph that changes over time due to the
addition or deletion of edges. When the set of edges in a graph changes, we are interested in knowing the change in the set of maximal
bicliques (the “change”), rather than in knowing the set of maximal bicliques that remain unaffected. The challenge in an efficient
algorithm is to enumerate the change without explicitly enumerating the set of all maximal bicliques. In this work, we present (1)
near-tight bounds on the magnitude of change in the set of maximal bicliques of a graph, due to a change in the edge set (2) a
“change-sensitive” algorithm for enumerating the change in the set of maximal bicliques, whose time complexity is proportional to the
magnitude of change that actually occurred in the set of maximal bicliques in the graph. To our knowledge, these are the first
algorithms for enumerating maximal bicliques in a dynamic graph, with such provable performance guarantees. Our algorithms are
easy to implement, and experimental results show that their performance exceeds that of current baseline implementations by orders
of magnitude.

F

1

I NTRODUCTION

Graphs are ubiquitous in representing linked data in many
domains such as in social network analysis, computational
biology, and web search. Often, these networks are dynamic,
where new connections are being added and old connections are being removed. The area of dynamic graph mining
focuses on efficient methods for finding and maintaining
significant patterns in a dynamic graph. In this work we
focus on the maintenance of dense subgraphs within a
dynamic graph.
Our work is motivated by many applications that require
the maintenance of dense substructures from a dynamic
graph. Angel et al. [6], propose an algorithm for identifying breaking news stories in real-time through dense
subgraph mining from an evolving graph, defined on the
co-occurrence of entities within messages in an online social
network. [17] present methods for detecting communities
among users in a microblogging platform through identifying dense structures in an evolving network representing
connections among users. A sample of other applications of
dense subgraph mining in networks include identification of
communities in a social network [15], [23], identification of
web communities [14], [28], [18], phylogenetic tree construction [11], [29], [34], communities in bipartite networks [19],
genome analysis [26], and closed itemset mining [32], [20].
We consider the fundamental problem of maintaining
maximal bicliques in a bipartite graph that is changing due
to the addition or deletion of edges. Let G = (L, R, E)
be a simple undirected bipartite graph with its vertex set
partitioned into L, R, and edge set E ⊆ L × R. A biclique in
G is a bipartition B = (X, Y ), X ⊆ L, Y ⊆ R such that each
vertex in X is connected to each vertex in Y . A biclique B
is called a maximal biclique if there is no other biclique B 0
•

Das and Tirthapura are with the Department of Electrical and Computer
Engineering, Iowa State University, Ames, IA 50011.
E-mail: {adas,snt}@iastate.edu.
The authors were partially supported through the NSF grant 1527541.

such that B is a proper subgraph of B 0 . Let BC(G) denote
the set of all maximal bicliques in G.
Suppose that, starting from bipartite graph G1 =
(L, R, E), the state of the graph changes to G2 = (L, R, E ∪
H) due to the addition of a set of new edges H . Let
Υnew (G1 , G2 ) = BC(G2 ) \ BC(G1 ) denote the set of new
maximal bicliques that arise in G2 that were not present
in G1 and Υdel (G1 , G2 ) = BC(G1 ) \ BC(G2 ) denote the
set of maximal bicliques in G1 that are no longer maximal
bicliques in G2 (henceforth called as subsumed bicliques).
See Fig. 1 for an example. Let Υ(G1 , G2 ) = Υnew (G1 , G2 ) ∪
Υdel (G1 , G2 ) denote the symmetric difference of BC(G1 )
and BC(G2 ). We ask the following questions:
(1) How large can be the size of Υ(G1 , G2 )? In particular,
can a small change in the set of edges cause a large change
in the set of maximal bicliques in the graph?
(2) How can we compute Υ(G1 , G2 ) efficiently? Can
we quickly compute Υ(G1 , G2 ) when |Υ(G1 , G2 )| is small?
In short, can we design change-sensitive algorithms for enumerating elements of Υ(G1 , G2 ), whose time complexity is
proportional to the size of change, |Υ(G1 , G2 )|?
1.1

Contributions

Magnitude of Change: Let g(n) denote the maximum
number of maximal bicliques possible in an n vertex
bipartite graph. A result due to Prisner [27] shows that
g(n) ≤ 2n/2 , where equality occurs when n is even. We
show that the change in the number of maximal bicliques
when a single edge is added to the graph can be as large as
3g(n − 2) ≈ 1.5 × 2n/2 , which is exponential in the number
of vertices in the graph. This shows that the addition of
even a single edge to the graph can lead to a large change
in the set of maximal bicliques in the graph. We further
show that this bound is tight for the case of the addition
of a single edge – the largest possible change in the set of
maximal bicliques upon adding a single edge is 3g(n − 2).
For the case when more edges can be added to the graph,

2

the addition of a batch of 100 edges, while the baseline
algorithm took more than 30 minutes.
1.2

Fig. 1: Change in maximal bicliques when the graph changes
from G1 to G2 due to the addition of edge set H =
{{a, y}, {c, x}}. Note that each maximal biclique of G1 is
subsumed by a larger maximal biclique in G2 , and there is
one new maximal biclique in G2 .

it is easy to see that the maximum possible change is no
larger than 2g(n).
Enumeration Algorithm: From our analysis, it is clear that
the magnitude of change in the set of maximal bicliques
in the graph can be as large as exponential in n in the
worst case. On the flip side, the magnitude of change can
be as small as 1 – for example, consider the case when a
newly arriving edge connects two isolated vertices in the
graph. Thus, there is a wide range of values the magnitude
of change can take. When the magnitude of change is
very large, an algorithm that enumerates the change must
inevitably pay a large cost, if only to enumerate the change.
On the other hand, when the magnitude of change is small,
it will ideally pay a smaller cost. This motivates our search
for a change-sensitive algorithm whose computational cost
for enumerating the change is proportional to the magnitude of the change in the set of maximal bicliques.
We present a change-sensitive algorithm, DynamicBC,
for enumerating the new maximal bicliques and subsumed
maximal bicliques, when a set of new edges H are added
to the bipartite graph G. The algorithm DynamicBC has
two parts, NewBC, for enumerating new maximal bicliques,
and SubBC, for enumerating subsumed maximal bicliques.
When a batch of new edges H of size ρ is added to the
graph, the time complexity of NewBC for enumerating Υnew ,
the set of new maximal bicliques, is O(∆2 ρ|Υnew |) where
∆ is the maximum degree of the graph after update. The
time complexity of SubBC for enumerating Υdel , the set
of subsumed bicliques, is O(2ρ |Υnew |). To the best of our
knowledge, these are the first provably change-sensitive
algorithms for maintaining maximal bicliques in a dynamic
graph.
Experimental Evaluation: We present an empirical evaluation of our algorithms on real bipartite graphs with million of nodes. Our results shows that the performance of
our algorithms are orders of magnitude faster than current
approaches. For example, on the actor-movie-1 graph
with 640K vertices and 1.4M edges, our algorithm took
about 30 milliseconds for computing the change due to

Related Work

Maximal Biclique enumeration (MBE) on a static graph:
There has been substantial prior work on enumerating maximal bicliques from a static graph. Alexe et al. [5] propose
an algorithm for MBE from a static graph based on the
consensus method, whose time complexity is proportional
to the size of the output (number of maximal bicliques
in the graph) - termed as output-sensitive algorithm. Liu et
al. [22] propose an algorithm for MBE based on depthfirst-search (DFS). Damaschke [7] propose an algorithm for
bipartite graphs with a skewed degree distribution. Gély et
al. [13] propose an algorithm for MBE through a reduction
to maximal clique enumeration (MCE). However, in their
work, the number of edges in the graph used for enumeration increases significantly compared to the original graph.
Makino & Uno [24] propose an algorithm for MBE based
on matrix multiplication, which provides the current best
time complexity for dense graphs. Eppstein [12] proposes
a linear time algorithm for MBE when the input graph has
bounded arboricity. Other works on sequential algorithm for
MBE on a static graph include [9], [10]. [25], [33], [31] present
parallel algorithms for MBE and MCE for the MapReduce
framework. [20] show a correspondence between closed
itemsets in a transactional database and maximal cliques in
an appropriately defined graph.
Dense Structures from Dynamic Graphs: There have
been some prior works related to maintenance of dense
structures similar to maximal bicliques in dynamic graphs.
Kumar et al. [18] define (i, j)-core which is a biclique with i
vertices in one partition and j vertices in another partition.
In their work, the authors propose a dynamic algorithm
for extracting non-overlapping maximal set of (i, j)-cores
for interesting communities. [30], [21], [16] present methods
for maintaining k -cores and k -trusses in a dynamic graph,
and [8] present algorithms for maintaining maximal cliques
in a dynamic graph.
Roadmap: The remaining section are organized as follows. We present definitions and preliminaries in Section 2.
Then we describe our algorithms in Section 3, results on the
size of change in the set of maximal bicliques in Section 4,
and experimental results in Section 5.

2

P RELIMINARIES

Let V (G) denote the set of vertices of G and E(G) the set
of edges in G. Let n and m denote the number of vertices
and number of edges in G respectively. Let ΓG (u) denote
the set of vertices adjacent to vertex u in G. If the graph G
is clear from the context, we use Γ(u) to mean ΓG (u). For
an edge e = (u, v) ∈ E(G), let G − e denote the graph after
deleting e ∈ E(G) from G and G + e denote the graph after
adding e ∈
/ E(G) to G. For a set of edges H , let G + H
(G − H ) denote the graph obtained after adding (deleting)
H to (from) E(G). Similarly, for a vertex v ∈
/ V (G), let G + v
denote the graph after adding v to G and for a vertex v ∈
V (G), let G − v denote the graph after deleting v and all its
adjacent edges from E(G). Let ∆(G) denote the maximum

3

For graph G and set of edges H , we use Υnew to mean
Υnew (G, G + H), and Υdel to mean Υdel (G, G + H).
Algorithm 1: DynamicBC(G, H, BC(G))
Input: G - Input bipartite graph, H - Edges being
added to G, BC(G)
Output: Υ : the union of set of new maximal bicliques
and subsumed bicliques
new
1 Υ
← NewBC(G, H)
del
2 Υ
← SubBC(G, H, BC(G), Υnew )
new
3 Υ ← Υ
∪ Υdel
Fig. 2: Cocktail-party graph on 6 vertices CP (3)
degree of a vertex in G and δ(G) the minimum degree of a
vertex in G.
Definition 1 (Change-Sensitive Algorithm). An algorithm for
a dynamic graph stream is called change-sensitive if its time
complexity of enumerating the change in a graph property is
proportional to the magnitude of change.
Results for a static graph. In [27], Prisner presented the
following result on the number of maximal bicliques in a
bipartite graph with n vertices.

We first present Algorithm NewBC for enumerating new
cliques in Section 3.1, and Algorithm NewBC for enumerating subsumed cliques in Section 3.2. The main result on
the time complexity of DynamicBC is summarized in the
following theorem.
Theorem 3. DynamicBC is a change-sensitive algorithm for
enumerating the change in the set of maximal bicliques, with time
complexity O(∆2 ρ|Υnew |+2ρ |Υnew |) where ∆ is the maximum
degree of a vertex in G + H and ρ is the size of H .
3.1

Enumerating New Maximal Bicliques

Theorem 1 (Theorem 2.1 [27]). Every bipartite graph with n
n
vertices contains at most 2 2 ≈ 1.41n maximal bicliques, and the
only extremal (maximal) bipartite graphs are the graphs CP (k).
Here, CP (k) denotes the cocktail-party graph which
is a bipartite graph with k vertices in each partition
where V (CP (k)) = {a1 , a2 , . . . , ak , b1 , b2 , . . . , bk } and
E(CP (k)) = {(ai , bp ) : i 6= p} [27]. See Figure 2 for an
example.
As a subroutine, we use an algorithm for enumerating
maximal bicliques from a static undirected graph, whose
runtime is proportional to the number of maximal bicliques.
There are a few algorithms of this kind [5], [22], [35]. We use
the following result due to Liu et al. [22] as it provides best
possible time and space complexity.
Theorem 2 (Liu et al., [22]). For a graph G with n vertices,
m edges, maximum degree ∆, and number of maximal bicliques
µ, there is an algorithm MineLMBC for enumerating maximal bicliques in G with time complexity O(n∆µ) and space complexity
O(m + ∆2 ).

MineLMBC is depth-first-search (DFS) based algorithm
for enumerating maximal bicliques of a static graph G =
(V, E). It takes as input the graph G and the size threshold
s. The algorithm enumerates all maximal bicliques of G with
size of each partition at least s. Clearly, by setting s = 1, the
algorithm enumerates all maximal bicliques of G.

3 C HANGE -S ENSITIVE A LGORITHM FOR M AXIMAL
B ICLIQUES
In this section, we present a change-sensitive algorithm
DynamicBC for enumerating the change in the set of maximal bicliques. The algorithm has two parts : (1) Algorithm NewBC for enumerating new maximal bicliques, and
(2) Algorithm SubBC for enumerating subsumed bicliques.

Fig. 3: The original graph G has 4 maximal bicliques. When
new edges in H (in dotted line) are added to G, all maximal
bicliques in G remain maximal in G + H and only one
maximal biclique is newly formed (< {a3 , a4 }, {b3 , b4 } >).
Let G0 denote the graph G + H . A baseline algorithm for
enumerating new maximal bicliques in G0 is to (1) enumerate all maximal bicliques in G, (2) enumerate all maximal
bicliques in G0 both using an output-sensitive algorithm
such as [22], and then (3) compute BC(G0 ) \ BC(G). However, this is not change-sensitive, since we need to compute
all maximal bicliques of G0 each time, but it is possible
that most of the maximal bicliques in G0 are not new.
For example, see Fig. 3. We next present an approach that
overcomes this difficulty.
For each new edge e ∈ H , let BC 0 (e) denote the set of
maximal bicliques in G0 containing edge e.
Lemma 1. Υnew = ∪e∈H BC 0 (e).
Proof. Each biclique in Υnew must contain at least one edge
from H . To see this, consider a biclique b ∈ Υnew . If b did not
contain an edge from H , then b is also a maximal biclique
in G, and hence cannot belong to Υnew . Hence, b ∈ BC 0 (e)
for some edge e ∈ H , and b ∈ ∪e∈H BC 0 (e). This shows that
Υnew ⊆ ∪e∈H B 0 (e).

4

Fig. 4: Construction of G0e from G0 = G + H when a set of
new edges H = {e, h} is added to G. A = ΓG0 (v) = {u, x}
and B = ΓG0 (u) = {v, y}.
Next consider a biclique b ∈ ∪e∈H BC 0 (e). It must be
the case that b ∈ BC 0 (h) for some h in H . Thus b is a
maximal biclique in G + H , and b contains edge h ∈ H
and b cannot be a biclique in G. Thus b ∈ Υnew . This shows
that ∪e∈H BC 0 (e) ⊆ Υnew .
Next, for each edge e = (u, v) ∈ H , we present an
efficient way to enumerate all bicliques in BC 0 (e) through
enumerating maximal bicliques in a specific subgraph G0e of
G0 , constructed as follows. Let A = ΓG0 (u) and B = ΓG0 (v).
Then G0e = (A, B, E 0 ) is a subgraph of G0 induced by
vertices in A and B . See Fig. 4 for an example of the
construction of G0e .
Lemma 2. For each e ∈ H , BC 0 (e) = BC(G0e )
Proof. First we show that BC 0 (e) ⊆ BC(G0e ). Consider a
biclique b = (X, Y ) in BC 0 (e). Let e = (u, v). Here b contains
both u and v . Suppose that u ∈ X and v ∈ Y . According
to the construction G0e contains all the vertices adjacent to u
and all the vertices adjacent to v . And in b, all the vertices
in X are connected to all the vertices in Y . Hence, b is a
biclique in G0e . Also, b is a maximal biclique in G0 , and G0e
is an induced subgraph of G0 which contains all the vertices
of b. Hence, b is a maximal biclique in G0e .
Next we show that BC(G0e ) ⊆ BC 0 (e). Consider a biclique b0 = (X 0 , Y 0 ) in BC(G0e ). Clearly, b0 contains e as it
contains both u and v and b0 is a maximal biclique in G0e .
Hence, b0 is also a biclique in G0 that contains e. Now we
prove that b0 is also maximal in G0 . Suppose not, that there
is a vertex w ∈ V (G0 ) such that b0 can be extended with
w. Then, as per the construction of G0e , w ∈ V (G0e ) since w
must be adjacent to either u or v . Then, b0 is not maximal in
G0e . This is a contradiction. Hence, b0 is also maximal in G0 .
Therefore, b0 ∈ BC 0 (e).
Based on the above observation, we present our changesensitive algorithm NewBC (Algorithm 2). We use an outputsensitive algorithm for a static graph MineLMBC for enumerating maximal bicliques from G0e . Note that typically, G0e is
much smaller than G0 since it is localized to edge e, and
hence enumerating all maximal bicliques from G0e should
be relatively inexpensive.
Theorem 4. NewBC enumerates the set of all new bicliques
arising from the addition of H in time O(∆2 ρ|Υnew |) where
∆ is the maximum degree of a vertex in G0 and ρ is the size of H .
The space complexity is O(|E(G0 )| + ∆2 ).
Proof. First we consider correctness of the algorithm. From
Lemma 1 and Lemma 2, we know that Υnew is enumerated
by enumerating BC(G0e ) for every e ∈ H . Our algorithm

Algorithm 2: NewBC(G, H)
Input: G - Input bipartite graph, H - Edges being
added to G
Output: bicliques in Υnew , each biclique output once
1 Consider edges of H in an arbitrary order
e1 , e2 , . . . , eρ
0
2 G ← G+H
3 for i = 1 . . . ρ do
4
e ← ei = (u, v)
5
G0e ← a subgraph of G0 induced by
ΓG0 (u) ∪ ΓG0 (v)
6
Generate bicliques of G0e using MineLMBC. For each
biclique thus generated, output b only if b does
not contain an edge ej for j < i

does this exactly, and use the MineLMBC algorithm for enumerating BC(G0e ).
For the runtime, consider that the algorithm iterates
over each edge e in H . In each iteration, it constructs a
graph G0e and runs MineLMBC(G0e ). Note that the number
of vertices in G0e is no more than 2∆, since it is the size
of the union of the edge neighborhoods of ρ edges in G0 .
The set of maximal bicliques generated in each iteration is a
subset of Υnew , therefore the number of maximal bicliques
generated from each iteration is no more than |Υnew |. From
Theorem 2, we have that the runtime of each iteration is
O(∆2 |Υnew |). Since there are ρ edges in H , the result on
runtime follows. For the space complexity, we note that the
algorithm does not store the set of new bicliques in memory
at any point. The space required to construct G0e is linear in
the size of G0 . From Theorem 2, the total space requirement
is O(|E(G0 )| + ∆2 ).
3.2

Enumerating Subsumed Maximal Bicliques

We now present a change-sensitive algorithm for enumerating BC(G) \ BC(G0 ) where G0 = G + H . Suppose a new
maximal biclique b of G0 subsumed a maximal biclique b0
of G. Note that b0 is also a maximal biclique in b − H . So,
one idea is to enumerate all maximal bicliques in b − H and
then check which among them is maximal in G. However,
checking maximality of a biclique is costly operation since
we need to consider neighborhood of every vertex in the
biclique. Another idea is to store the bicliques of the graph
explicitly and see which among the generated bicliques are
contained in the set of maximal bicliques of G. This is not
desirable either since large amount of memory is required
to store the set of all maximal bicliques of G.
A more efficient approach is to store the signatures
of the maximal bicliques instead of storing the bicliques
themselves. Then, we enumerate all maximal bicliques in
b − H and for each biclique generated, we compare the
signature of the generated biclique with the signatures of
the bicliques stored. An algorithm following this idea is
presented in Algorithm 3. In this algorithm we reduce the
cost of main memory by storing the signatures. We use a
standard hash function (such as 64 bit murmur hash 1 ) for
1. https://sites.google.com/site/murmurhash/

5

computing signatures of maximal bicliques. For computing
the signature, first we represent a biclique in canonical
form (vertices in first partition represented in lexicographic
order followed by vertices in another partition represented
in lexicographic order). Then we convert the string into
bytes, and apply hash function on the computed bytes.
The hash function returns signature as output. By storing
the signatures instead of maximal bicliques, we are able to
check whether a maximal biclique from b − H is contained
in the set of maximal bicliques of G by comparing their hash
values. Thus we pay much less cost in terms of memory by
storing the signatures of bicliques.
Now we prove that Algorithm 3 indeed enumerates all
maximal bicliques of b − H .
Lemma 3. In Algorithm 3, for each b ∈ Υnew , S after Line 14
contains all maximal bicliques in b − H .
Proof. First observe that, removing H from b is equivalent
to removing those edges in H which are present in b. Hence,
computing maximal bicliques in b−H reduces to computing
maximal bicliques in b − H1 where H1 is the set of all edges
in H which are present in b.
We use induction on the number of edges k in H1 .
Consider the base case, when k = 1. H1 contains a single
edge e1 = {u, v}. Clearly, b − H1 has two maximal bicliques
b \ {u} and b \ {v}. Suppose, that the set H1 is of size k . Our
inductive hypothesis is that all maximal bicliques in b − H1
are enumerated. Consider H10 = {e1 , e2 , ..., ek , ek+1 } with
k + 1 edges. Now each maximal biclique b0 in b − H1 either
remains maximal within b − H10 (if at least one endpoint
of ek+1 is not in b0 ) or generates two maximal bicliques in
b − H10 (if both endpoints of ek+1 are in b0 ). Thus, for each
b ∈ Υnew , S after Line 14 contains all maximal bicliques
within b − H .
Now we show that the algorithm described above is a
change-sensitive algorithm for enumerating all elements of
Υdel when the number of edges ρ in H is constant.
Theorem 5. Algorithm 3 enumerates all bicliques in Υdel =
BC(G) − BC(G + H) using time O(2ρ |Υnew |) where ρ is the
number of edges in H . The space complexity of the algorithm is
O(|E(G0 )| + |V (G0 )| + ∆2 + |BC(G)|).
Proof. We first show that every biclique b0 enumerated by
the algorithm is indeed a biclique in Υdel . Note that b0 is a
maximal biclique in G, due to explicitly checking the condition. Further, b0 is not a maximal biclique in G+H , since it is
a proper subgraph of b, a maximal biclique in G + H . Next,
we show that all bicliques in Λdel are enumerated. Consider
any subsumed biclique b0 ∈ Λdel . It must be contained
within b \ H , where b is a maximal biclique within Λnew .
Moreover, b0 will be a maximal biclique within b \ H , and
will be enumerated by the algorithm according to Lemma 3.
For the time complexity we show that for any b ∈ Υnew ,
the maximum number of maximal bicliques in b − H is
2ρ using induction on ρ. Suppose ρ = 1 so that H contains a single edge, say e1 = (u, v). Then, b − H has
two maximal bicliques, b \ {u} and b \ {v}, proving the
base case. Suppose that for any set H of size k , it was
true that b − H has no more than 2k maximal bicliques.
Consider a set H 00 = {e1 , e2 , . . . , ek+1 } with k + 1 edges.

Algorithm 3: SubBC(G, H, BC, Υnew )
Input: G - Input bipartite graph
H - Edge set being added to G
BC - Set of maximal bicliques in G
Υnew - set of new maximal bicliques in G + H
Output: All cliques in Υdel = BC(G) \ BC(G + H)
del
1 Υ
←∅
new
2 for b ∈ Υ
do
3
S ← {b}
4
for e = (u, v) ∈ E(b) ∩ H do
5
S0 ← φ
6
for b0 ∈ S do
7
if e ∈ E(b0 ) then
8
b1 = b0 \ {u} ; b2 = b0 \ {v}
9
S 0 ← S 0 ∪ b1 ; S 0 ← S 0 ∪ b2
10
11
12

else
S 0 ← S 0 ∪ b0
/* S 0 contains all the maximal
bicliques in b − {e1 , e2 , ..., ek } where
{e1 , e2 , ..., ek } ⊆ E(b) ∩ H are
considered so far.
*/

13
14
15
16
17

S ← S0
for b0 ∈ S do
if b0 ∈ BC then
Υdel ← Υdel ∪ b0

Let H 0 = {e1 , e2 , . . . , ek }. Subgraph b − H 00 is obtained
from b − H 0 by deleting a single edge ek+1 . By induction,
we have that b − H 0 has no more than 2k maximal bicliques.
Each maximal biclique b0 in b − H 0 either remains a maximal
biclique within b − H 00 (if at least one endpoint of ek+1 is
not in b0 ), or leads to two maximal bicliques in b − H 00 (if
endpoints of ek+1 are in different bipartition of b0 ). Hence,
the number of maximal bicliques in b − H 00 is no more than
2k+1 , completing the inductive step.
Following this, for each biclique b ∈ Υnew , we need to
check for maximality for no more than 2ρ bicliques in G.
This checking can be performed by checking whether each
such generated biclique in contained in the set BC(G) and
for each biclique, this can be done in constant time.
For the space bound, we first note that in Algorithm 3,
enumerating maximal bicliques within b − H consumes
space O(|E(G0 )| + ∆2 ), and checking for maximality can be
done in space linear in size of G. However, for storing the
maximal bicliques in G takes O(|BC(G)|) space. Hence, for
these operations, the overall space-cost for each b ∈ Υnew is
O(|E(G0 )| + |V (G0 )| + ∆2 + |BC(G)|). The only remaining
space cost is the size of Υnew , which can be large. Note that,
the algorithm only iterates through Υnew in a single pass. If
elements of Υnew are provided as a stream from the output
of an algorithm such as NewBC, then they do not need to
be stored within a container, so that the memory cost of
receiving Υnew is reduced to the cost of storing a single
maximal biclique within Υnew at a time.

6

Algorithm 4: Decremental(G,H)
Input: G - Input bipartite graph, H - Edges being
deleted from G
Output: Υnew (G, G − H) ∪ Υdel (G, G − H)
new
1 Υ
← φ; Υdel ← φ; G00 ← G − H
del
2 Υ
← NewBC(G00 , H)
new
3 Υ
← SubBC(G00 , H, BC(G00 ), Υdel )
new
4 returnΥ
∪ Υdel

3.3

Decremental and Fully Dynamic Cases

We now consider the maintenance of maximal bicliques
in the decremental case, when edges are deleted from the
graph. This case can be handled using a reduction to the
incremental case. We show that the maintenance of maximal
bicliques due to deletion of a set of edges H from a bipartite graph G is equivalent to the maintenance of maximal
bicliques due to addition of H to the bipartite graph G − H .
Lemma 4. Υnew (G, G − H) = Υdel (G − H, G) and
Υdel (G, G − H) = Υnew (G − H, G)
Proof. Note that Υnew (G, G − H) is the set of all bicliques
that are maximal in G − H , but not in G. By definition,
this is equal to Υdel (G − H, G). Similarly we can show that
Υdel (G, G − H) = Υnew (G − H, G).
Based on the above lemma, an algorithm for the decremental case is presented in Algorithm 4. For the fully
dynamic case, where we need to consider both the addition
and deletion of edges, we first compute the changes due to
addition of edges, followed by changes due to deletion of
edges.

4

M AGNITUDE OF CHANGE IN B ICLIQUES

We consider the maximum change in the set of maximal
bicliques when a set of edges is added to the bipartite graph.
Let λ(n) denote the maximum size of Υ(G, G + H) taken
over all n vertex bipartite graphs G and edge sets H . We
derive the following upper bound on the maximum size of
Υ(G, G + H) in the following Lemma:
Lemma 5. λ(n) ≤ 2g(n).
Proof. Note that, for any bipartite graph G with n vertices
and for any new edge set H it must be true that |BC(G)| ≤
g(n) and |BC(G + H)| ≤ g(n). Since |Υnew (G, G + H)| ≤
|BC(G + H)| and |Υdel (G, G + H)| ≤ |BC(G)|, it follows
that |Υ(G, G + H)| ≤ |BC(G + H)| + |BC(G)| ≤ 2g(n).
Next we analyze the upper bound of |Υ(G, G + e)| in the
following when an edge e ∈
/ E(G) is added to G.

Fig. 5: Construction showing the changes in the set of
maximal bicliques when a new edge is added. G is in the
left on n = 6 vertices. G00 consists of vertices in L0 and R0
and edges among them to make it a cocktail-party graph. G0
in the right is obtained by adding edge e = (u, v) to G.
large as 3g(n − 2) in Lemma 9 we prove that the size of
Υ(G, G + e) is at most 3g(n − 2).
Lemma 6. For any even integer n > 2 there exists a bipartite
graph G on n vertices and an edge e = (u, v) ∈
/ E(G) such that
|Υ(G, G + e)| = 3g(n − 2).
Proof. We use proof by construction. Consider bipartite
graph G = (L, R, E) constructed on vertex set U ∪ V with
n vertices such that |L| = |R| = n/2. Let u ∈ L and v ∈ R
be two vertices and let L0 = L \ {u} and R0 = R \ {v}.
Let G00 denote the induced subgraph of G on vertex sets L0
and R0 . In our construction, G00 is CP ( n2 − 1). In graph G,
in addition to the edges in G00 , we add an edge from each
vertex in R0 to u and an edge from each vertex in L0 to v .
We add edge e = (u, v) to G to get graph G0 = G + e (see
Fig. 5 for construction). We claim that the size of Υ(G, G0 )
is 3g(n − 2).
First, we note that the total number of maximal bicliques
in G is 2g(n−2). Each maximal biclique in G contains either
vertex u or v , but not both. The number of maximal bicliques
that contain vertex u is g(n−2), since each maximal biclique
in G00 leads to a maximal biclique in G by adding u. Similarly, the number of maximal bicliques in G that contains v
is g(n − 2), leading to a total of 2g(n − 2) maximal bicliques
in G.
Next, we note that the total number of maximal bicliques
in G0 is g(n − 2). To see this, note that each maximal biclique
in G0 contains both vertices u and v . Further, for each
maximal biclique in G00 , we get a corresponding maximal
biclique in G0 by adding vertices u and v . Hence the number
of maximal bicliques in G0 equals the number of maximal
bicliques in G00 , which is g(n − 2).
No maximal biclique in BC(G) contains both u and
v , while every maximal biclique in G0 contains both u
and v . Hence, BC(G) and BC(G0 ) are disjoint sets, and
|Υ(G, G0 )| = |BC(G)| + |BC(G0 )| = 3g(n − 2).

Theorem 6. For an integer n ≥ 2, a bipartite graph G =
(L, R, E) with n vertices, and any edge e = (u, v) ∈
/ E(G), u ∈
U, v ∈ V , the maximum size of Υ(G, G + e) is 3g(n − 2), and
for each even n, there exists a bipartite graph that achieves this
bound.

Lemma 7. If e = (u, v) ∈
/ E(G) is inserted to G where u ∈
L, v ∈ R, all new maximal bicliques in G + e must contain e.

We prove this theorem in the following two lemmas. In
Lemma 6 we prove that the size of Υ(G, G + e) can be as

Proof. Proof by contradiction. Assume that there is a new
maximal biclique b = (b1 , b2 ) in BC(G + e) − BC(G) that

Now we will prove a few results that we will use in
proving Lemma 9.

7

does not contain e. Then b must be present in G but is not
maximal in G, and there must be another vertex w ∈ L
(or R) that can be added to b while remaining a biclique.
Clearly, w can be added to biclique b in G + e also, so that b
is not maximal in G + e, contradicting our assumption.
Lemma 8. If e = (u, v) is added to G, each biclique b ∈
BC(G) − BC(G + e) contains either u or v .
Proof. Proof by contradiction. Suppose there is maximal
biclique b = (b1 , b2 ) in BC(G) − BC(G + e) that contain
neither u nor v . Then, b must be maximal biclique in G. Since
b is not maximal biclique in G + e, b is contained in another
maximal biclique b0 = (b01 , b02 ) in G + e. From Lemma 7, b0
must contain edge e = (u, v), and hence, both vertices u and
v . Since b0 is a biclique, every vertex in b02 is connected to u
in G0 . Hence, every vertex in b2 is connected to u even in G.
Therefore, b ∪ {u} is a biclique in G, and b is not maximal in
G, contradicting our assumption.
Observation 1. For a bipartite graph G = (L, R, E) and a
vertex u ∈ V (G), the number of maximal bicliques that contains
v is at most g(n − 1).
Proof. Suppose, u ∈ L. Then each maximal biclique b in G
that contains u, corresponds to a unique maximal biclique in
G − {u}. Such maximal bicliques can be derived from b by
deleting u from b. As the maximum number of maximal
bicliques in G − {u} is g(n − 1), maximum number of
maximal bicliques in G can be no more than g(n − 1).
Observation 2. The number of maximal bicliques containing a
specific edge (u, v) is at most g(n − 2).
Proof. Consider an edge (u, v) ∈ E(G). Let vertex set
V 0 = (ΓG (u)∪ΓG (v))−{u, v}, and let G0 be the subgraph of
G induced by V 0 . Each maximal biclique b in G that contains
edge (u, v) corresponds to a unique maximal biclique in
G0 by simply deleting vertices u and v from b. Also, each
maximal biclique b0 in G0 corresponds to a unique maximal
biclique in G that contains (u, v) by adding vertices u and
v to b0 . Thus, there is a bijection between the maximal
bicliques in G0 and the set of maximal bicliques in G that
contains edge (u, v). The number of maximal bicliques in
G0 can be at most g(n − 2) since G0 has no more than (n − 2)
vertices, completing the proof.
Lemma 9. For a bipartite graph G = (L, R, E) on n vertices
and edge e = (u, v) ∈
/ E(G), the size of Υ(G, G + e) can be no
larger than 3g(n − 2).
Proof. Proof by contradiction. Suppose there exists a bipartite graph G = (L, R, E) and edge e ∈
/ E(G) such that
|Υ(G, G+e)| ≥ 3g(n−2). Then either |BC(G+e)−BC(G)| ≥
g(n − 2) or |BC(G) − BC(G + e)| ≥ 2g(n − 2).
Case 1: |BC(G + e) − BC(G)| ≥ g(n − 2): This means
that total number of new maximal bicliques formed due to
addition of edge e is larger than g(n − 2). From Lemma 7,
each new maximal biclique formed due to addition of e
must contain e. From Observation 2, the total number of
maximal bicliques in an n vertex bipartite graph containing
a specific edge can be at most g(n − 2). Thus, the number
of new maximal bicliques after adding edge e is at most
g(n − 2), contradicting our assumption.

Case 2: |BC(G)−BC(G+e)| ≥ 2g(n−2): Using Lemma 8,
each maximal biclique b ∈ BC(G) − BC(G + e) must contain
either u or v , but not both. Suppose that b contains u but
not v . Then, b must be a maximal biclique in G − v . Using
Observation 1, we see that the number of maximal bicliques
in G − v that contains a specific vertex u is no more than
g(n − 2). In a similar way, the number of possible maximal
bicliques that contain v is at most g(n − 2). Therefore, the
total number of maximal bicliques in BC(G) − BC(G + e) is
at most 2g(n − 2), contradicting our assumption.
Combining Lemma 5, Theorem 6 and using the fact that
3g(n − 2) = 1.5g(n) for even n, we obtain the following
when n is even:
Theorem 7. 1.5g(n) ≤ λ(n) ≤ 2g(n)

5

E XPERIMENTAL E VALUATION

In this section, we present results of an experimental evaluation of our algorithms.
5.1

Data

We consider the following real-world bipartite graphs in
our experiments. A summary of the datasets is presented in
Table 1. In the actor-movie [1] graph, vertices consist of
actors in one bipartition and movies in another bipartition.
There is an edge between an actor and a movie if the
actor played in that movie. In the dblp-author [2] graph,
vertices consist of authors in one partition and the publications in another partition. Edges connect authors to their
publications. In the epinions-rating [3] graph, vertices
consist of users in one partition and products in another
partition. There is an edge between a user and a product if
the user rated the product. Also, the edges have timestamps
of their creation. In the flickr-membership [4] graph,
vertices consists of users and groups. There is an edge
between a user and a group if that user is a member of
that group.
We converted the above graphs into dynamic graphs
by creating edge streams as follows: For actor-movie,
dblp-author, and flickr-membership we created initial graphs by retaining each edge in the original graph with
probability 0.1 and deleting the rest. Then the deleted edges
are added back as an edge stream, until the original graph is
reached. We named the initial graphs as actor-movie-1,
dblp-author-1, and flickr-membership-1. For the
epinions-rating graph, we created the initial graph by
retaining initial 10% edges of the original graph according
to their timestamps, and considered rest of the edges for
creating the edge stream in timestamp ordering. We named
the initial graph as epinions-rating-init. In Table 1,
the number of edges of the initial graph is in the column
Edges(initial) and the number of edges when we end
the experiment is in column Edges(final).
5.2

Experimental Setup and Implementation Details

We implemented our algorithms using Java on a 64-bit Intel(R) Xeon(R) CPU clocked at 3.10 Ghz and 8G DDR3 RAM
with 6G heap memory space. Unless otherwise specified, we
considered batches of size 100.

8

TABLE 1: Summary of Graphs Used
Dataset
actor-movie-1
dblp-author-1
epinions-rating-init
flickr-membership-1

Nodes

Edges(initial)

Edges(final)

Edges(original graph)

Avg. deg.(original graph)

639286
6851776
996744
895589

146917
864372
1366832
855179

1470404
8649016
1631832
1355179

1470404
8649016
13668320
8545307

6
3
31
35

0.04

Initial-graph

DynamicBC

BaselineBC

actor-movie-1
dblp-author-1
epinion-rating-init
flickr-membership-1

30 ms.
20 ms.
3.5 sec.
0.5 sec.

> 30 min.
> 20 hours
> 10 hours
1 hour

DynamicBC

0.035
0.03
0.025
0.02
0.015
0.01
0.005
0
1-1K

4K-5K
8K-9K 12K-13K
Iteration range

Avg. comp. time in range

Avg. comp. time in range

TABLE 2: Comparison with Baseline: computation time for adding a single batch of size 100

0.03

0.02
0.015
0.01
0.005
0
1-1K

DynamicBC

18
16
14
12
10
8
6
4
1-.25K

1K-1.25K
Iteration range

39K-40K
Iteration range

77K-78K

(b) dblp-author-1

2.5K-2.6K

Avg. comp. time in range

Avg. comp. time in range

(a) actor-movie-1
20

DynamicBC

0.025

7
6

DynamicBC

5
4
3
2
1
0
1-1K

2K-3K
Iteration range

4K-5K

(d) flickr-membership-1

(c) epinions-rating-init

Fig. 6: Computation time (in sec.) for enumerating the change in maximal bicliques, per batch of edges.
Metrics: We evaluate our algorithms using the following
metrics: (1) computation time for new maximal bicliques
and subsumed bicliques when a set of edges are added,
(2) change-sensitiveness, that is, the total computation time
as a function of the size of change. We measure the size
of change as the sum of the total number of edges in the
new maximal bicliques and the subsumed bicliques, and
(3) space cost, that is the memory used by the algorithm
for storing the graph, and other data structures used by

the algorithm, and (4) cumulative computation time for
different batch sizes, that is the cumulative computation
time from the initial graph to the final graph while using
different batch size.
5.3

Discussion of Results

Comparison with Baseline. We compared the performance
of our algorithm, DynamicBC, with a baseline algorithm
for maintaining maximal bicliques, we have implemented

0.04
0.035
0.03
0.025
0.02
0.015
0.01
0.005
0

NewBC
SubBC

K

0K 13
K
-1 K1
3K 6K 9K 12
14K

7K

Avg. comp. time in range

Avg. comp. time in range

9

0.03
0.025
0.02
0.015
0.01
0.005
0

Iteration range

K
5K -2K 2.6
K 1.2
K K5
5
.2
5
7
12.
1K 1.

Iteration range

(c) epinions-rating-init

(b) dblp-author-1
Avg. comp. time in range

Avg. comp. time in range

NewBC
SubBC

1K 1K 1K 1K 8K
-3 -4 -6 -7 -7
K K
K K
K
30 40 60 70 77
Iteration range

(a) actor-movie-1
20
18
16
14
12
10
8
6
4
2
0

NewBC
SubBC

7
6
5

NewBC
SubBC

4
3
2
1
0

2K -3K -4K -5K
1K K2K 3K 4K
11

Iteration range

(d) flickr-membership-1

Fig. 7: Computation time (in sec.) broken down into time for new and subsumed bicliques
algorithm that we call BaselineBC. The baseline algorithm
computes Υ(G, G + H) by (1) Enumerating BC(G),
(2) Enumerating BC(G + H), and (3) computing the
difference of the two. We use MineLMBC [22] for enumerating
bicliques from a static graph. Table 2 shows a comparison
of the runtimes of DynamicBC and BaselineBC. From the
table, it is clear that DynamicBC is faster than BaselineBC
by two to three orders of magnitude. For instance, for
adding a single batch of size 100 to actor-movie-1,
BaselineBC takes more than 30 min., whereas DynamicBC
takes around 30 ms.
Computation Time per Batch of Edges: Let an
“iteration” denote the addition of a single batch of edges.
Fig. 6 shows the computation time per iteration versus
iteration number. From the plots, we observe that the
computation time increases as the iteration increases.
This trend is consistent with predictions. Note that as
computation progresses, the number of edges in the graph
increases, and note that the the computation time is
proportional to the size of graph as well as size of change
(Theorem 3). In Fig. 6(c) we see that computation time
decreases suddenly and then again increases. This may
seem anomalous, but is explained by noting that in these
cases, the magnitude of change decreases in those iterations,

and then increases thereafter.
In Fig. 7, we show the breakdown of the computation
time of DynamicBC into time taken for enumerating new
cliques (NewBC) and for enumerating subsumed cliques
(SubBC). Observe that the computation time increases for
both new maximal bicliques and subsumed bicliques as
more batches are added. This is because the graph becomes
denser when more batches are added and the time taken
to compute the change increases, consistent with Theorem 3.
Change-Sensitiveness: Fig. 8 shows the computation
time as a function of the size of change. We observe that
the computation time of DynamicBC is roughly proportional
to the size of change. The computation time of both
NewBC and SubBC increases as number of new maximal
bicliques and subsumed bicliques increases. Clearly, this
observation supports our theoretical analysis. In some plots
(Fig. 8(c),8(d)) we see a rapid increase in the computation
time with the size of change. This is because, when the
graph grows, memory consumption increases considerably
and this affects the computation time of the algorithm.
Space Cost: Fig. 9 shows the space cost of DynamicBC for
different graphs. As SubBC needs to maintain the maximal

0.08
0.07
0.06
0.05
0.04
0.03
0.02
0.01
0
1-10k

DynamicBC
20K-30K
Size range

40K-70K

Avg. comp. time in range

Avg. comp. time in range

10

100
DynamicBC
90
80
70
60
50
40
30
20
10
0
100K-1M
Size range

0.02
0.015
0.01
0.005
0
1-5K

DynamicBC
10K-15K
Size range

25K-35K

(b) dblp-author-1

100M-1B

Avg. comp. time in range

Avg. comp. time in range

(a) actor-movie-1

0.025

500
DynamicBC
450
400
350
300
250
200
150
100
50
0
100K-1M
Size range

100M-1B

(d) flickr-membership-1

(c) epinions-rating-init

Fig. 8: Computation time (in sec.) for total change vs. size of total change.
bicliques in memory for computing subsumed bicliques,
we report the space consumption in two cases: (1) when we
store the maximal bicliques in memory, (2) when we store
the signatures of bicliques in memory instead of storing
the bicliques. Signatures consume less memory than the
actual bicliques as the signatures have fixed size (64 bits
in our case using the murmur hash function) for different
sizes of bicliques. Therefore, memory consumption by the
algorithm that uses signatures should be smaller than the
algorithm that does not use signatures. The trend is also
clear in the plots. The difference in memory consumption is
not prominent during the initial iterations because, sizes of
maximal bicliques are much smaller during initial iterations
and therefore memory consumption is mainly due to the
graph that we maintain in memory. We are not showing the
space cost without hash for the third input graph because
the algorithm could not execute on the third input graph
without hashing, due to running out of memory.
Computation Time for Different Batch Size: Table 3
shows the cumulative computation time for different graphs
when we use different batch size. We observe that the
total computation time increases when increasing the batch
size. The reason for this trend is that the computation time
for subsumed cliques increases with increasing batch size,

while the computation time for the new maximal bicliques
remains almost same across different batch sizes. Note that,
the time complexity for SubBC has (in the worst case) an
exponential dependence on the batch size. Therefore, the
computation time for subsumed cliques tends to increase
with an increase in the batch size. However, with a very
small batch size (such as 1 or 10), the change in the maximal
bicliques is very small, and the overhead can be large.
Maintaining Large Maximal Bicliques:
We also
consider maintaining large maximal bicliques with
predefined size threshold s, where it is required that each
bipartition of the biclique has size at least s. For large
subsumed bicliques, we provide s in addition to other
inputs to SubBC as well. Table 4 shows the cumulative
computation time by varying the threshold size s from 1
to 6. Clearly, s = 1 means that we maintain all maximal
bicliques. As expected, the cumulative computation time
decreases significantly in most of the cases as the size
threshold s increases.

6

C ONCLUSION

In this work, we presented a change-sensitive algorithm
for enumerating changes in the set of maximal bicliques in

120

Avg. space cost in range

Avg. space cost in range

11

Without hash
with hash

100
80
60
40
20
0
1-1K

4K-5K
8K-9K
Iteration range

12K-13K

700

Without hash
with hash

600
500
400
300
200

100
1-1K 39K-40K
Iteration range

350

(b) dblp-author-1
Avg. space cost in range

Avg. space cost in range

(a) actor-movie-1
With hash

300
250
200
150
100
50
1-.25K

77K-78K

1K-1.25K
Iteration range

700

Without hash
With hash

600
500
400
300
200
100
0
1-1K

2.5K-2.6K

2K-3K
Iteration range

4K-5K

(d) flickr-membership-1

(c) epinion-rating-init
Fig. 9: Space cost (in MB)

TABLE 3: Total computation time (from the initial graph to the final graph) for different batch sizes
Initial-graph
actor-movie-1
dblp-author-1
epinion-rating-init
flickr-membership-1

batch-size-1

batch-size-10

batch-size-100

3.8 min. (3.3 + 0.5)
11.3 min. (9 + 2.3)
3.3 hours (3.1 + .2)
2.1 hours (1.9 + 0.2)

3.8 min. (2.8 + 1)
14.1 min. (8.8 + 5.3)
3.7 hours (3.1 + 0.6)
2.4 hours (1.9 + 0.5)

3.9 min. (2.9 + 1)
15.7 min. (8.3 + 7.4)
7 hours (3.2 + 3.8)
3 hours (2.1 + 0.9)

TABLE 4: Total computation time (from initial to final graph) by varying the threshold size s
Initial-graph
actor-movie-1
dblp-author-1
epinion-rating-init
flickr-membership-1

s=1

s=2

s=3

s=4

s=5

s=6

203 sec.
947 sec.
7 hours
3 hours

124 sec.
531 sec.
6.5 hours
2.5 hours

105 sec.
445 sec.
6.3 hours
2.3 hours

100 sec.
403 sec.
6 hours
2.1 hours

103 sec.
399 sec.
5.5 hours
1.9 hours

98 sec.
400 sec.
5 hours
1.6 hours

dynamic graph. The performance of this algorithm is proportional to the magnitude of change in the set of maximal
bicliques – when the change is small, the algorithm runs
faster, and when the change is large, it takes a proportionally
longer time. We present near-tight bounds on the maximum
possible change in the set of maximal bicliques, due to a
change in the set of edges in the graph. Our experimental
evaluation shows that the algorithm is efficient in practice,
and scales to graphs with millions of edges. This work leads

to natural open questions (1) Can we design more efficient algorithms for enumerating the change, especially for
enumerating subsumed cliques? (2) Can we parallelize the
algorithm for enumerating the change in maximal bicliques?

R EFERENCES
[1]

Actor movies network dataset – KONECT.
http://konect.
uni-koblenz.de/networks/actor-movie, Oct. 2016.

12

[2]
[3]
[4]
[5]
[6]

[7]
[8]
[9]
[10]
[11]

[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]

[21]
[22]
[23]
[24]
[25]
[26]

[27]
[28]

Dblp network dataset – KONECT. http://konect.uni-koblenz.de/
networks/dblp-author, Oct. 2016.
Epinions product ratings network dataset – KONECT. http://
konect.uni-koblenz.de/networks/epinions-rating, Oct. 2016.
Flickr network dataset – KONECT. http://konect.uni-koblenz.
de/networks/flickr-groupmemberships, Oct. 2016.
G. Alexe, S. Alexe, Y. Crama, S. Foldes, P. L. Hammer, and B. Simeone. Consensus algorithms for the generation of all maximal
bicliques. Discrete Applied Mathematics, 145(1):11–21, 2004.
A. Angel, N. Koudas, N. Sarkas, D. Srivastava, M. Svendsen,
and S. Tirthapura. Dense subgraph maintenance under streaming
edge weight updates for real-time story identification. The VLDB
Journal, pages 1–25, 2013.
P. Damaschke. Enumerating maximal bicliques in bipartite graphs
with favorable degree sequences. Information Processing Letters,
114(6):317–321, 2014.
A. Das, M. Svendsen, and S. Tirthapura. Change-sensitive algorithms for maintaining maximal cliques in a dynamic graph. arXiv
preprint arXiv:1601.06311, 2016.
V. M. Dias, C. M. De Figueiredo, and J. L. Szwarcfiter. Generating
bicliques of a graph in lexicographic order. Theoretical Computer
Science, 337(1):240–248, 2005.
V. M. Dias, C. M. de Figueiredo, and J. L. Szwarcfiter. On the
generation of bicliques of a graph. Discrete Applied Mathematics,
155(14):1826–1832, 2007.
A. C. Driskell, C. An, J. G. Burleigh, M. M. McMahon, B. C.
O’Meara, and M. J. Sanderson. Prospects for building the tree of
life from large sequence databases. Science, 306(5699):1172–1174,
2004.
D. Eppstein. Arboricity and bipartite subgraph listing algorithms.
Information processing letters, 51(4):207–211, 1994.
A. Gély, L. Nourine, and B. Sadi. Enumeration aspects of maximal
cliques and bicliques. Discrete applied mathematics, 157(7):1447–
1459, 2009.
D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense
subgraphs in massive graphs. In VLDB, pages 721–732, 2005.
R. A. Hanneman and M. Riddle. Introduction to social network
methods. http://faculty.ucr.edu/∼hanneman/nettext/. Textbook
on the web.
X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu. Querying ktruss community in large and dynamic graphs. In SIGMOD, pages
1311–1322, 2014.
A. Java, X. Song, T. Finin, and B. L. Tseng. Why we twitter: An
analysis of a microblogging community. In WebKDD/SNA-KDD,
pages 118–138, 2007.
R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling
the Web for emerging cyber-communities. Computer networks,
31(11):1481–1493, 1999.
S. Lehmann, M. Schwartz, and L. K. Hansen. Biclique communities. Physical Review E, 78(1):016108, 2008.
J. Li, H. Li, D. Soh, and L. Wong. A correspondence between
maximal complete bipartite subgraphs and closed patterns. In
European Conference on Principles of Data Mining and Knowledge
Discovery, pages 146–156. Springer, 2005.
R. Li, J. X. Yu, and R. Mao. Efficient core maintenance in large
dynamic graphs. TKDE, 26(10):2453–2465, 2014.
G. Liu, K. Sim, and J. Li. Efficient mining of large maximal
bicliques. In Data warehousing and knowledge discovery, pages 437–
448. Springer, 2006.
D. Lo, D. Surian, K. Zhang, and E.-P. Lim. Mining direct antagonistic communities in explicit trust networks. In CIKM, pages
1013–1018, 2011.
K. Makino and T. Uno. New algorithms for enumerating all
maximal cliques. In SWAT, pages 260–272. 2004.
A. P. Mukherjee and S. Tirthapura. Enumerating maximal bicliques from a large graph using mapreduce. In IEEE BigData
Congress, pages 707–716, 2014.
N. Nagarajan and C. Kingsford. Uncovering genomic reassortments among influenza strains by enumerating maximal bicliques.
In Bioinformatics and Biomedicine, 2008. BIBM’08. IEEE International
Conference on, pages 223–230. IEEE, 2008.
E. Prisner. Bicliques in graphs i: Bounds on their number. Combinatorica, 20(1):109–117, 2000.
J. E. Rome and R. M. Haralick. Towards a formal concept analysis
approach to exploring communities on the world wide web. In
Formal Concept Analysis, volume 3403 of LNCS, pages 33–48. 2005.

[29] M. J. Sanderson, A. C. Driskell, R. H. Ree, O. Eulenstein, and
S. Langley. Obtaining maximal concatenated phylogenetic data
sets from large sequence databases. Mol. Biol. Evol., 20(7):1036–
1042, 2003.
[30] A. E. Sariyüce, B. Gedik, G. Jacques-Silva, K. Wu, and Ü. V.
Çatalyürek. Streaming algorithms for k-core decomposition.
PVLDB, 6(6):433–444, 2013.
[31] M. Svendsen, A. P. Mukherjee, and S. Tirthapura. Mining maximal
cliques from a large graph using mapreduce: Tackling highly
uneven subproblem sizes. J. Parallel Distrib. Comput., 79-80:104–
114, 2015.
[32] P. Valtchev, R. Missaoui, and R. Godin. A framework for incremental generation of closed itemsets. Discrete Applied Mathematics,
156(6):924–949, 2008.
[33] Y. Xu, J. Cheng, A. W.-C. Fu, and Y. Bu. Distributed maximal clique
computation. In IEEE BigData Congress, pages 160–167, 2014.
[34] C. Yan, J. G. Burleigh, and O. Eulenstein. Identifying optimal
incomplete phylogenetic data sets from sequence databases. Mol.
Phylogenet. Evol., 35(3):528–535, 2005.
[35] Y. Zhang, C. A. Phillips, G. L. Rogers, E. J. Baker, E. J. Chesler,
and M. A. Langston. On finding bicliques in bipartite graphs: a
novel algorithm and its application to the integration of diverse
biological data types. BMC bioinformatics, 15(1):1, 2014.

Apurba Das is a 4th year Ph.D. student in the
department of Computer Engineering at Iowa
State University. He received his Masters in
Computer Science from Indian Statistical Institute, Kolkata in 2011 and worked for 2 years
after that as a software developer at Ixia. His research interests are in the area of graph mining,
dynamic and streaming graph algorithms, and
large scale data analysis.

Dr. Srikanta Tirthapura received his Ph.D. in
Computer Science from Brown University in
2002, and his B.Tech. in Computer Science and
Engineering from IIT Madras in 1996. He is the
Kingland Professor of Data Analytics in the department of Electrical and Computer Engineering at Iowa State University. He has worked at
Oracle Corporation and is a recipient of the IBM
Faculty Award, and the Warren Boast Award
for excellence in Undergraduate Teaching. His
research interests include algorithms for largescale data analysis, stream computing, and cybersecurity.

