Contents 1 Introduction
Enumeration of maximal bicliques (also known as complete bipartite subgraph) can model several applications in the field of data mining including web mining, bioinformatics, and telecommunication usage data analysis [1]. However, the maximal biclique mining is a computationally demanding task [8] and the running time of the algorithm increases exponentially with respect to the number of vertices of the given graph. Several algorithms have been proposed for maximal biclique mining including Eppstein algorithm [11] and MICA [7]. Recently, the relationship between closed item set mining and maximal biclique has been well studied in [1] and LCM-MBC algorithm has been proposed for maximal biclique mining which extends the LCM closed item set mining algorithm [12] to generate maximal bicliques. However, these maximal biclique mining algorithms are limited to 2D data sets. The 2D data sets can be extended to 3D data sets by adding another dimension and enumeration of maximal bicliques from a 3D data set gives more useful information. One typical example is the web network data. Web communities are discovered by identifying maximal bicliques from web networks [1] and adding a dimension such as month/week gives rise to 3D data. In 2D version, the users are represented by vertices and their interactions are represented as edges [1]. Such a two-dimensional model of the scenario is not efficient as it does not focus on the strength of interaction. Also, if a weighted graph is used to counter this problem, it does not account for the pattern of the interaction with time. Therefore, if this is added as the third dimension (maybe in slices of month or year, as required), it will be useful in analyzing the density of interaction over a period. Thus, three-dimensional modeling of the interaction using 3D adjacency matrix provides more information and biclique patterns from 3D adjacency matrix represent the interactions as well as their strength over time. The same idea can be extended to mobile communication networks to discover interacting customer communities [1]. Like LCM-MBC algorithm, which extends the LCM algorithm, it is possible to use the existing 3D closed pattern mining algorithms such as CubeMiner [2], [6] and TRIAS [17] for 3D maximal biclique enumeration. However, this is not computationally efficient since all the maximal biclique patterns will be generated twice [1]. The symmetry property of the graph data set can be exploited to develop efficient algorithms for 3D maximal bicliques mining. In this paper, we propose CubeMiner-MBC algorithm for efficient mining of 3D maximal bicliques from 3D Boolean adjacency matrix containing no self loops. CubeMiner-MBC algorithm applies a subtree pruning technique, derived from the symmetric property of the graph data set, which prunes certain nodes in the enumeration tree and reduces the overall running time of the algorithm. The CubeMiner-MBC algorithm also incorporates several optimizations for efficient cutter generation and closure checking.
