Link Mining: Models, Algorithms, and Applications

Wewouldliketoconveyourappreciationtoallauthorsfortheirvaluablec- tributions. WewouldalsoliketoacknowledgethatthisworkissupportedbyNSF throughgrantsIIS-0905215,IIS-0914934,andDBI-0960443. Chicago,Illinois PhilipS. Yu Urbana-Champaign,Illinois JiaweiHan Pittsburgh,Pennsylvania ChristosFaloutsos v Contents Part I Link-Based Clustering 1 Machine Learning Approaches to Link-Based Clustering. . . . . . . . . . . 3 Zhongfei(Mark)Zhang,BoLong,ZhenGuo,TianbingXu, andPhilipS. Yu 2 Scalable Link-Based Similarity Computation and Clustering. . . . . . . . 45 XiaoxinYin,JiaweiHan,andPhilipS. Yu 3 Community Evolution and Change Point Detection in Time-Evolving Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 JimengSun,SpirosPapadimitriou,PhilipS. Yu,andChristosFaloutsos Part II Graph Mining and Community Analysis 4 A Survey of Link Mining Tasks for Analyzing Noisy and Incomplete Networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 GalileoMarkNamata,HossamSharara,andLiseGetoor 5 Markov Logic: A Language and Algorithms for Link Mining. . . . . . . 135 PedroDomingos,DanielLowd,StanleyKok,AniruddhNath,Hoifung Poon,MatthewRichardson,andParagSingla 6 Understanding Group Structures and Properties in Social Media. . . . 163 LeiTangandHuanLiu 7 Time Sensitive Ranking with Application to Publication Search. . . . . 187 XinLi,BingLiu,andPhilipS. Yu 8 Proximity Tracking on Dynamic Bipartite Graphs: Problem De?nitions and Fast Solutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 Hanghang Tong, Spiros Papadimitriou, Philip S. Yu, andChristosFaloutsos vii viii Contents 9 Discriminative Frequent Pattern-Based Graph Classi?cation. . . . . . . . 237 HongCheng,XifengYan,andJiaweiHan Part III Link Analysis for Data Cleaning and Information Integration 10 Information Integration for Graph Databases. . . . . . . . . . . . . . . . . . . . . 265 Ee-PengLim,AixinSun