在大型标记图中计数频繁模式:基于超图的方法
Jinghan Meng1, Napath Pitaksirianan1, Yi-Cheng Tu1
1University of South Florida, 4202 E Fowler Ave, Tampa, FL 33620, USA.
Data mining and knowledge discovery
|February 23, 2024
概括
本研究引入了一个新的超图框架,以统一图形挖掘支持措施,开发新的最小实例 (MI) 和最小顶点覆盖 (MVC) 措施. 这项研究揭示了多项式时间中MVC和最大独立集合 (MIS) 的常数因子近似算法.
科学领域:
- 图形数据库和数据挖掘
- 超图理论和算法 超图理论和算法
- 计算复杂性和近似算法算法.
背景情况:
- 图形数据库对于信息表示越来越受欢迎.
- 在单个图表中频繁的模式挖掘在支持措施和搜索计划中面临挑战.
- 现有的支持措施,如基于最小图像和基于重叠图的支持措施,都有局限性.
研究的目的:
- 提出一个新的框架,用于设计支持措施在单图矿业.
- 引入新的支持措施,最小实例 (MI) 和最小顶点覆盖 (MVC),基于事件/实例超图.
- 统一和分析现有和新的支持措施,揭示它们的界限关系和硬度特性.
主要方法:
- 开发了一个基于事件/实例超图的框架,以统一支持措施.
- 介绍并分析了新的支持措施:最小实例 (MI) 和最小顶点覆盖 (MVC).
- 利用线性编程和半确定的编程来实现MVC和最大独立集合 (MIS) 的多项式时间放松.
主要成果:
- 拟议的框架统一了大多数主要的现有和新的支持措施.
- 最小实例 (MI) 测量被证明与模式实例的数量密切相关.
- 发现了MVC和MIS的常数近似算法,挑战了先前的假设.
- 开发了MVC和MIS的多项式时间放松,计数限制在一个常数因子内.
结论:
- 基于超图的框架有效地统一了图形挖掘的各种支持措施.
- 像MI和MVC这样的新措施提供了优势,并在框架内得到了很好的描述.
- 该研究提供了关于图形挖掘措施的近似性和复杂性的重要见解.
相关概念视频
01:05Histogram
13.1K
The histogram is a graphical representation in the x-y form of data distribution in a data set. The horizontal x-axis is labeled with what the data represents (for instance, distance from your home to school). The vertical y-axis is labeled either frequency or relative frequency (or percent frequency or probability).
A histogram graph consists of contiguous (adjoining) boxes. The heights of the bars correspond to frequency values. The graph will have the same shape with respective labels. The...
A histogram graph consists of contiguous (adjoining) boxes. The heights of the bars correspond to frequency values. The graph will have the same shape with respective labels. The...
13.1K
00:54Time-Series Graph
4.4K
A time-series graph is a line graph with repeated measurements taken at successive intervals of time. It is also called a time series chart. To construct a time-series graph, one must look at both pieces of a paired data set. The horizontal axis is used to plot the time increments, and the vertical axis is used to plot the values of the variable that one is measuring. By using the axes in this way, each point on the graph will correspond to time and a measured quantity. The points on the graph...
4.4K
01:07Bar Graph
16.5K
A bar graph is also called a bar chart and consists of bars that are separated from each other. It either uses horizontal or vertical bars to show comparisons among categories. The bars can be rectangles, or they can be rectangular boxes (used in three-dimensional plots). One axis of the graph represents the specific categories being compared, and the other axis shows a discrete value. In this graph, the length of the bar for each category is proportional to the number or percent of individuals...
16.5K
01:07Multiple Bar Graph
5.1K
As the name suggests, a multiple bar graph is the same as a bar graph but has multiple bars to depict relationships between different data values. One can include as many parameters as possible. However, each parameter must have the same unit of measurement.
Each bar or column in the multiple bar graph represents a data value. These graphs are used primarily in interrelating two or more sets of data. The categories of different kinds of data are listed along the horizontal or x-axis, whereas...
Each bar or column in the multiple bar graph represents a data value. These graphs are used primarily in interrelating two or more sets of data. The categories of different kinds of data are listed along the horizontal or x-axis, whereas...
5.1K
01:17Probability Histograms
11.6K
A probability histogram is a visual representation of a probability distribution. Similar a typical histogram, the probability histogram consists of contiguous (adjoining) boxes. It has both a horizontal axis and a vertical axis. The horizontal axis is labeled with what the data represents. The vertical axis is labeled with probability. Each rectangular bar in the histogram is 1 unit wide, which suggests that the area under each bar equals the probability, P(x), where x is 1, 2, 3, and so on.
11.6K
01:14Relative Frequency Histogram
5.5K
The relative frequency depicts the proportion of data points that have each value. The frequency tells the number of data points that have each value. Like the histogram, a relative frequency histogram also has the same shape with a horizontal scale (the x-axis), but the vertical scale (the y-axis) is marked with relative frequencies (percentages of the whole) instead of actual frequencies. A relative frequency histogram is a graphical representation of a frequency distribution where the...
5.5K