An Efficient Algorithm for Enumerating Maximal Bicliques from a Dynamically Growing Graph

摘要

Enumerating maximal biclique subgraphs from a graph is substantially important in many fields such as web mining, business intelligence, bioinformatics, social network analysis and so on. Although many previous studies have contributed much to efficient enumerating maximal biclique subgraphs from a graph, all of them proposed their algorithms based on a large static graph which remained unchanged in their application scenarios. In the real world, the social networks and other models have often dynamically changed thus either vertices or edges will be added to or removed from the corresponding graph. Therefore, these traditional approaches are not effective because they will repeat a complete enumeration process which has much repetitive work done in the previous enumeration. To reduce repetitive work and achieve high efficiency, we proposed a novel algorithm for enumerating maximal bicliques in a dynamically changed graph. Rather than to search the whole graph from first to last, we only search for newly created or reduced maximal bicliques based on the results enumerated before the change of the graph. In this paper, we proved the rightness of our methods and performed many simulations compared with other algorithms only for static graphs. The results demonstrated that our methods achieved high efficiency for dynamically changed graphs.