tailieunhanh - Managing and Mining Graph Data part 37

Managing and Mining Graph Data part 37 is a comprehensive survey book in graph data analytics. It contains extensive surveys on important graph topics such as graph languages, indexing, clustering, data generation, pattern mining, classification, keyword search, pattern matching, and privacy. It also studies a number of domain-specific scenarios such as stream mining, web graphs, social networks, chemical and biological data. The chapters are written by leading researchers, and provide a broad perspective of the area. This is the first comprehensive survey book in the emerging topic of graph data processing. . | 3446 MANAGING AND MINING GRAPH DATA Figure . R topologically sorted directed acyclic graph. The label sequence kernel can be efficiently computed by dynamic programming running from right to left. Figure . Recursion for computing r x1 x 1 using recursive equation . r x1 x 1 can be computed based on the precomputed values of r x2 x 2 x2 x1 x2 x 1. General Directed Graphs. For cyclic graphs nodes cannot be topologically sorted. This means that we cannot employ a one-pass dynamic programming angorlthm los acyclic gtaphSn However we can obtain a recursive form Graph Classification 3147 cf kernel Hike and reduce the problem to solving a system of simultaneous linear equations. Let us rewrite as L k G G lim .EE s xi x re xi xi 242 L -x 1 if 1 1 1 1 xi xj where ri xi x i q xi x1 and re xi x i 52 t x2 x 2 xi x i 2 t x3 x 3 x2 x 2 x X2 x 2 52 t xi x xi-i x _i q xi x xe x e lfor I 2 Replacing oir ltri of summation in we have the following L k G G s xi xi lim rl xi xi V V i iy L -x i x1 x 1 l i 7 s xi x i lim RL xI x I Z 4 L -rx x1 x 1 where L Rl xi x i 52re xi x i . i i ritus we need to compute Rx xi x i to obtain k G G . Now let ut restate tins proCIcm in terms of linear system theory 38 The following recutrive rerateonsfop holds between r and rfe_i k 2 rk xi x i 52 t i j xi x i rk_i i j . i 3 sri4k 3448 MANAGING AND MINING GRAPH DATA Using the recursive relationship for Rl also holds as follows L Rl xi x i ri xi x i 2 rk xi xi k 2 L ri xi xi J2 t i j xi Xi rk-i i j k 2 i j ri xi xi 52 t i j Xi x i RL-i i j 2. 5 i j Thus Rl csn be perceived as a discrete-time linear system 38 evolving as the tiim L increases. Assuming that Rl csnverges see 21 los he convergence coiiiSilionSi we have the i oilowinss equilibrium equation R. xi x i ri xi x i 2 t i j xi x i R i j 31. 6 i j Therefore. the computation of the keenc 1 flnttily requires solving simultaneous linear cquationr and substituting the solutions into . Now .