Database Reference
In-Depth Information
of duplicate patterns seen within the same or across different random walks. As a
random walk chain is traversed, ORIGAMI maintains the signature of the intermedi-
ate patterns in a bounded size hash table. As an intermediate or maximal subgraph is
generated, its signature is added to the hash table and the collision rate is updated. If
the collision rate exceeds a threshold , the method could (1) abort further extension
along the current path and randomly choose another path; or (2) trigger the termina-
tion condition across different walks, since it implies that the same part of the search
space is being revisited.
4.3
Orthogonal Representative Set Generation
Given a set of maximal subgraphs M
, the next step is to extract an α -orthogonal β -
representative set from it. We can construct a meta-graph Γ ( M
) to measure similarity
between graph patterns in M
, in which each node represents a maximal subgraph
pattern, and an edge exists between two nodes if their similarity is bounded by α .
Then the problem of finding an α -orthogonal pattern set can be modeled as finding
a maximal clique in the similarity graph Γ ( M
).
Foragiven α , there could be multiple α -orthogonal pattern sets as feasible so-
lutions. We could use the size of the residue set to measure the goodness of an
α -orthogonal set. An optimal α -orthogonal β -representative set is the one which
minimizes the size of the residue set. [ 2 ] proved that this problem is NP-hard.
Given the hardness result, ORIGAMI resorts to approximate algorithms to solve
the problem which guarantees local optimality. The algorithm starts with a random
maximal clique in the similarity graph Γ ( M
) and tries to improve it. At each state
transition, another maximal clique which is a local neighbor of the current maximal
clique is chosen. If the new state has a better solution, the new state is accepted as the
current state and the process continues. The process terminates when all neighbors of
the current state have equal or larger residue sizes. Two maximal cliques of size m and
n (assume m
1 vertices. The
state transition procedure selectively removes one vertex from the maximal clique of
the current state and then expands it to obtain another maximal clique which satisfies
the neighborhood constraints.
n ) are considered neighbors if they share exactly n
5
Mining Dense Graph Patterns
Mining dense subgraphs is an important graph mining task. Dense subgraphs are use-
ful patterns for many applications, such as detecting communities in social networks,
detecting link spams on the Web, finding motifs in biological networks, visualizing
complex networks, and so on. There are different definitions of dense subgraph
patterns, including clique [ 10 , 12 , 42 , 44 ], quasi-clique [ 36 ], k -core [ 11 ], k -truss
[ 39 , 52 ], dense neighborhood graph [ 41 ], dense bipartite subgraph [ 18 ], etc. Such
Search WWH ::




Custom Search