With the recent ?ourishing research activities on Web search and mining, social networkanalysis, informationnetworkanalysis, informationretrieval, linkana- sis, andstructuraldatamining, researchonlinkmininghasbeenrapidlygrowing, forminganew?eldofdatamining. Traditionaldataminingfocuseson ?at or isolated datainwhicheachdata objectisrepresentedasanindependentattributevector. However, manyreal-world data sets are inter-connected, much richer in structure, involving objects of h- erogeneoustypesandcomplexlinks. Hence, thestudyoflinkminingwillhavea highimpactonvariousimportantapplicationssuchasWebandtextmining, social networkanalysis, collaborative?ltering, andbioinformatics. Asanemergingresearch?eld, therearecurrentlynobooksfocusingonthetheory andtechniquesaswellastherelatedapplicationsforlinkmining, especiallyfrom aninterdisciplinarypointofview. Ontheotherhand, duetothehighpopularity oflinkagedata, extensiveapplicationsrangingfromgovernmentalorganizationsto commercial businesses to people s daily life call for exploring the techniques of mininglinkagedata. Therefore, researchersandpractitionersneedacomprehensive booktosystematicallystudy, furtherdevelop, andapplythelinkminingtechniques totheseapplications. Thisbookcontainscontributedchaptersfromavarietyofprominentresearchers inthe?eld. Whilethechaptersarewrittenbydifferentresearchers, thetopicsand contentareorganizedinsuchawayastopresentthemostimportantmodels, al- rithms, andapplicationsonlinkmininginastructuredandconciseway. Giventhe lackofstructurallyorganizedinformationonthetopicoflinkmining, thebookwill provideinsightswhicharenoteasilyaccessibleotherwise. Wehopethatthebook willprovideausefulreferencetonotonlyresearchers, professors, andadvanced levelstudentsincomputersciencebutalsopractitionersinindustry. 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, AnwitamanDatta, andKuiyuChang 11 Veracity Analysis and Object Distinction. . . . . . . . . . . . . . . . . . . . . . . . . . 283 XiaoxinYin, JiaweiHan, andPhilipS. Yu Part IV Social Network Analysis 12 Dynamic Community Identi?cation. . . . . . . . .
