【摘要】 二分图可以对2种不同类型实体之间的关系进行建模。二分图中的团称为二分团，是其基本的稠密子结构。计算给定二分图中(p,q)二分团的个数具有十分重要的意义。针对现有二分团计数方法因输入图规模较大所导致的低效性问题，本文提出针对(p,q)二分团计数的优化方法，该方法通过构建二分图中所有不相交最大二分团的索引MBC＿I,可以显著减少二分团计数方法输入图的规模，提升(p,q)二分团计数的效率。之后，提出基于度的整体删减策略，并基于此提出优化计数算法CNBC＿I~*,来进一步提高计数效率。最后，在多个数据集上进行了实验，实验结果验证了本文方法的高效性。更多还原

【Abstract】 The bipartite graph can model the relationship between two different types of entities. The clique in a bipartite graph is called a biclique and is its basic dense substructure. Calculating the number of(p,q)-bicliques in a given bipartite graph is of great significance. In response to the inefficiency caused by the large input graph size of existing bicliques counting methods, this paper proposes an optimization method for(p,q)-bicliques counting. This method significantly reduces the input graph size of bicliques counting methods and improves the efficiency of(p,q)-bicliques counting by constructing the index MBC＿I for all non-intersecting maximum bicliques in the bipartite graph. Afterwards, a degree based overall pruning strategy is proposed, and based on this, an optimized counting algorithm CNBC＿I~* is proposed to further improve counting efficiency. Finally, experiments are conducted on multiple datasets, and the experimental results validate the efficiency of the proposed method.更多还原