Link Mining: Models Algorithms and Applications

With the recent ?ourishing research activities on Web search and mining social networkanalysisinformationnetworkanalysisinformationretrievallinkana- sisandstructuraldataminingresearchonlinkmininghasbeenrapidlygrowing forminganew?eldofdatamining. Traditionaldataminingfocuseson\?at\or\isolated\datainwhicheachdata objectisrepresentedasanindependentattributevector. Howevermanyreal-world data sets are inter-connected much richer in structure involving objects of h- erogeneoustypesandcomplexlinks. Hencethestudyoflinkminingwillhavea highimpactonvariousimportantapplicationssuchasWebandtextminingsocial networkanalysiscollaborative?lteringandbioinformatics. Asanemergingresearch?eldtherearecurrentlynobooksfocusingonthetheory andtechniquesaswellastherelatedapplicationsforlinkminingespeciallyfrom aninterdisciplinarypointofview. Ontheotherhandduetothehighpopularity oflinkagedataextensiveapplicationsrangingfromgovernmentalorganizationsto commercial businesses to peoples daily life call for exploring the techniques of mininglinkagedata. Thereforeresearchersandpractitionersneedacomprehensive booktosystematicallystudyfurtherdevelopandapplythelinkminingtechniques totheseapplications. Thisbookcontainscontributedchaptersfromavarietyofprominentresearchers inthe?eld. Whilethechaptersarewrittenbydifferentresearchersthetopicsand contentareorganizedinsuchawayastopresentthemostimportantmodelsal- rithmsandapplicationsonlinkmininginastructuredandconciseway. Giventhe lackofstructurallyorganizedinformationonthetopicoflinkminingthebookwill provideinsightswhicharenoteasilyaccessibleotherwise. Wehopethatthebook willprovideausefulreferencetonotonlyresearchersprofessorsandadvanced levelstudentsincomputersciencebutalsopractitionersinindustry. Wewouldliketoconveyourappreciationtoallauthorsfortheirvaluablec- tributions. WewouldalsoliketoacknowledgethatthisworkissupportedbyNSF throughgrantsIIS-0905215IIS-0914934andDBI-0960443. ChicagoIllinois PhilipS. Yu Urbana-ChampaignIllinois JiaweiHan PittsburghPennsylvania ChristosFaloutsos v Contents Part I Link-Based Clustering 1 Machine Learning Approaches to Link-Based Clustering. . . . . . . . . . . 3 Zhongfei(Mark)ZhangBoLongZhenGuoTianbingXu andPhilipS. Yu 2 Scalable Link-Based Similarity Computation and Clustering. . . . . . . . 45 XiaoxinYinJiaweiHanandPhilipS. Yu 3 Community Evolution and Change Point Detection in Time-Evolving Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 JimengSunSpirosPapadimitriouPhilipS. YuandChristosFaloutsos Part II Graph Mining and Community Analysis 4 A Survey of Link Mining Tasks for Analyzing Noisy and Incomplete Networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 GalileoMarkNamataHossamShararaandLiseGetoor 5 Markov Logic: A Language and Algorithms for Link Mining. . . . . . . 135 PedroDomingosDanielLowdStanleyKokAniruddhNathHoifung PoonMatthewRichardsonandParagSingla 6 Understanding Group Structures and Properties in Social Media. . . . 163 LeiTangandHuanLiu 7 Time Sensitive Ranking with Application to Publication Search. . . . . 187 XinLiBingLiuandPhilipS. 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?catio