Link Mining: Models, Algorithms, and Applications



430 pages  (PDF 600Pages)
Publisher: Springer; 1st Edition. edition (29 Sep 2010)
Language English
ISBN-10: 1441965149
ISBN-13: 978-1441965141

This book presents in-depth surveys and systematic discussions on models, algorithms and applications for link mining. Link mining is an important field of data mining. Traditional data mining focuses on "flat" data in which each data object is represented as a fixed-length attribute vector. However, many real-world data sets are much richer in structure, involving objects of multiple types that are related to each other. Hence, recently link mining has become an emerging field of data mining, which has a high impact in various important applications such as text mining, social network analysis, collaborative filtering, and bioinformatics. At present, there are no books in the market focusing on the theory and techniques as well as the related applications for link mining. On the other hand, due to the high popularity of linkage data, extensive applications ranging from governmental organizations to commercial businesses to people’s daily life call for exploring the techniques of mining linkage data; people need such a reference book to systematically apply the link mining techniques to these applications to develop the related technologies. Therefore, such a book is in high demand on the market.



Contents
Part I Link-Based Clustering
1 Machine Learning Approaches to Link-Based Clustering . . . . . . . . . . . 3
Zhongfei (Mark) Zhang, Bo Long, Zhen Guo, Tianbing Xu,
and Philip S. Yu
2 Scalable Link-Based Similarity Computation and Clustering . . . . . . . . 45
Xiaoxin Yin, Jiawei Han, and Philip S. Yu
3 Community Evolution and Change Point Detection
in Time-Evolving Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Jimeng Sun, Spiros Papadimitriou, Philip S. Yu, and Christos Faloutsos
Part II Graph Mining and Community Analysis
4 A Survey of LinkMining Tasks for Analyzing Noisy and Incomplete
Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Galileo Mark Namata, Hossam Sharara, and Lise Getoor
5 Markov Logic: A Language and Algorithms for Link Mining . . . . . . . 135
Pedro Domingos, Daniel Lowd, Stanley Kok, Aniruddh Nath, Hoifung
Poon, Matthew Richardson, and Parag Singla
6 Understanding Group Structures and Properties in Social Media . . . . 163
Lei Tang and Huan Liu
7 Time Sensitive Ranking with Application to Publication Search . . . . . 187
Xin Li, Bing Liu, and Philip S. Yu
8 Proximity Tracking on Dynamic Bipartite Graphs: Problem
Definitions and Fast Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
Hanghang Tong, Spiros Papadimitriou, Philip S. Yu,
and Christos Faloutsos
vii
viii Contents
9 Discriminative Frequent Pattern-Based Graph Classification . . . . . . . . 237
Hong Cheng, Xifeng Yan, and Jiawei Han
Part III Link Analysis for Data Cleaning and Information Integration
10 Information Integration for Graph Databases . . . . . . . . . . . . . . . . . . . . . 265
Ee-Peng Lim, Aixin Sun, Anwitaman Datta, and Kuiyu Chang
11 Veracity Analysis and Object Distinction . . . . . . . . . . . . . . . . . . . . . . . . . . 283
Xiaoxin Yin, Jiawei Han, and Philip S. Yu
Part IV Social Network Analysis
12 Dynamic Community Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
Tanya Berger-Wolf, Chayant Tantipathananandh, and David Kempe
13 Structure and Evolution of Online Social Networks . . . . . . . . . . . . . . . . 337
Ravi Kumar, Jasmine Novak, and Andrew Tomkins
14 Toward Identity Anonymization in Social Networks . . . . . . . . . . . . . . . . 359
Kenneth L. Clarkson, Kun Liu, and Evimaria Terzi
Part V Summarization and OLAP of Information Networks
15 Interactive Graph Summarization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
Yuanyuan Tian and Jignesh M. Patel
16 InfoNetOLAP: OLAP and Mining of Information Networks . . . . . . . . 411
Chen Chen, Feida Zhu, Xifeng Yan, Jiawei Han, Philip Yu,
and Raghu Ramakrishnan
17 Integrating Clustering with Ranking in Heterogeneous Information
Networks Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
Yizhou Sun and Jiawei Han
18 Mining Large Information Networks by Graph Summarization . . . . . 475
Chen Chen, Cindy Xide Lin, Matt Fredrikson, Mihai Christodorescu,
Xifeng Yan, and Jiawei Han
Part VI Analysis of Biological Information Networks
19 Finding High-Order Correlations in High-Dimensional
Biological Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
Xiang Zhang, Feng Pan, and Wei Wang
Contents ix
20 Functional Influence-Based Approach to Identify Overlapping
Modules in Biological Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
Young-Rae Cho and Aidong Zhang
21 Gene Reachability Using Page Ranking on Gene Co-expression
Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
Pinaki Sarder, Weixiong Zhang, J. Perren Cobb, and Arye Nehorai
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569