MANAGING AND MINING GRAPH DATA - Charu Aggarwal

1 MANAGING AND MINING GRAPH DATAMANAGING AND MINING GRAPH DATAE dited byCHARU C. AGGARWALIBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USAHAIXUN WANGM icrosoft Research Asia, Beijing, China 100190 Kluwer Academic PublishersBoston/Dordrecht/LondonContent sList of FiguresxvList of TablesxxiPrefacexxiii1An Introduction to GRAPH Data1 Charu C. Aggarwal and Haixun Management and MINING data Management and MINING : A Survey of Algorithms andApplications13 Charu C. Aggarwal and Haixun data Management and Query Processing Construction of Massive MINING MINING in Algorithms for GRAPH Algorithms for GRAPH Dynamics of Time-Evolving and Biological Bug and Future Research55 References553 GRAPH MINING : Laws and Generators69 Deepayan Chakrabarti,Christos Faloutsos and Mary Patterns71viMANAGING AND MINING GRAPH Laws and Heavy-Tailed Static GRAPH in Evolving Structure of Specific GRAPH Attachment and for specific Generators: A Language and Access Methods for GRAPH Databases125 Huahai He and Ambuj K.

2 Specific on GRAPH Query of the Selection Pattern Pruning and Retrieval of Feasible Reduction of Search of Search Query Research : Query Syntax of GraphQL156 References1575 GRAPH Indexing161 Xifeng Yan and Jiawei GRAPH Frequent Similarity Structural Miss Set with Substructure Reachability Queries: A Survey181 Jeffrey Xu Yu and Jiefeng + the Optimal Chain Heuristic Geometrical-Based Partitioning Cover 2-Hop Pattern Special Case: A General and Summary212 References2127 Exact and Inexact GRAPH Matching: Methodology and Applications217 Kaspar Riesen,Xiaoyi Jiang and Horst GRAPH GRAPH Edit Inexact GRAPH Matching Matching for data MINING and Information Retrieval231viiiMANAGING AND MINING GRAPH Space Embeddings of Graphs via GRAPH Survey of Algorithms for Keyword Search on GRAPH Data249 Haixun Wang and Charu C.

3 Search on XML for LCA-based Keyword Search on Relational and Search on Schema-Free Semantics and Answer Exploration by Backward Exploration by Bidirectional GRAPH Exploration the BLINKS ObjectRank and Future Research271 References2719A Survey of Clustering Algorithms for GRAPH Data275 Charu C. Aggarwal and Haixun Clustering Minimum Cut GRAPH Generalizations and Network Structure Girvan-Newman Spectral Clustering Case of Massive Graphs as Classical Algorithms to Structural XProj of GRAPH Clustering Detection in Web Applications and Social and Future Research297 References29910A Survey of Algorithms for Dense Subgraph Discovery303 Victor E. Lee,Ning Ruan,Ruoming Jin and Charu of Dense vs. Relative of Dense Component between Clusters and Dense for Detecting Dense Components in a Single Enumeration and Approximation Algorithms for Discovering Dens-est Dense Patterns with Density Components with Frequency Cross- GRAPH of Dense Component and Future Research331 References33311 GRAPH Classification337 Koji Tsuda and Hiroto Walks on Sequence Computation of Label Sequence of GRAPH Pattern of GRAPH Remarks359 References35912 MINING GRAPH Patterns365 Hong Cheng,Xifeng Yan and Jiawei Subgraph and Maximal Subgraphs in a Single Computational Significant GRAPH : A Branch-and-Bound Approach373xMANAGING AND MINING GRAPH : A Partial Least Squares Regression : A Structural Leap Search.

4 A Feature Representation Representative Orthogonal Maximal Subgraph Representative Set Survey on Streaming Algorithms for Massive Graphs393 Jian Model for Massive and Counting Approximation using Multiple Approximation in One Walks on Survey of Privacy-Preservation of Graphs and Social Networks421 Xintao Wu,Xiaowei Ying,Kun Liu and Lei in Publishing Social Attacks on Naive Anonymized Attacks and Passive Privacy Preservation via Edge Preservation via to Structural Disclosure Preserving Preservation via Rich Protection in Rich Bipartite Rich Interaction Edge-Weighted Privacy Issues in Online Social Link Structure of the Entire Personal Identifying Information from SocialNet-working and Future Work448 Acknowledgments449 References44915A Survey of GRAPH MINING for Web Applications455 Debora Donato and Aristides Analysis Ranking High-Quality of Successful Items in a Co-citation High-Quality Content in Question-Answering Query of Query Log MINING Applications to Social Network Analysis487 Lei Tang and Huan Patterns in Large-Scale Community Community Community Community Structure Issues507 References50817 Software-Bug Localization with

5 GRAPH Mining515 Frank Eichinger and Klemens of Call GRAPH Based Bug Localization517xiiMANAGING AND MINING GRAPH Call in Localization with Call and Tree GRAPH Based Bug and Future Directions542 Acknowledgments543 References54318A Survey of GRAPH MINING Techniques for Biological Datasets547S. Parthasarathy,S. Tatikonda and D. Subtree Alignment and Graphs for the Discovery of Frequent Subgraph Discovery in Biological Graphs for the Discovery of in Chemical GRAPH data Mining581 Nikil Wale,Xia Ning and George Descriptors for Chemical Fingerprints (FP) Keys (MK) Connectivity Fingerprints (ECFP) Subgraphs (FS) GRAPH Fragments (GF) of Algorithms for Chemical based on based on GRAPH Compound Based on Direct Based on Indirect of Indirect Similarity Potential Targets for Methods For Target of Target Fishing Research Directions601 References602 Index607 List of laws and and effective properties of the campaign donations GRAPH : (a)shows all weight properties, including the densificationpower law and WPL.

6 (b) and (c) show the Snapshot PowerLaw for in- and out-degrees. Both have slopes>1( for-tification effect ), that is, that the more campaigns anorganization supports, the superlinearly-more money itdonates, and similarly, the more donations a candidategets, the more average amount-per-donation is plots on (c) and (d) showiwandowversus they are very stable over Densification Power LawThe number of edgesE(t)is plotted against the number of nodesN(t)on log-logscales for (a) the arXiv citation GRAPH , (b) the patents ci-tation GRAPH , and (c) the Internet Autonomous Systemsgraph. All of these grow over time, and the growth fol-lows a power law in all three cases component properties of Postnet network, anetwork of blog posts. Notice that we experience anearly gelling point at (a), where the diameter peaks. Notein (b), a log-linear plot of component size vs. time, thatat this same point in time the giant connected componenttakes off, while the sizes of the second and third-largestconnected components (CC2 and CC3) stabilize.

7 We fo-cus on these next-largest connected components in (c).84xviMANAGING AND MINING GRAPH patterns for a network of blog posts. (a) showsthe entropy plot of edge additions, showing inset shows the addition of edges over time. (b)describes the decay of post popularity. The horizontalaxis indicates time since a post s appearance (aggregatedover all posts), while the vertical axis shows the numberof links acquired on that Internet as a Jellyfish Bowtie structure of the Erd-os-R enyi Barab asi-Albert edge copying Heuristically Optimized Tradeoffs small-world Waxman R-MAT of Kronecker multiplicationTop: a 3-chain and its Kronecker product with itself; each of theXinodes gets expanded into3nodes, which are then linkedtogether. Bottom row: the corresponding adjacency ma-trices, along with matrix for the fourth Kronecker sample GRAPH query and a GRAPH in the simple GRAPH (a) Concatenation by edges, (b) Concatenation by (a) Path and cycle, (b) Repetition of sample GRAPH with sample GRAPH mapping between the GRAPH pattern in Figure andthe GRAPH in Figure example of valued (a) A GRAPH template with a single parameterP, (b) Agraph instantiated from the GRAPH in Figure and Figure GRAPH query that generates a co-authorship GRAPH fromthe DBLP possible execution of the Figure translation of a GRAPH into facts of Datalog139 List of translation of a GRAPH pattern into a rule of sample GRAPH pattern and mates using neighborhood subgraphs and pro-files.

8 The resulting search spaces are also shown for dif-ferent pruning of the search examples of search space for clique time for clique queries (low hits) space and running time for individual steps (syn-thetic graphs, low hits) time (synthetic graphs, low hits) Support and Simple GraphG(left) and Its Index (right) (Figure 1in 32) Codes Used in Dual-Labeling (Figure 2 in 34) Cover (based on Figure in 1) a virtual Directed GRAPH , and its Two DAGs,G andG (Fig-ure 2 in 13) (Aw, w, Dw) (Figure 6 in 14) Maintenance Closure 2-hop Distance Aware Cover (Figure 2 in 10) Algorithm Steps (Figure 3 in 10) GRAPH (Figure 1(a) in 12) GRAPH Database forGD(Figure 2 in 12) kinds of graphs: (a) undirected and unlabeled,(b) directed and unlabeled, (c) undirected with labelednodes (different shades of gray refer to different labels),(d) directed with labeled nodes and (b) is an induced subgraph of (a), and GRAPH (c) isa non-induced subgraph of (a).

9 221xviiiMANAGING AND MINING GRAPH (b) is isomorphic to (a), and GRAPH (c) is isomor-phic to a subgraph of (a). Node attributes are indicatedby different shades of (c) is a maximum common subgraph of GRAPH (a)and (b). (a) is a minimum common supergraph of GRAPH (b) and (c). possible edit path between graphg1and graphg2(nodelabels are represented by different shades of gray). and database Semantics for Keyword SearchQ={x, y}onXML size of the join tree is only bounded by the data matching and join trees expansion across clusters may per-form Sub-structural Clustering Algorithm (High Level De-scription) GRAPH to Illustrate Component example of web example of Shingling of CSV Set Enumeration Tree for{x,y,z} classification and label rules of kernel (a) An example of labeled graphs. Vertices and edges arelabeled by uppercase and lowercase letters, traversing along the bold edges, the label sequence( ) is produced.

10 (b) By repeating random walks, onecan construct a list of topologically sorted directed acyclic GRAPH . The labelsequence kernel can be efficiently computed by dynamicprogramming running from right to for computingr(x1, x 1)using recursive equa-tion ( ).r(x1, x 1)can be computed based on the pre-computed values ofr(x2, x 2), x2> x1, x 2> x space based on subgraph patterns. The featurevector consists of binary pattern of figure of the tree-shaped search space of graphpatterns ( , the DFS code tree). To find the optimalpattern efficiently, the tree is systematically expanded byrightmost 20 discriminative subgraphs from the CPDB subgraph is shown with the corresponding weight,and ordered by the absolute value from the top left tothe bottom right. H atom is omitted, and C atom isrepresented as a dot for simplicity. Aromatic bonds ap-peared in an open form are displayed by the combinationof dashed and solid obtained by gPLS.