(p,q) - - 对大型稀疏双部分图形进行双边计数和计数
Jianye Yang1, Yun Peng1, Dian Ouyang1
1Guangzhou University, Guangzhou, China.
The VLDB journal : very large data bases : a publication of the VLDB Endowment
|June 26, 2023
概括
本研究介绍了BCList++在大型二分位图中进行高效的双旋计数,显著优于现有方法. 一个扩展,IUBCList,处理不确定的图表,提供了相当大的加速度.
科学领域:
- 图形理论和算法
- 计算数学 计算数学 计算数学
- 数据挖掘和网络分析.
背景情况:
- 二分位图是各种应用中的基本结构,包括网络分析和机器学习.
- 有效地计算和列举双曲线 (完整的子图) 对于像图形神经网络 (GNN) 优化和最密集的子图检测等任务至关重要.
- 现有的方法在大型,稀疏的二分位图的可扩展性和效率方面扎,缺乏对双曲线计数的有效解决方案.
研究的目的:
- 开发高效的算法来计算和计算 (p,q) 双位数在大型稀疏的二分位图中.
- 提出一种先进的方法,BCList++,通过减少计算复杂性来改进基线方法.
- 为了将双旋计数技术扩展到不确定的二分位图,使用一种有效的方法,IUBCList.
主要方法:
- 介绍了BCList,这是一个分支和绑定的算法,用于双旋计数的修剪技术.
- 开发了BCList++,采用基于层的探索策略和成本模型,以优化双曲列举.
- 拟议的IUBCList,基于BCList++和修剪技术来处理不确定的二分位图.
主要成果:
- BCList++ 显示出显著的性能改进,在真实数据集上表现高达三倍的基准方法.
- 在BCList++中的成本模型有效地指导了计算层的选择,提高了效率.
- IUBCList实现了显著的加快速度,在不确定的二分位图上,在两位数的数量上超过了基线方法.
结论:
- BCList++提供了一个可扩展和高效的解决方案,用于 (p,q) -biclique计数和列举在大型稀疏的二分位图中.
- 开发的方法,特别是BCList++和IUBCList,在计算图形理论方面取得了重大进展.
- 这些发现突出了双点分析在优化图形神经网络和其他复杂网络应用中的潜力.
相关概念视频
01:12Bewley Lattice Diagram
771
The Bewley lattice diagram, developed by L. V. Bewley, effectively organizes the reflections occurring during transmission-line transients. It visually represents how voltage waves propagate and reflect within a transmission line, making it easier to understand the complex interactions that occur.
771
01:17Cochran's Q Test
428
Cochran's Q Test is a nonparametric statistical test used to determine if there are potential differences in the outcomes of three or more related groups on a binary (yes/no) or dichotomous outcome. It is essentially an extension of the McNemar Test, which is limited to two related samples - Cochran's Q test can handle three or more related samples, making it more versatile in scenarios where subjects are measured under multiple conditions. The test statistic follows a Chi-Square...
428
01:09The Buckingham Pi Theorem
755
The Buckingham Pi theorem provides a structured method to simplify fluid dynamics problems by reducing complex systems of variables to dimensionless terms.
755
01:12Theorems of Pappus and Guldinus: Problem Solving
769
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
769
02:33Lattice Centering and Coordination Number
9.7K
The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
Types of Unit Cells
Imagine taking a large number of identical...
9.7K
01:08Hückel's Rule Diagram of π MOs: Frost Circle
4.5K
The Frost circle or the inscribed polygon method is a graphical method for determining the relative energies of π molecular orbitals (MOs) for planar, fully conjugated, and monocyclic compounds. This method was first described by A. A. Frost and Boris Musulin in 1953.
A Frost circle is constructed by drawing a polygon whose number of edges is equal to the number of carbons of the given cyclic system, with one of the vertices pointing down. Then, a circle is drawn enclosing the polygon so...
A Frost circle is constructed by drawing a polygon whose number of edges is equal to the number of carbons of the given cyclic system, with one of the vertices pointing down. Then, a circle is drawn enclosing the polygon so...
4.5K