tailieunhanh - Managing and Mining Graph Data part 14

Managing and Mining Graph Data part 14 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. . | Graph Mining Laws and Generators 111 that only 3 parameters might not progride enough degrees of freedom to match all varieties of graphs extensions of this model should be investigated. A itep its thit direction is the Kronecker graph generator 157 which generalizas the R-MAT model and can maich several interesting patterns such as the llamshricatlon Power Law and the shrinking diameters effect in addition to all ticc RpMAT matches. Graph Generation by Kronecker Multiplication. The R-MAT genera- tor described in the p-eviour paragraphs achieves its power mainly via a form of recursions the adjacency matrix is recursively split into equal-sized quadrants over cx liicli edget are distributed unequatiy. One way to generalize this idea ir vit i. Kronecker matrix wherein one small initial matrix is recursevely imultiplieO with itself to yield 1 arge graph topologies. Unlike RM AT this generatoi has simple closediform expressions for several measures of interest. such as deerre dislrihulions and diamoters thus enabling ease of aneliysis trn parameter-titling. Description and properties. We first recall the deli nition of the Kronecker product. Definition Kronecker product of matrices . Given two matrices A agj and B of sizes n x m and n x m respectively the Kronecker product matrix C of dimensions n n x m m is given by C A B I 1 1 B 02 1 B an iB ai 2B . aymB O2 2B . O2 mB . . an 2B . . . an mB f In other words for any nodes Xi and Xj in A and X -. ami X in B we have nodes Xi fe ami Xjy in the Kronecker product C and an edge connects them iff edges Xi Xj ami X X exist in A ami B. The Kroncckcn product of two guaphs is lire Kronecker product of their adjacency matrices. Let us consider an example. Ilig ut c a-c shows the recursive construction of G H when G H is a 3-node psth. Consider node X1 2 in Figure ci It belongs to the H graph lloat replaced node X1 see Figure 3. Ififefe and in fact is the X2 nodi he