Database Reference
In-Depth Information
5.3
Other Dense Subgraph Patterns
Wang et al. [ 41 ] defined another type of dense subgraph pattern, called dense neigh-
borhood graph (DN-graph), based on the common neighbors. A DN-graph with
parameter λ , denoted as G ( V , E , λ ), is a connected subgraph of graph G ( V , E )
that satisfies the following conditions: (1) every connected pair of vertices in G
share at least λ common neighbors; and (2) for any v
V , λ ( V ∪{
V
\
v
}
) ,
V , λ ( V −{
and for any v
λ . Here, λ ( V ) measures the minimal joint
neighborhood size between any connected vertex pair inside the vertex set V .Itis
proved that mining DN-graphs is NP-complete, by making a connection with the
maximal clique mining problem. As the joint neighborhood size of two vertices u , v
is in fact the number of triangles the edge e ( u , v ) participates in a graph, approximate
algorithms are proposed which iteratively generate triangles to refine the λ values
of graph edges. Another algorithm Stream DN is also proposed for semi-streaming
graph setting, which assumes that the graph vertices can be fitted into main memory,
while the edges are stored in an ordered manner in the secondary storage.
Gibson et al. [ 18 ] proposed an algorithm for mining dense bipartite subgraphs
in massive graphs. Informally, a dense bipartite subgraph in a graph G ( V , E )isa
pair of subset A , B
v
}
)
B .
Here, 'most' parameterizes the density of the subgraph. An efficient algorithm is
proposed to mine the dense bipartite subgraphs by recursively fingerprinting the
graph. Specifically, for each node in a graph, the algorithm applies a shingling
algorithm to the set of destinations linked-to from that node. An s -element subset
of the destination set forms a shingle. Nodes that share a sufficiently large number
of shingles are clustered together. In the next phase, shingles that tend to occur on
the same nodes are grouped together, as the commonly co-occurring shingles lead to
the identification of a dense bipartite subgraph. The recursive shingling process can
convert dense subgraphs of arbitrary size into small-size fingerprints, which allow
identifying the dense subgraphs in a straightforward manner.
V of nodes such that ( a , b )
E for 'most' a
A , b
6
Mining Graph Patterns in Streams
Recently, there have been studies on mining graph patterns in a streaming environ-
ment. In the streaming model, one assumes that the input can be read sequentially in
a number of passes over the data, while the total amount of random access memory
(RAM) for computation is sublinear in the size of the input. The goal is to reduce
the number of passes on the data, while minimizing the amount of RAM for storing
the intermediate results.
Aggarwal et al. [ 1 ] studied mining dense graph patterns in graph streams. The
stream
S
is defined as the sequence G 1 , ... , G r , ... , where each graph G i is a set of
edges. The mined patterns should have two desired properties: node co-occurrences
and edge density. That is, a set of nodes co-occur frequently in the graphs, and the
edges among these nodes are dense. The node co-occurrence over a set of nodes
Search WWH ::




Custom Search