MARGIN算法：有效挖掘最大频繁子图

需积分: 14 137 浏览量更新于2024-07-26 收藏 949KB PDF 举报

Maximal frequent subgraph mining 是一个在数据挖掘领域中处理复杂网络结构的重要问题，其核心挑战在于面对数量呈指数级增长的子图可能性。传统的频繁子图挖掘方法可能会面临搜索空间过大、效率低下的问题，因为所有可能的子图组合需要逐一评估其频繁性，这在大规模数据中几乎是无法承受的。在这种背景下，MARGIN (Maximal Frequent Subgraph Mining)算法应运而生。MARGIN算法的关键在于它专注于寻找搜索空间中的"边界"节点，这些节点位于频繁子图和不频繁子图的分界线上。通过这种方式，算法可以有效地避免对所有潜在候选模式进行无谓的搜索，显著地减小了待考虑的子图集合，从而提高了搜索效率。 MARGIN算法的运作机制是沿着频繁与不频繁子图的边界移动，只探索那些有可能包含最大频繁子图的节点。它的正确性通过理论证明得以保障，这意味着算法不仅在理论上有效，而且在实际应用中能够产生可验证的结果。实验结果显示，MARGIN技术在效率和实用性上都表现出色，特别是在处理大量数据时，能够显著提升频繁子图挖掘任务的性能。 MARGIN算法的研究集中在数据库管理领域，特别是数据挖掘应用中的数据归纳和模式发现。它的主要术语包括图挖掘（Graph mining）和最大频繁子图挖掘（Maximal Frequent Subgraph Mining），这些都是理解算法背景和技术细节的关键。此外，该工作还涉及到了算法设计中的通用术语——算法（Algorithms）。 MARGIN算法为解决大规模频繁子图挖掘问题提供了一种创新且高效的解决方案，它通过优化搜索策略，减少了计算量，使得在实际场景中，如社交网络分析、生物网络研究等，能快速提取出具有代表性的频繁子图结构，这对于理解和分析复杂的网络关系具有重要意义。

10:8

•

L. T. Thomas et al.

Fig. 4. Embedded model.

count of each node in the example lattice along with all the existing cuts in the

lattice L

and L

respectively.

Note that all isomorphic graphs of a graph g in the Lattice L

will thus have

the same support in D. However the subgraphs corresponding to the children

of each isomorphic form might be different. Also while one isomorphic form

of a subgraph might become a f (†)-node, the other might not. This is because

for one isomorphic form, all supergraphs might be frequent in a graph G

∈ D

while for another isomorphic form in G

∈ D there might exist an infrequent

supergraph making it a f (†)-node.

3.1 Lattice Representation Models

The lattice structure to the MARGIN algorithm can be represented using two

models, namely the replication model and the embedded model.

In the replication model (Figure 3), each subgraph g ⊂

graph

∈ D is repre-

sented exactly once in the lattice L

of G

as described in Section 3.

The embedded model is shown in Figure 4 for the graphs in Figure 2. In an

embedded model, the lattice L of the database D is common for all G

∈ D.All

isomorphic forms of any subgraph in D are represented using a single node in

the embedded model. Each node in the lattice L stores the information about

the occurrences of all of its isomorphic forms in the database. The bottommost

node corresponds to the empty graph φ

and the topmost nodes correspond to

the graphs in D. The graph a − c in Figure 2 has three isomorphic forms in

the database but will be represented exactly once along with the information

about its occurrence in G

at location 1 − 0and1− 2 and its occurrence in G

at location 0 − 1.

In the rest of the article, we proceed using the replication model unless

mentioned. With minor modiﬁcations the MARGIN algorithm can be applied

to the embedded model. A detailed discussion of the two models can be found

in Section 4.6.

4. THE MARGIN APPROACH

In 4.1, we provide the intuition behind the algorithm proposed to ﬁnd the max-

imal frequent subgraphs. In Section 4.2, we present the MARGIN algorithm

ACM Transactions on Knowledge Discovery from Data, Vol. 4, No. 3, Article 10, Pub. date: October 2010.

MARGIN: Maximal Frequent Subgraph Mining

•

10:9

Fig. 5. Upper-3-Property.

followed by the proof in Section 4.3. In the Section 4.6, we analyze the two

possible implementations of the lattice representation models.

4.1 Intuition

We start by deﬁning the Upper-

3-Property that holds in every lattice L

∈ D which we exploit in our algorithm.

ROPERTY 1(UPPER DIAMOND PROPERTY (Upper -3-PROPERTY)). Any two chil-

dren C

, C

of a node P, where C

, C

∈ Lattice L

of G

for G

∈ D, will have a

common child A.

ROOF.Lete

and e

be the edges incident on the vertices n

and n

in P

respectively. Let P ∪{e

}=C

and P ∪{e

}=C

as in Figure 5. Hence e

would

be incident on n

in C

and e

would be incident on n

in C

.LetA = C

∪{e

Hence, A = (P ∪{e

}) ∪{e

}=(P ∪{e

}) ∪{e

}=C

∪{e

Hence, A = C

∪{e

}=C

∪{e

} is the common child of C

and C

proving the

Upper-

3-property.

Consider any two children A

and A

of a node B in a lattice. In a lattice

of the replication model, by deﬁnition, A

and A

are obtained by extending

B. However, in the embedded model, any two children of a node need not be

the extensions of the same isomorphic form. Hence, in the embedded model,

the Upper-

3-property holds similarly except that A

and A

should be the

extensions of the same isomorphic form of the subgraph B in order to have a

common child C of A

and A

Next, we provide an intuition to the MARGIN algorithm. The set of can-

didate subgraphs that are likely to become maximally frequent are the f (†)

nodes. This is because they are frequent subgraphs having an infrequent child.

The remaining nodes of the lattice cannot be maximal frequent subgraphs. In

this article, we present an approach that avoids traversing the lattice bottom

up and instead traverses the cuts alone in each lattice L

for G

∈ D. We prune

the set of f (†) nodes to give the set of maximal frequent subgraphs. MAR-

GIN algorithm unlike the Apriori based algorithms goes directly to any one

of the f (†) nodes of the lattice L

and then ﬁnds all other f (†) nodes by cut-

ting across the lattice L

. We give an insight in this article into the approach

developed.

ACM Transactions on Knowledge Discovery from Data, Vol. 4, No. 3, Article 10, Pub. date: October 2010.

剩余41页未读，继续阅读

u010125929

粉丝: 0
资源: 2

MARGIN算法：有效挖掘最大频繁子图

Sliding window based weighted maximal frequent pattern mining over data streams

Identification of core-attachment complexes based on maximal frequent patterns in protein-protein interaction networks

Maximal Beasts

Maximal Cliques：找出图中所有的最大完全子图（maximal cliques）-matlab开发

Maximal contractions in Boolean algebras

Redundancy-Aware Maximal Cliques

MAXIMAL FLOW THROUGH A NETWORK

Find maximal cliques for large & sparse network:Find maximal cliques for large & sparse network-matlab开发

Maximal values of generalized algebraic immunity

A Maximal Clique Based Multiobjective Evolutionary algorithm

最新资源